Seminar Calendar
for Graph Theory and Combinatorics events the next 12 months of Sunday, January 1, 2017.

.
events for the
events containing

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



Tuesday, January 24, 2017

Graph Theory and Combinatorics Seminar
3:00 pm   in 241 Altgeld Hall,  Tuesday, January 24, 2017
 Del Edit Copy
Submitted by molla.
 Many $T$ copies in $H$-free subgraphs of random graphsAbstract: For two fixed graphs $T$ and $H$ let $ex(G(n,p),T,H)$ be the random variable counting the maximum number of copies of $T$ in an $H$-free subgraph of the random graph $G(n,p)$. We show that for the case $T=K_m$ and $\chi(H)>m$ the behavior of $ex(G(n,p),K_m,H)$ depends strongly on the relation between $p$ and $m_2(H)=\max_{H'\subset H, |V(H')|\geq 3}\left\{ \frac{e(H')-1}{v(H')-2} \right\}$. When $m_2(H)>m_2(K_m)$ we prove that with high probability, depending on the value of $p$, either one can keep almost all copies of $K_m$ in an $H$-free subgraph of $G(n,p)$, or it is asymptotically best to take a $\chi(H)-1$ partite subgraph of $G(n,p)$. The transition between these two behaviors occurs at $p=n^{-1/m_2(H)}$. When $m_2(H)< m_2(K_m)$, the above cases still exist, however for $\delta>0$ small at $p=n^{-1/m_2(H)+\delta}$ one can typically still keep most of the copies of $K_m$. The reason for this is that although $K_m$ has the minimum average degree among the $m$-color-critical graphs, it does not have the smallest $m_2(G)$ among such graphs. This is joint work with N. Alon and C. Shikhelman.

Tuesday, January 31, 2017

Graph Theory and Combinatorics Seminar
3:00 pm   in 241 Altgeld Hall,  Tuesday, January 31, 2017
 Del Edit Copy
Submitted by molla.
 Anton Bernshteyn (Illinois Math)DP-colorings of graphs with high chromatic numberAbstract: Let $G$ be an $n$-vertex graph with chromatic number $\chi(G)$. Ohba's conjecture (now a celebrated theorem due to Noel, Reed, and Wu) claims that whenever $\chi(G) \geq (n-1)/2$, the list chromatic number of $G$ equals $\chi(G)$. DP-coloring is a generalization of list coloring introduced recently by Dvořák and Postle. We establish an analog of Ohba's conjecture for the DP-chromatic number; namely we show that the DP-chromatic number of $G$ also equals $\chi(G)$ as long as $\chi(G)$ is sufficiently large''. In contrast to the list coloring case, large'' here means $\chi(G)\geq n-O(\sqrt{n})$, and we also show that this lower bound is best possible (up to the constant factor in front of $\sqrt{n}$). This is joint work with Alexandr Kostochka and Xuding Zhu.

Tuesday, February 7, 2017

Graph Theory and Combinatorics Seminar
3:00 pm   in 241 Altgeld Hall,  Tuesday, February 7, 2017
 Del Edit Copy
Submitted by molla.
 Ruth Luo (Illinois Math)The maximum number of cliques in graphs without long cyclesAbstract: The Erdős-Gallai Theorem states that for $k\geq 3$ every graph on $n$ vertices with more than $\frac{1}{2}(k-1)(n-1)$ edges contains a cycle of length at least $k$. Kopylov proved a strengthening of this result for 2-connected graphs with extremal examples $H_{n,k,t}$ and $H_{n,k,2}$. In this talk, we generalize the result of Kopylov to bound the number of $s$-cliques in a graph with circumference less than $k$. Furthermore, we show that the same extremal examples that maximize the number of edges also maximize the number of cliques of any fixed size. Finally, we obtain the extremal number of $s$-cliques in a graph with no path on $k$-vertices.

Tuesday, February 14, 2017

Graph Theory and Combinatorics Seminar
3:00 pm   in 241 Altgeld Hall,  Tuesday, February 14, 2017
 Del Edit Copy
