Department of


Seminar Calendar
for Graph Theory and Combinatorics Seminar events the year of Saturday, May 23, 2020.

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.
      April 2020              May 2020              June 2020      
 Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa
           1  2  3  4                   1  2       1  2  3  4  5  6
  5  6  7  8  9 10 11    3  4  5  6  7  8  9    7  8  9 10 11 12 13
 12 13 14 15 16 17 18   10 11 12 13 14 15 16   14 15 16 17 18 19 20
 19 20 21 22 23 24 25   17 18 19 20 21 22 23   21 22 23 24 25 26 27
 26 27 28 29 30         24 25 26 27 28 29 30   28 29 30            

Tuesday, January 21, 2020

2:00 pm in 243 Altgeld Hall,Tuesday, January 21, 2020

Lichiardopol's Conjecture on Disjoint Cycles in Tournaments

Douglas B. West (Zhejiang Normal University and University of Illinois)

Abstract: In a 1981 survey on cycles in digraphs, Bermond and Thomassen conjectured that every digraph with minimum outdegree at least $2k-1$ contains $k$ disjoint cycles. In 2010, Lichiardopol conjectured a stronger property for tournaments: for positive integers $k$ and $q$ with $q\ge3$, every tournament with minimum out-degree at least $(q-1)k-1$ contains $k$ disjoint cycles of length $q$.

Bang-Jensen, Bessy, and Thomassé [2014] proved the special case of the Bermond--Thomassen Conjecture for tournaments. This implies the case $q=3$ of Lichiardopol's Conjecture. The case $q=4$ was proved in a masters thesis by S. Zhu [2019]. We give a uniform proof for $q\ge5$, thus completing the proof of Lichiardopol's Conjecture. This result is joint work with Fuhong Ma and Jin Yan of Shandong University.

Tuesday, January 28, 2020

2:00 pm in 243 Altgeld Hall,Tuesday, January 28, 2020

Ramsey upper density of infinite graphs

Ander Lamaison (Freie U. Berlin)

Abstract: Let $H$ be an infinite graph. In a two-coloring of the edges of the complete graph on the natural numbers, what is the densest monochromatic subgraph isomorphic to $H$ that we are guaranteed to find? We measure the density of a subgraph by the upper density of its vertex set. This question, in the particular case of the infinite path, was introduced by Erdős and Galvin. Following a recent result for the infinite path, we present bounds on the maximum density for other choices of $H$, including exact values for a wide class of bipartite graphs.

Tuesday, February 4, 2020

2:00 pm in 243 Altgeld Hall,Tuesday, February 4, 2020

The Game of Plates and Olives

Sean English (University of Illinois, Urbana-Champaign)

Abstract: Much can be learned about a manifold by studying the smooth functions on it. One particularly nice type of functions are Morse Functions. The game of plates and olives was formulated by Nicolaescu to study an enumeration problem related to Morse functions on the 2-sphere.

In the game of plates and olives, there are four different types of moves:
1.) add a new plate to the table,
2.) combine two plates and their olives onto one plate, removing the second plate from the table,
3.) add an olive to a plate, and
4.) remove an olive from a plate.

We will look at the original problem of enumerating Morse functions on the sphere, and also will look at the game of plates and olives when it is played by choosing a move to make at each step randomly. We will see that with high probability the number of olives grows linearly as the total number of moves goes to infinity.

This project was joint work with Andrzej Dudek and Alan Frieze.

Tuesday, February 11, 2020

2:00 pm in 243 Altgeld Hall,Tuesday, February 11, 2020

Large triangle packings and Tuza's conjecture in random graphs

Patrick Bennett (Western Michigan University)

Abstract: The triangle packing number $\nu(G)$ of a graph $G$ is the maximum size of a set of edge-disjoint triangles in $G$. Tuza conjectured that in any graph $G$ there exists a set of at most $2\nu(G)$ edges intersecting every triangle in $G$. We show that Tuza's conjecture holds in the random graph $G=G(n,m)$, when $m \le 0.2403n^{3/2}$ or $m\ge 2.1243n^{3/2}$. This is done by analyzing a greedy algorithm for finding large triangle packings in random graphs.

