Department of

# Mathematics

Seminar Calendar
for Graph Theory and Combinatorics Seminar events the year of Tuesday, June 30, 2020.

.
events for the
events containing

Questions regarding events or the calendar should be directed to Tori Corkery.
       May 2020              June 2020              July 2020
Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa
1  2       1  2  3  4  5  6             1  2  3  4
3  4  5  6  7  8  9    7  8  9 10 11 12 13    5  6  7  8  9 10 11
10 11 12 13 14 15 16   14 15 16 17 18 19 20   12 13 14 15 16 17 18
17 18 19 20 21 22 23   21 22 23 24 25 26 27   19 20 21 22 23 24 25
24 25 26 27 28 29 30   28 29 30               26 27 28 29 30 31
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.

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.