Department of

Mathematics


Seminar Calendar
for Graph Theory and Combinatorics Semianr events the year of Wednesday, August 16, 2017.

     .
events for the
events containing  

(Requires a password.)
More information on this calendar program is available.
Questions regarding events or the calendar should be directed to Tori Corkery.
      July 2017             August 2017           September 2017   
 Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa
                    1          1  2  3  4  5                   1  2
  2  3  4  5  6  7  8    6  7  8  9 10 11 12    3  4  5  6  7  8  9
  9 10 11 12 13 14 15   13 14 15 16 17 18 19   10 11 12 13 14 15 16
 16 17 18 19 20 21 22   20 21 22 23 24 25 26   17 18 19 20 21 22 23
 23 24 25 26 27 28 29   27 28 29 30 31         24 25 26 27 28 29 30
 30 31                                                             

Tuesday, March 28, 2017

3:00 pm in 241 Altgeld Hall,Tuesday, March 28, 2017

Combinatorial geometry problems and Turán hypergraphs

Zoltán Furëdi (Illinois Math and Renyi Institute of Mathematics)

Abstract: We overlook a few applications of using extremal hypergraphs in combinatorial geometry questions. A sample result: Let $h(n)$ be the maximum number of triangles among $n$ points on the plane which are almost regular (all three angles are between 59 to 61 degrees). Conway, Croft, Erdős and Guy (1979) proved an upper bound for $h(n)$ and conjectured that $h(n)=(1+o(1)) n^3/ 24$. We prove this (and other) conjectures. Among our main tools we use Razborov's flag algebra method to determine the Turán numbers of certain 3-uniform hypergraphs. This is a joint work with Imre Bárány (with some computer help from Manfred Scheucher).

Tuesday, April 4, 2017

3:00 pm in 241 Altgeld Hall,Tuesday, April 4, 2017

Orthogonal one-factorizations\\ of complete multipartite graphs

Mariusz Meszka (AGH University of Science and Technology, Kraków, Poland)

Abstract: A one-factor of a graph $G$ is a regular spanning subgraph of degree one. A one-factorization of $G$ is a set ${\cal F}=\{F_1,\,F_2,\ldots ,F_r\}$ of edge-disjoint one-factors such that $E(G)=\bigcup_{i=1}^r E(F_i)$. Two one-factorizations ${\cal F}=\{F_1,\,F_2,\ldots ,F_r\}$ and ${\cal F'}=\{F'_1,\,F'_2,\ldots ,F'_r\}$ are orthogonal if $|F_i\cap F'_j|\leq 1$ for all $1\leq i < j \leq r$. A set of $k$ one-factorizations $\{{\cal F}^1,{\cal F}^2,\ldots ,{\cal F}^k\}$ of $G$ is mutually orthogonal if, for every $1\leq i < j\leq k$, ${\cal F}^i$ and ${\cal F}^j$ are orthogonal. A pair of orthogonal one-factorizations of an $s$-regular graph $G$ on $2n$ vertices corresponds to the existence of a Howell design of type $(s,2n)$, for which a graph $G$ is called an underlying graph. Let $S$ be a set of $2n$ symbols. A Howell design $H(s,2n)$ on the symbol set $S$ is an $s\times s$ array that satisfies the following conditions: (1) every cell is either empty or contains an unordered pair of symbols from $S$, (2) every symbol of $S$ occurs exactly once in each row and exactly once in each column of $H$, (3) every unordered pair of symbols occurs in at most one cell of $H$. Necessary condition for the existence of Howell designs $H(s,2n)$ is $n\leq s\leq 2n-1$. A pair of orthogonal one-factorizations of a complete bipartite graph $K_{n,n}$ corresponds to a Howell design $H_k(n,2n)$, and moreover they are equivalent to a pair of mutually orthogonal latin squares of side $n$. In the other extreme case, an $H(2n-1,2n)$ is a Room square of side $2n-1$, which corresponds to two orthogonal one-factorizations of a complete graph $K_n$. An important question related to Howell designs concerns properties of graphs which are underlying graphs of Howell designs. While for $s=2n-1$ and $s=2n-2$ these graphs are unique (the complete graph $K_{2n}$ and the cocktail party graph $K_{2n}\setminus F$, respectively, where $F$ is a one-factor), determining these graphs in general seems to be hopeless. The goal of this talk is to show that balanced complete multipartite graphs are underlying graphs of Howell designs. The main result provides almost complete solution to the existence problem of two orthogonal one-factorizations of a complete balanced multipartite graph $K_{p\times q}$. Some infinite families of $k$ mutually orthogonal one-factorizations of $K_{p\times q}$ for $k\geq 3$ will be also presented.