Tuesday, February 18, 2020

2:00 pm in 243 Altgeld Hall,Tuesday, February 18, 2020

Progress towards Nash-Williams' Conjecture on Triangle Decompositions

Michelle Delcourt (Ryerson University)

Abstract: Partitioning the edges of a graph into edge disjoint triangles forms a triangle decomposition of the graph. A famous conjecture by Nash-Williams from 1970 asserts that any sufficiently large, triangle divisible graph on $n$ vertices with minimum degree at least $0.75n$ admits a triangle decomposition. In the light of recent results, the fractional version of this problem is of central importance. A fractional triangle decomposition is an assignment of non-negative weights to each triangle in a graph such that the sum of the weights along each edge is precisely one.

We show that for any graph on $n$ vertices with minimum degree at least $0.827327n$ admits a fractional triangle decomposition. Combined with results of Barber, Kühn, Lo, and Osthus, this implies that for every sufficiently large triangle divisible graph on n vertices with minimum degree at least $0.82733n$ admits a triangle decomposition. This is a significant improvement over the previous asymptotic result of Dross showing the existence of fractional triangle decompositions of sufficiently large graphs with minimum degree more than $0.9n$. This is joint work with Luke Postle.

Tuesday, February 25, 2020

1:00 pm in 243 Altgeld Hall,Tuesday, February 25, 2020

Geometry of the Minimal Solutions of Linear Diophantine Equations

Papa A. Sissokho (Illinois State Univeristy)

Abstract: Let ${\bf a}=(a_1,\ldots,a_n)$ and ${\bf b}=(b_1,\ldots,b_m)$ be vectors with positive integer entries, and let $\mathcal{S}({\bf a},{\bf b})$ denote the set of all nonnegative solutions $({\bf x},{\bf y})$, where ${\bf x}=(x_1,\ldots,x_n)$ and ${\bf y}=(y_1,\ldots,y_m)$, of the linear Diophantine equation $x_1a_1+...+ x_na_n=y_1b_1+...+y_mb_m$. A solution is called minimal if it cannot be written as the sum of two nonzero solutions in $\mathcal{S}({\bf a},{\bf b})$. The set of all minimal solutions, denoted by $\mathcal{H}({\bf a},{\bf b})$, is called the Hilbert basis of $\mathcal{S}({\bf a},{\bf b})$. The solution ${\bf g}_{i,j}=(b_j{\bf e}_i,a_i{\bf e}_{n+j})$ of the above Diophantine equation, where ${\bf e}_k$ is the $k$th standard unit vector of $\mathbb{R}^{n+m}$, is called a generator. In this talk, we discuss a recent result which shows that every minimal solution in $\mathcal{H}({\bf a},{\bf b})$ is a convex combination of the generators and the zero-solution.

Tuesday, March 3, 2020

2:00 pm in 243 Altgeld Hall,Tuesday, March 3, 2020

The avoidance density of (k, l)-sum-free sets

Yifan Jing (University of Illinois, Urbana-Champaign)

Abstract: Let $\mathscr{M}_{(2,1)}(N)$ be the infimum of the size of the largest sum-free subset of any set of $N$ positive integers. An old conjecture in additive combinatorics asserts that there is a constant $c=c(2,1)$ and a function $\omega(N)\to\infty$ as $N\to\infty$, such that $cN+\omega(N)<\mathscr{M}_{(2,1)}(N)<(c+\varepsilon)N$ for any $\varepsilon>0$. The constant $c(2, 1)$ is recently determined by Eberhard, Green, and Manners, while the existence of $\omega(N)$ is still open. In this talk, we consider the analogue conjecture for $(k,l)$-sum-free sets. We determine the constant $c(k,l)$ for every $(k,l)$, and prove the existence of the function $\omega(N)$ for infinitely many $(k,l)$. The proof uses tools from probabilistic combinatorics, fourier analysis, and nonstandard analysis.

Tuesday, March 10, 2020

