Department of


Seminar Calendar
for Graph Theory and Combinatorics Seminar events the year of Saturday, February 29, 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.
     January 2020          February 2020            March 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    1  2  3  4  5  6  7
  5  6  7  8  9 10 11    2  3  4  5  6  7  8    8  9 10 11 12 13 14
 12 13 14 15 16 17 18    9 10 11 12 13 14 15   15 16 17 18 19 20 21
 19 20 21 22 23 24 25   16 17 18 19 20 21 22   22 23 24 25 26 27 28
 26 27 28 29 30 31      23 24 25 26 27 28 29   29 30 31            

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.