Submitted by molla.
 Sarka Petrickova (Illinois Math)Families in posets minimizing the number of comparable pairsAbstract: Given a poset $P$, we say a family $\mathcal{F} \subseteq P$ is centered if it is obtained by `taking sets as close to the middle layer as possible'. A poset $P$ is said to have the centeredness property if for any $M$, amongst all families of size $M$ in $P$, centered families contain the minimum number of comparable pairs. Kleitman showed that the Boolean lattice $\{0,1\}^n$ has the centeredness property. It was conjectured by Noel, Scott, and Sudakov, and by Balogh and Wagner, that the poset $\{0,1,\ldots,k\}^n$ (where $(A_1,\dots,A_n)\le (B_1,\dots,B_n)$ if $A_i\le B_i$ for each $i\in [n]$) also has the centeredness property, provided $n$ is sufficiently large compared to $k$. We show that this conjecture is false for all $k\geq 2$ and investigate the range of $M$ for which it holds. Further, we improve a result of Noel, Scott, and Sudakov by showing that the poset of subspaces of $\mathbf{F}_q^n$ has the centeredness property. This is joint work with Jozsef Balogh and Adam Zsolt Wagner.

Tuesday, February 21, 2017

Graph Theory and Combinatorics Seminar
3:00 pm   in 241 Altgeld Hall,  Tuesday, February 21, 2017
 Del Edit Copy
Submitted by molla.
 Douglas B. West (Illinois Math and Zhejiang Normal University)Reconstruction from the deck of $k$-vertex induced subgraphsAbstract: The $k$-deck of a graph is its multiset of subgraphs induced by $k$ vertices; we ask whether the $k$-deck determines the graph. We show that a complete $r$-partite graph is determined by its $(r+1)$-deck. Letting $n=|V(G)|$, we generalize a result of Bollobás by showing that for $l=(1-o(1))n/2$, almost every graph $G$ is determined by various sets of ${l+2\choose 2}$ subgraphs with $n-l$ vertices. However, when $l=n/2$, the entire $(n-l)$-deck does not always determine whether $G$ is connected (it fails for $n$-vertex paths). We strengthen a result of Manvel by proving for each $l$ that when $n$ is sufficiently large (at least $l^{l^2}$), the $(n-l)$-deck determines whether $G$ is connected ($n\ge25$ suffices when $l=3$, and $n\le 2l$ cannot suffice). Finally, for every graph $G$ with maximum degree $2$, we determine the least $k$ such that $G$ is reconstructible from its $k$-deck, which involves extending a result of Stanley. This is joint work with Hannah Spinoza.

Tuesday, February 28, 2017

Graph Theory and Combinatorics Seminar
3:00 pm   in 241 Altgeld Hall,  Tuesday, February 28, 2017
 Del Edit Copy
Submitted by molla.
 Misha Lavrov (Carnegie Mellon University)Distance-uniform graphs with large diameterAbstract: We say that a graph is epsilon-distance-uniform if there is a value d (called the critical distance) such that, for every vertex v, all but an epsilon fraction of the other vertices are at distance exactly d from v. Random graphs are distance-uniform with logarithmic critical distance, and it was conjectured by Alon, Demaine, Hajiaghayi, and Leighton that the critical distance (equivalently, the diameter) of a distance-uniform graph must always be logarithmic. In this talk, we use a generalization of the Towers of Hanoi puzzle to construct distance-uniform graphs with a much larger diameter: for constant epsilon, as large as n^O(1/log log n). We show that this construction is more or less worst possible for sufficiently small epsilon, leaving open the possibility that for large epsilon, much worse cases exist. This is joint work with Po-Shen Loh.

Tuesday, March 7, 2017

Graph Theory and Combinatorics Seminar
3:00 pm   in 241 Altgeld Hall,  Tuesday, March 7, 2017
 Del Edit Copy
Submitted by molla.
 Gexin Yu (College of William & Mary)The strong chromatic index of graphs with maximum degree four is at most 21Abstract: A strong edge-coloring of a graph $G$ is a coloring of the edges such that every color class induces a matching in $G$. The strong chromatic index of a graph is the minimum number of colors needed in a strong edge-coloring of the graph. In 1985, Erdős and Nešetřil conjectured that every graph with maximum degree $\Delta$ has a strong edge-coloring using at most $\frac{5}{4}\Delta^2$ colors if $\Delta$ is even, and at most $\frac{5}{4}\Delta^2 - \frac{1}{2}\Delta + \frac{1}{4}$ if $\Delta$ is odd. This conjecture is widely unresolved with the only verified case being for $\Delta = 3$, due independently to Andersen as well as Horák, Qing, and Trotter. In this paper, we show that the strong chromatic index of graphs (where we allow for multiple edges) with maximum degree at most four is always at most 21. This improves a previous bound due to Cranston and moves closer to the conjectured upper bound of 20. This is joint work with Mingfang Huang and Michael Santana.

Tuesday, March 14, 2017

Graph Theory and Combinatorics Seminar
3:00 pm   in 241 Altgeld Hall,  Tuesday, March 14, 2017
 Del Edit Copy
Submitted by molla.
 Katherine Anders (The University of Texas at Tyler)Rooted forests that avoid sets of permutationsAbstract: An unordered rooted labeled forest avoids the pattern $\pi\in\mathcal{S}_n$ if the sequence obtained from the labels along the path from the root to any vertex does not contain a subsequence that is in the same relative order as $\pi$. We enumerate several classes of forests that avoid certain sets of permutations, including the set of unimodal forests, via bijections with set partitions with certain properties. This is joint work with Kassie Archer.

Tuesday, March 28, 2017

Graph Theory and Combinatorics Semianr
3:00 pm   in 241 Altgeld Hall,  Tuesday, March 28, 2017
 Del Edit Copy
Submitted by molla.
 Zoltán Furëdi (Illinois Math and Renyi Institute of Mathematics)Combinatorial geometry problems and Turán hypergraphsAbstract: 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

Graph Theory and Combinatorics Semianr
3:00 pm   in 241 Altgeld Hall,  Tuesday, April 4, 2017
 Del Edit Copy
Submitted by molla.
 Mariusz Meszka (AGH University of Science and Technology, Kraków, Poland)Orthogonal one-factorizations\\ of complete multipartite graphsAbstract: 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.

Tuesday, April 11, 2017

Graph Theory and Combinatorics Seminar
3:00 pm   in 241 Altgeld Hall,  Tuesday, April 11, 2017
 Del Edit Copy
Submitted by molla.
 Jaehoon Kim (University of Birmingham)On the number of Hamiltonian subsetsAbstract: In 1981, Komlós conjectured that among all graphs with minimum degree at least $d$, the complete graph $K_{d+1}$ minimises the number of Hamiltonian subsets, where a subset of vertices is Hamiltonian if it contains a spanning cycle. We prove this conjecture when $d$ is sufficiently large. In fact we prove a stronger result: for large $d$, any graph $G$ with average degree at least $d$ contains almost twice as many Hamiltonian subsets as $K_{d+1}$, unless $G$ is isomorphic to $K_{d+1}$ or a certain other graph which we specify. This is joint work with Hong Liu, Maryam Sharifzadeh and Katherine Staden.

Tuesday, April 18, 2017

Graph Theory and Combinatorics Seminar
3:00 pm   in 241 Altgeld Hall,  Tuesday, April 18, 2017
 Del Edit Copy
Submitted by molla.
 Kevin Ford (Illinois Math)Permutations fixing k-sets and applications to group theoryAbstract: A $k$-set of a permutation $\pi\in S_n$ is a subset $I\in [n]$ of size $k$ which is itself permuted by $\pi$. Equivalently, $I$ is a product of a subset of the cycles of $\pi$. In this talk, we discuss two problems: (1) If one chooses $r>1$ permutations at random, what is the likelihood that for some large $k$ each contains a $k$-set? This has application to the problem of invariable generation of $S_n$, and is connected with a famous old problem of Erdős: to show that almost all integers have two divisors in some dyadic interval $(y,2y]$. (2) Given $k_1, k_2, \ldots, k_m$ what is the likelihood that a random $\pi$ has a $k_1$-set, $k_2$-set, ..., $k_m$-set (all disjoint)? Such bounds are applied to the problem of estimating how many permutations $\pi \in S_n$ lie in transitive subgroups of $S_n$ other than $S_n$ or $A_n$. This is joint work with Sean Eberhard, Ben Green and Dimitrios Koukoulopoulos.

Tuesday, April 25, 2017

Graph Theory and Combinatorics Seminar
3:00 pm   in Altgeld Hall,  Tuesday, April 25, 2017
 Del Edit Copy
Submitted by molla.
 Chao Xu (Illinois Computer Science)Small $k$-certificate in hypergraphs and representing all min-cutsAbstract: For a hypergraph $H=(V,E)$, a hypergraph $H'=(V,E')$ is called a $k$-certificate of $H$ if it preserves all the cut values up to $k$. That is, $|\delta_{H'}(S)| \geq \min(|\delta_H(S)|,k)$ for all $S\subset V$. Nagamochi and Ibaraki showed there exists a $k$-certificate with $O(kn)$ edges for graphs, where $n$ is the number of vertices. A similar argument shows this extends to hypergraphs. We show a stronger result of hypergraphs: there is a $k$-certificate with size (sum of degrees) $O(kn)$, and it can be obtained by removing vertices from edges in $H$. We also devise an algorithm that finds a representation of all min-cuts in a hypergraph in the same running time as finding a single min-cut. The algorithm uses Cunningham's decomposition framework, and different generalizations of maximum adjacency ordering. This is joint work with Chandra Chekuri.

Tuesday, May 2, 2017

Graph Theory and Combinatorics
3:00 pm   in 241 Altgeld Hall,  Tuesday, May 2, 2017
 Del Edit Copy
Submitted by molla.
 Louis DeBiasio (Miami University)Infinite graph-Ramsey theoryAbstract: Ramsey's theorem guarantees a monochromatic copy of any countably infinite graph $G$ in any $r$-coloring of the edges of the complete graph $K_\mathbb{N}$. It is natural to wonder how "large" of a monochromatic copy of $G$ we can find with respect to some measure -- for instance, the (upper) density of the vertex set of $G$ in $\mathbb{N}$. Unlike finite graph-Ramsey theory, where this question has been studied extensively, the infinite version has been mostly overlooked. Erdős and Galvin proved that in every 2-coloring of $K_\mathbb{N}$, there exists a monochromatic path whose vertex set has upper density at least $2/3$, but it is not possible to do better than $8/9$. They also showed that there exists a monochromatic path $P$ such that for infinitely many $n$, the set $\{1,2,...,n\}$ contains the first $\frac{n}{3+\sqrt{3}}$ vertices of $P$, but it is not possible to do better than $2n/3$. We improve both results, in the former case achieving an upper density at least $3/4$ and in the latter case obtaining a tight bound of $2/3$. Inspired by this, we consider infinite analogs of well-known finite results on directed paths, trees (connected subgraphs), and graphs of bounded maximum degree/chromatic number. Joint work with Paul McKenney