2:00 pm in 243 Altgeld Hall,Tuesday, March 10, 2020

Online DP-coloring of graphs

Sasha Kostochka (University of Illinois, Urbana-Champaign)

Abstract: It is known that the DP-chromatic number (also called correspondence chromatic number), $\chi_{DP}(G)$, and the online chromatic number (also called paintability), $\chi_{P}(G)$, of a graph $G$ are both at least the list chromatic number (also called choosability), $\chi_{\ell}(G)$, and can be significantly larger. The goal of the talk is twofold. First, we present examples of graphs $G$ with $\chi_P(G)>\chi_{DP}(G)$ (but only by $1$). Second, we introduce online DP-coloring of graphs and the online DP-chromatic number, $\chi_{DPP}(G)$. This parameter is an upper bound for both, $\chi_{P}(G)$ and $\chi_{DP}(G)$, but still has good properties of colorings: $\chi_{DPP}(G)$ is at most the degeneracy of $G$ plus $1$, a version of Brooks' Theorem holds for it, and every planar graph is online DP-colorable with $5$ colors.

This is joint work with S.-J. Kim, X. Li and X. Zhu.

Tuesday, April 14, 2020

2:00 pm in Zoom,Tuesday, April 14, 2020

On stability of triangle-free graphs

Felix Clemen (University of Illinois, Urbana-Champaign)

Abstract: In the first part of this talk we take a look at the structure of $K_{r+1}$-free graphs with number of edges slightly below the Turan number $\mathrm{ex}(n,K_{r+1})$. The Erdos-Simonovits stability theorem states that for all $\epsilon>0$ there exists $\alpha>0$ such that if $G$ is a $K_{r+1}$-free graph on $n$ vertices with $e(G) > \mathrm{ex}(n,K_{r+1}) - \alpha n^2$, then one can remove $\epsilon n^2$ edges from $G$ to obtain an $r$-partite graph. Furedi gave a short proof that one can choose $\alpha=\epsilon$. We give a bound for the relationship of $\alpha$ and $\epsilon$ which is asymptotically sharp as $\epsilon$ goes to $0$. This is joint work with Jozsef Balogh, Mikhail Lavrov, Bernard Lidicky and Florian Pfender.

In the second part of the talk we study graphs with number of edges slightly above the Turan number $\mathrm{ex}(n,K_{r+1})$. What is the minimum number of cliques of such graphs? Lovasz and Simonovits proved that an n-vertex graph with $e(G) > \mathrm{ex}(n,K_{3}) + t$ contains at least $t n/2$ triangles. Katona and Xiao considered the same problem under the additional condition that there are no $s$ vertices covering all triangles. They settled the case $t=1$ and $s=2$. Solving their conjecture, we determine the minimum number of triangles for general $s$ and $t$. Additionally, solving another conjecture of Katona and Xiao, we extend the theory for considering cliques instead of triangles. This is joint work with Jozsef Balogh.

Please E-mail for the Zoom ID and password.

Tuesday, April 21, 2020

1:00 pm in Zoom,Tuesday, April 21, 2020

The size-Ramsey number of a path

Louis DeBiasio (Miami University)

Abstract: Given a graph $H$, the size-Ramsey number of $H$ is the minimum $m$ such that there exists a graph $G$ with $m$ edges such that in every $2$-coloring of $G$, there exists a monochromatic copy of $H$. Paul Erdos offered $ \$ $100 simply to determine the correct order of magnitude of the size-Ramsey number of $P_n$, the path on $n$ vertices, and Beck solved this problem by showing that the size-Ramsey number of $P_n$ is between $2.25n$ and $900n$. (Note that a trivial lower bound is $2(n-2)$ and when one first thinks about the problem, it seems surprisingly hard to even improve the lower bound to something like $2.0001n$.) The best lower and upper bounds, after many incremental improvements, stood at $2.5n$ and $74n$, both due to recent work of Dudek and Pralat.

We improve the lower bound to $3.75n$; that is, we prove that every graph with at most $3.75n$ edges has a $2$-coloring such that there are no monochromatic $P_n$'s. We also discuss the $r$-color version of the problem.

Joint work with Deepak Bal.

Please email for the zoom ID and password.

Tuesday, April 28, 2020

1:00 pm in Zoom,Tuesday, April 28, 2020

Proof of the Core Conjecture of Hilton and Zhao

Songling Shan (Illinois State Univeristy)

Abstract: Let $G$ be a simple graph with maximum degree $\Delta$. We call $G$ overfull if $|E(G)|>\Delta \lfloor |V(G)|/2\rfloor$. The core of $G$, denoted $G_{\Delta}$, is the subgraph of $G$ induced by its vertices of degree $\Delta$. A classic result of Vizing shows that $\chi'(G)$, the chromatic index of $G$, is either $\Delta$ or $\Delta+1$. It is NP-complete to determine the chromatic index for a general graph. However, if $G$ is overfull then $\chi'(G)=\Delta+1$. Hilton and Zhao in 1996 conjectured that if $G$ is a simple connected graph with $\Delta\ge 3$ and $\Delta(G_\Delta)\le 2$, then $\chi'(G)=\Delta+1$ if and only if $G$ is overfull or $G=P^*$, where $P^*$ is obtained from the Petersen graph by deleting a vertex. This conjecture, if true, implies an easy approach for calculating $\chi'(G)$ for graphs $G$ satisfying the conditions. The progress on the conjecture has been slow: it was only confirmed for $\Delta=3,4$, respectively, in 2003 and 2017. We confirm this conjecture for all $\Delta\ge 4$.

This is joint work with Yan Cao, Guantao Chen and Guangming Jing.

Please Email Sean at for the zoom ID and password

Tuesday, May 5, 2020

2:00 pm in Zoom,Tuesday, May 5, 2020

A variant of the Erdos-Renyi random graph process

Pawel Pralat (Ryerson Unversity)

Abstract: We consider a natural variant of the Erdos-Renyi random graph process in which $k$ vertices are special and are never put into the same connected component. The model is natural and interesting on its own, but is actually inspired by the combinatorial data fusion problem that itself is connected to a number of important problems in graph theory. We will show that a phase transition occurs when the number of special vertices is roughly $n^{1/3}$, where $n$ is the number of vertices.

For the Zoom meeting ID and password please email

Tuesday, May 12, 2020

2:00 pm in Zoom,Tuesday, May 12, 2020

Lower bounds for difference bases

Anton Bernshteyn (Carnegie Mellon University)

Abstract: A difference basis with respect to $n$ is a subset $A \subseteq \mathbb{Z}$ such that $A - A \supseteq [n]$. Rédei and Rényi showed that the minimum size of a difference basis with respect to $n$ is $(c+o(1))\sqrt{n}$ for some positive constant $c$. The precise value of $c$ is not known, but some bounds are available, and I will discuss them in this talk. This is joint work with Michael Tait (Villanova University).

For the Zoom ID and password, please email Sean at

Tuesday, May 19, 2020

2:00 pm in Zoom,Tuesday, May 19, 2020

Transversal $C_k$-factors in subgraphs of the balanced blowup of $C_k$

Theodore Molla (University of South Florida)

Abstract: Call a blowup of a graph an $n$-blowup if each part has size $n$. For a subgraph $G$ of a blowup of $F$, we define the minimum partial degree of $G$ to be the smallest minimum degree over all of the bipartite subgraphs of $G$ that correspond to edges of $F$. Johannson proved that when $G$ is a spanning subgraph of the $n$-blowup of a triangle with minimum partial degree at least $2n/3 + n^{1/2}$, then G contains $n$ vertex disjoint triangles. Fischer's Conjecture, which was proved by Keevash and Mycroft in 2015, is a generalization of this result to complete graphs larger than the triangle. Another generalization, conjectured independently by Fischer and Häggkvist, is the following: If $G$ is a spanning subgraph of the $n$-blowup of $C_k$ with minimum partial degree at least $(1 + 1/k)n/2 + 1$, then $G$ contains $n$ vertex disjoint copies of $C_k$ that each intersect all of the $k$ parts. In this talk, we will discuss a proof of an asymptotic version of this conjecture.

This is joint work with Beka Ergemlidze.

Please email Sean English at SEnglish (at) Illinois (dot) edu for the Zoom ID and password.

Tuesday, May 26, 2020

2:00 pm in Zoom,Tuesday, May 26, 2020

Colorful phenomena in discrete geometry and combinatorics via topological methods

Shira Zerbib (Iowa State University)

Abstract: We will discuss two recent topological results and their applications to several different problems in discrete geometry and combinatorics involving colorful settings.

The first result is a polytopal-colorful generalization of the topological KKMS theorem due to Shapley. We apply this theorem to prove a colorful extension of the d-interval theorem of Tardos and Kaiser, as well as to provide a new proof to the colorful Caratheodory theorem due to Barany. Our theorem can be also applied to questions regarding fair-division of goods (e.g., multiple cakes) among a set of players. This is a joint work with Florian Frick.

The second result is a new topological lemma that is reminiscent of Sperner’s lemma: instead of restricting the labels that can appear on each face of the simplex, our lemma considers labelings that enjoy a certain symmetry on the boundary of the simplex. We apply this to prove that the well-known envy-free division theorem of a cake is true even if the players are not assumed to prefer non-empty pieces, whenever the number of players is prime or equal to 4. This is joint with Frederic Meunier.

Please email Sean at SEnglish (at) illinois (dot) edu for the Zoom ID and password.

Tuesday, June 2, 2020

2:00 pm in Zoom,Tuesday, June 2, 2020

Turan numbers for a $4$-uniform hypergraph

Karen Gunderson (University of Manitoba)

Abstract: For any $r\geq 2$, an $r$-uniform hypergraph $\mathcal{H}$, and integer $n$, the Turan number for $\mathcal{H}$ is the maximum number of hyperedges in any $r$-uniform hypergraph on $n$ vertices containing no copy of $\mathcal{H}$. While the Turan numbers of graphs are well-understood and exact Turan numbers are known for some classes of graphs, few exact results are known for the cases $r \geq 3$. I will present a construction, using quadratic residues, for an infinite family of hypergraphs having no copy of the $4$-uniform hypergraph on $5$ vertices with $3$ hyperedges, with the maximum number of hyperedges subject to this condition. I will also describe a connection between this construction and a `switching' operation on tournaments, with applications to finding new bounds on Turan numbers for other small hypergraphs.

Please email Sean at for the Zoom ID and password.

Tuesday, June 9, 2020

2:00 pm in Zoom,Tuesday, June 9, 2020

Packing $(1,1,2,4)$-coloring of subcubic outerplanar graphs

Xujun Liu (University of Illinois, Urbana-Champaign)

Abstract: For $1\leq s_1 \le s_2 \le \ldots \le s_k$ and a graph $G$, a packing $(s_1, s_2, \ldots, s_k)$-coloring of $G$, is a partition of $V(G)$ into sets $V_1, V_2, \ldots, V_k$ such that for each $1\leq i \leq k$ the distance between any two distinct $x,y\in V_i$ is at least $s_i + 1$. The packing chromatic number, $\chi_p(G)$, of a graph $G$ is the smallest $k$ such that $G$ has a packing $(1,2, \ldots, k)$-coloring. It is known that there are trees of maximum degree 4 and subcubic graphs $G$ with arbitrarily large $\chi_p(G)$. Recently, there was a series of papers on packing $(s_1, s_2, \ldots, s_k)$-colorings of subcubic graphs in various classes. We show that every $2$-connected subcubic outerplanar graph has a packing $(1,1,2)$-coloring and every subcubic outerplanar graph is packing $(1,1,2,4)$-colorable. Our results are sharp in the sense that there are $2$-connected subcubic outerplanar graphs that are not packing $(1,1,3)$-colorable and there are subcubic outerplanar graphs that are not packing $(1,1,2,5)$-colorable. This is joint work with Alexandr Kostochka.

Please contact Sean English at for the Zoom information.