Department of

Mathematics


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

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 SEnglish@illinois.edu.

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 SEnglish@illinois.edu 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 SEnglish@illinois.edu for the Zoom information.

Tuesday, June 16, 2020

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

Longest cycles in $3$-connected hypergraphs and bipartite graphs

Misha Lavrov (University of Illinois, Urbana-Champaign)

Abstract: Take a bipartite graph $G$ with bipartition $(X,Y)$ such that $|X|=n$ and $|Y|=m \ge n$. In general, this can't possibly be Hamiltonian, but we can still hope to find a cycle of length $2n$, covering $X$. We show that if $G$ is $3$-connected and the minimum degree in $X$ is at least $\max\{n, \frac{m+10}{4}\}$, then such a cycle always exists; this bound is best possible. In the language of hypergraph, this gives a Dirac-type condition for Hamiltonian Berge cycles in $3$-connected hypergraphs.

This is joint work with Alexandr Kostochka, Ruth Luo, and Dara Zirlin.

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

Tuesday, June 23, 2020

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

Linear cycles of consecutive lengths in linear hypergraphs

Tao Jiang (Miami University)

Abstract: A well-known result of Verstraete states that for each integer $k\geq 2$ every graph $G$ with average degree at least $8k$ contains cycles of $k$ consecutive even lengths, the shortest of which is at most twice the radius of $G$. Besides being interesting on its own, Verstraete's result also immediately implies that the Turan number $\mathrm{ex}(n, C_{2k})$ of the even cycle of length $2k$ is at most $8kn^{1+1/k}$, hence retrieving the classic theorem of Erdos and of Bondy and Simonovits with improved coefficients.

In this talk, we establish two extensions of Verstraete's result for linear cycles in linear $r$-uniform hypergraphs, where $r\geq 3$. A hypergraph is linear if every two edges intersect in at most one vertex. An $r$-uniform linear cycle $C^r_m$ is an $r$-uniform hypergraph consisting a cyclic list of edges $e_1,\dots,e_m$ such that consecutive edges intersect in one vertex and otherwise they are disjoint.

We prove that for all fixed $r\geq 3$, $k\geq 3$, there exists a constant $c_1=c_1(r)$ such that every linear $r$-uniform hypergraph $G$ with average degree $d(G)\geq c_1k$ contains linear cycles of $k$ consecutive even lengths, the shortest of which is at most $2 \frac{ \log n}{\log (d(G)/k)}$. In particular, as an immediate corollary, we retrieve the current best known upper bound on the linear Turan number of $C^r_{2k}$ with improved coefficients.

Furthermore, we show that for any fixed integers $r,k\geq 3$, there exists a constant $c_2=c_2(r)$ such that every $n$-vertex linear $r$-uniform graph with average degree $d(G)\geq c_2 k$, contains linear cycles of $k$ consecutive lengths (even and odd together), the shortest of which has length at most $6\frac{\log n}{\log (d(G)/k)} +5$. Both the degree condition and the shortest length among the cycles guaranteed are tight up to a constant factor. As a corollary it follows that there exists a constant $c_3=c_3(r)$ such that every $r$-uniform linear hypergraph with average degree at least $c_3$ contains an even cycle and an odd cycle of lengths at most $O(\log n)$, which is interesting on its own.

This is joint work with Jie Ma and Liana Yepremyan.

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

Tuesday, June 30, 2020

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

Variations on twins in permutations

Andrzej Dudek (Western Michigan University)

Abstract: Let $\pi$ be a permutation of the set $[n]=\{1,2,\dots, n\}$. Two disjoint order-isomorphic subsequences of $\pi$ are called twins. How long twins are contained in every permutation? The well known Erdos-Szekeres theorem implies that there is always a pair of twins of length $\Omega(\sqrt{n})$. On the other hand, by a simple probabilistic argument Gawron proved that for every $n\geq 1$ there exist permutations with no twins of length greater than $O(n^{2/3})$. His conjecture states that the latter bound is the correct size of the longest twins guaranteed in every permutation. In this talk we show that asymptotically almost surely a random permutation contains twins of length at least $\Omega(n^{2/3})$, which supports this conjecture. (This was also proved recently by Bukh and Rudenko.) We also discuss several variants of the problem with diverse restrictions imposed on the twins.

This is a joint work with Jaroslaw Grytczuk and Andrzej Rucinski.

For the Zoom ID, please email Sean at SEnglish (at) illinois (dot) edu

Tuesday, July 7, 2020

2:00 pm in Zoom,Tuesday, July 7, 2020

A survey of Berge-Turan hypergraph problems

Cory Palmer (University of Montana)

Abstract: For a graph $F$, we say that a hypergraph $\mathcal{H}$ is a Berge-$F$ if there is an injection $f: V(F) \rightarrow V(\mathcal{H})$ and bijection $f':E(F)\rightarrow E(\mathcal{H})$ such that for every edge $uv\in E(F)$ we have $\{f(u),f(v)\}\subseteq f'(uv)$. Alternatively, $\mathcal{H}$ is Berge-$F$ if we can embed a distinct graph edge into each hyperedge of $\mathcal{H}$ to obtain a copy of $F$. Note that for a fixed $F$ there are many different hypergraphs that are a Berge-$F$ and a fixed hypergraph $\mathcal{H}$ can be a Berge-$F$ for more than one graph $F$.

A hypergraph is Berge-$F$-free if it contains no subhypergraph isomorphic to any Berge-$F$. The maximum number of edges in an Berge-$F$-free $n$-vertex $r$-graph is denoted $\mathrm{ex}_r(n,\textrm{Berge-}F)$. Observe that when $r=2$, then a Berge-$F$ is simply the graph $F$ and then we are investigating the classical Turan function $\mathrm{ex}(n,F)$.

Early work on $\mathrm{ex}_r(n,\textrm{Berge-}F)$ focused on the case when $F$ is a path or a cycle. Results of Gyori, Katona, and Lemons and Davoodi, Gyori, Methuku and Tompkins establish an analogue of the Erdos-Gallai theorem for Berge paths. Gyori and Lemons proved $\mathrm{ex}_r(n,\textrm{Berge-}C_{2k}) = O(n^{1+1/k})$ for $r \geq 3$. This matches the order of magnitude of the bound found in the graph case. They prove the same upper bound for $\textrm{Berge-}C_{2k+1}$-free hypergraphs which is significantly different from the graph case.

In this talk we will survey results on the function $\mathrm{ex}_r(n,\textrm{Berge-}F)$ for various graphs $F$. We will also discuss the connection to other extremal problems and give a number of interesting open problems.

Please contact Sean at SEnglish (at) illinois (dot) edu for the Zoom information.

Tuesday, July 14, 2020

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

On the graph homomorphism density functional

Alexander Sidorenko

Abstract: Let $H$ be a graph with vertices $1,2,\ldots,n$ and edge-set $E$. We associate with it a functional that acts on bounded measurable (symmetric) functions $F: \: [0,1]^2 \to \mathbb{R}$, namely $$ t_H(F) \; = \; \int_{[0,1]^n} \prod_{\{i,j\} \in E} F(x_i,x_j) \: dx_1 dx_2 \cdots dx_n \; . $$ This notion arises from counting copies of $H$ in a large graph $F$.

We will review results and open problems in such areas as
Majorization ($H$ majorizes $G$ when $t_H(F) \geq t_G(F)$ for all $F$),
Positivity of $t_H$.
Convexity of $t_H$.

Please contact Sean English at SEnglish (at) illinois (dot) edu for the Zoom ID.

Tuesday, July 21, 2020

2:00 pm in Zoom,Tuesday, July 21, 2020

Vertex Partitions into an Independent Set and a Forest with Each Component Small

Matt Yancey

Abstract: For $b < 2$, we give optimal sparsity conditions for a graph to be partitionable into two subgraphs, the first one is an independent set and the second has maximum average degree at most $b$. This is joint work with Daniel Cranston.

Please contact Sean English at SEnglish (at) illinois (dot) edu for the Zoom ID.

Tuesday, July 28, 2020

2:00 pm in Zoom,Tuesday, July 28, 2020

11/4-colorability of subcubic triangle-free graphs

Bernard Lidicky (Iowa State University)

Abstract: We prove that every connected subcubic triangle-free graph except for two exceptional graphs on $14$ vertices has fractional chromatic number at most $11/4$. This is a joint work with Zdenek Dvorak and Luke Postle.

Please contact Sean English at SEnglish (at) illinois (dot) edu for the Zoom ID.

Tuesday, August 4, 2020

2:00 pm in Zoom,Tuesday, August 4, 2020

The size-Ramsey number of powers of bounded degree trees

Taisa Martins (Universidade Federal Fluminense)

Abstract: Given a positive integer $s$, the $s$-colour size-Ramsey number of a graph $H$ is the smallest integer $m$ such that there exists a graph $G$ with $m$ edges where in any $s$-colouring of $E(G)$ there is a monochromatic copy of $H$. We prove that, for any positive integers $k$ and $s$, the $s$-colour size-Ramsey number of the $k$th power of any $n$-vertex tree is linear on $n$.

This is a joint work with S. Berger, Y. Kohayakawa, G. S. Maesaka, W. Mendonca, G. O. Mota and O. Parczyk.

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

Tuesday, August 11, 2020

2:00 pm in Zoom,Tuesday, August 11, 2020

New Upper Bounds on Generalized Ramsey Numbers

Emily Heath (University of Illinois, Urbana-Champaign)

Abstract: A $(p,q)$-coloring of a graph $G$ is an edge-coloring of $G$ in which each $p$-clique contains edges of at least $q$ distinct colors. We are interested in the function $f(n,p,q)$, first introduced by Erdos and Shelah, which is the minimum number of colors needed for a $(p,q)$-coloring of the complete graph $K_n$. The best-known general upper bound on $f(n,p,q)$ was given by Erdos and Gyarfas in 1997 using a probabilistic argument. Since then, improved bounds in the case where $p=q$ have been obtained only for $p = 4$ and $p = 5$. In this talk, I will introduce a general strategy for finding new constructive upper bounds and explain how to apply this technique to obtain improved bounds for $p=6$ and $p=8$.

This is joint work with Alex Cameron.

Please email Sean English at SEnglish (at) illinois (dot) edu for Zoom details.

Tuesday, August 18, 2020

2:00 pm in Zoom,Tuesday, August 18, 2020

The Turan number of even linear cycles in random hypergraphs

Liana Yepremyan (University of Illinois, Chicago)

Abstract: For two $r$-uniform hypergraphs $G$ and $H$ the Turan number $\mathrm{ex}(G, H)$ is the maximum number of edges in an $H$-free subgraph of $G$. We study the typical value of $\mathrm{ex}(G, H)$ when $G=G_{n,p}^{(r)}$, the Erdos-Renyi random $r$-uniform hypergraph for $r\geq 3$ and $H=C_{2\ell}^{(r)}$, the $r$-uniform linear cycle of length $2\ell$. The case of graphs ($r=2$) is a longstanding open problem that was studied by many researchers.

We determine $\mathrm{ex}(G_{n,p}^{(r)}, C_{2\ell}^{(r)})$ up to polylogarithmic factors for all but a small interval of values of $p=p(n)$ whose length vanishes as $\ell\rightarrow\infty$. Our main technical contribution is a balanced supersaturation result for linear even cycles which substantially improves previous results of Ferber, Samotij and Mckinley and Balogh, Narayanan and Skokan. This is joint work with Dhruv Mubayi.

Please contact Sean English at SEnglish (at) illinois (dot) edu for Zoom details.

Tuesday, August 25, 2020

2:00 pm in Zoom,Tuesday, August 25, 2020

Binary scalar products

Andrey Kupavskii

Abstract: Let $A,B$ be two families of vectors in $R^d$ that both span it and such that $ < a, b> $ is either $0$ or $1$ for any $a, b$ from $A$ and $B$, respectively. We show that $|A| |B| \le (d+1) 2^d$. This allows us to settle a conjecture by Bohn, Faenza, Fiorini, Fisikopoulos, Macchia, and Pashkovich (2015) concerning $2$-level polytopes (polytopes such that for every facet-defining hyperplane $H$ there is its translate $H'$ such that $H$ together with $H'$ cover all vertices). The authors conjectured that for every $d$-dimensional $2$-level polytope $P$ the product of the number of vertices of $P$ and the number of facets of $P$ is at most $d 2^{d+1}$, which we show to be true. Joint work with Stefan Weltge.

Please contact Sean English at SEnglish (at) illinios (dot) edu for the Zoom information.

Tuesday, September 1, 2020

2:00 pm in Zoom,Tuesday, September 1, 2020

Splits with Forbidden Graphs

Ryan R. Martin (Iowa State University)

Abstract: In this talk, we fix a graph $H$ and ask into how many vertices each vertex of a clique of size $n$ can be "split" such that the resulting graph is $H$-free. Formally: A graph is an $(n,k)$-graph if its vertex set is a pairwise disjoint union of $n$ parts of size at most $k$, such that there is an edge between any two distinct parts. Let $$ f(n,H) = \min \{k \in \mathbb N : \mbox{there is an $(n,k)$-graph $G$ such that $H\not\subseteq G$}\} . $$ Barbanera and Ueckerdt observed that $f(n, H)=2$ for any graph $H$ that is not bipartite. If a graph $H$ is bipartite and has a well-defined Turan exponent, i.e., ${\rm ex}(n, H) = \Theta(n^r)$ for some $r$, we show that $\Omega (n^{2/r-1}) = f(n, H) = O (n^{2/r -1} \log ^{1/r} n)$. We extend this result to all bipartite graphs for which upper and a lower Turan exponents do not differ by much. In addition, we prove that $f(n, K_{2,t}) =\Theta(n^{1/3})$ for any fixed integer $t\geq 2$.

This is joint work with Maria Axenovich, Karlsruhe Institute of Technology.

For the Zoom ID, please contact Sean at SEnglish (at) illinois (dot) edu.

Tuesday, September 8, 2020

2:00 pm in Zoom,Tuesday, September 8, 2020

Extensions of Mantel’s Theorem

Jozsef Balogh (UIUC)

Abstract: Mantel’s theorem is a basic classical theorem of extremal graph theory. There are many different extensions and generalizations investigated and many open questions remained. I will talk about four recent results, including `stability’ and `supersaturation’ properties. The results are partly joined with Clemen, Katona, Lavrov, Lidicky, Linz, Pfender and Tuza.

Tuesday, September 15, 2020

2:00 pm in Zoom,Tuesday, September 15, 2020

Dirac-type theorems for random hypergraphs

Asaf Ferber (Univeristy of California - Irvine)

Abstract: For positive integers $d < k$ and $n$ divisible by $k$, let $m_{d}\left(k,n\right)$ be the minimum $d$-degree ensuring the existence of a perfect matching in a $k$-uniform hypergraph. In the graph case (where $k=2$), a classical theorem of Dirac says that $m_{1}\left(2,n\right)=\lceil n/2 \rceil$. However, in general, our understanding of the values of $m_{d}\left(k,n\right)$ is still very limited, and it is an active topic of research to determine or approximate these values. In this talk we discuss a ``transference'' theorem for Dirac-type results relative to random hypergraphs. Specifically, for any $d< k$, and any "not too small" $p$, we prove that a random $k$-uniform hypergraph $G$ with $n$ vertices and edge probability $p$ typically has the property that every spanning subgraph of $G$ with minimum $d$-degree at least $\left(1+o(1)\right)m_{d}\left(k,n\right)p$ has a perfect matching. Observe that this result holds even in cases that $m_{d}\left(k,n\right)$ is still unknown.

Joint work with Matthew Kwan.

Please contact Sean at SEnglish (at) illinois (dot) edu for the Zoom ID.

Tuesday, September 22, 2020

2:00 pm in Zoom,Tuesday, September 22, 2020

Tilings in vertex ordered graphs

Lina Li (University of Waterloo)

Abstract: Over recent years, there has been much interest in both Turan and Ramsey properties of vertex ordered graphs. In this talk, we initiate the study of embedding spanning structures into vertex ordered graphs. In particular, we introduce a general framework for approaching the problem of determining the minimum degree threshold for forcing a perfect $H$-tiling in an ordered graph. (In the unordered graph setting, this problem was resolved by Kuhn and Osthus in 2009.) We use our general framework to resolve the perfect $H$-tiling problem for all ordered graphs $H$ of interval chromatic number $2$. Already in this restricted setting the class of extremal examples is richer than in the unordered graph problem. This is joint work with Jozsef Balogh and Andrew Treglown.

Please contact Sean at SEnglish (at) illinois (dot) edu for the Zoom information.

Tuesday, September 29, 2020

2:00 pm in Zoom,Tuesday, September 29, 2020

Ramsey graphs and anti-concentration

Matthew Kwan (Stanford University)

Abstract: Anti-concentration inequalities provide limits on the extent to which random variables can be concentrated: for example, they commonly give uniform upper bounds on the probability that a random variable takes any particular value. In this talk I'll discuss some of the many connections between anti-concentration and combinatorics, initially focusing on applications to Ramsey graphs but also touching on a few other topics such as the polynomial Littlewood-Offord problem and permanents of random matrices.

Please Email Sean at SEnglish (at) illinois (dot) edu for Zoom information.

Tuesday, October 6, 2020

2:00 pm in Zoom,Tuesday, October 6, 2020

Subgraphs of large connectivity and chromatic number

Bhargav Narayanan (Rutgers University)

Abstract: Resolving a problem raised by Norin, we show that for each $k\in \mathbb{N}$, there exists an $f(k)\leq 7k$ such that every graph $G$ with chromatic number at least $f(k)+1$ contains a subgraph $H$ with both connectivity and chromatic number at least $k$. This result is best-possible up to multiplicative constants, and sharpens earlier results of Alon-Kleitman-Thomassen-Saks-Seymour from 1987 showing that $f(k)=O(k^3)$, and of Chudnovsky-Penev-Scott-Trotignon from 2013 showing that $f(k)=O(k^2)$.

For Zoom information please email Sean at SEnglish (at) illinois (dot) edu

Tuesday, October 13, 2020

2:00 pm in Zoom,Tuesday, October 13, 2020

Asymptotic Structure for the Clique Density Theorem

Jaehoon Kim (KAIST)

Abstract: The famous Erdos-Rademacher problem asks for the smallest number of $r$-cliques in a graph with the given number of vertices and edges. Despite decades of active attempts, the asymptotic value of this extremal function for all $r$ was determined only recently by Reiher. Here we describe the asymptotic structure of all almost extremal graphs. This task for $r=3$ was previously accomplished by Pikhurko and Razborov. This is joint work with Hong Liu, Oleg Pikhurko and Maryam Sharifzadeh.

For Zoom information, please contact Sean at SEnglish (at) illinois (dot) edu.

Tuesday, October 20, 2020

1:00 pm in Zoom,Tuesday, October 20, 2020

Ordered paths and the Erdős–Szekeres theorem

Misha Lavrov (Kennesaw State University)

Abstract: This talk is about several Ramsey-type problems on ordered graphs motivated by the Erdos–Szekeres theorem. This theorem guarantees that any sequence of $rs+1$ distinct numbers has an increasing subsequence of length $r+1$ or a decreasing subsequence of length $s+1$. In another, stronger formulation: any red-blue coloring of an ordered complete graph on $rs+1$ vertices, there is a red ordered path of length $r$ or a blue ordered path of length $s$.

Our main result characterizes all ordered graphs on $rs+1$ vertices for which the same conclusion holds. We also apply our techniques to prove bounds on the online coloring number (for any number of colors). In the monotone subsequence formulation, the online problem is a natural algorithmic question: how many comparisons are necessary to find a monotone subsequence guaranteed by the Erdos–Szekeres theorem?

These results are joint work with Jozsef Balogh, Felix Clemen, and Emily Heath.

Please contact Sean at SEnglish (at) illinois (dot) edu for Zoom information.

Tuesday, October 27, 2020

2:00 pm in Zoom,Tuesday, October 27, 2020

Universality of random polynomials

Oanh Nguyen (UIUC)

Abstract: Consider polynomials whose coefficients are 1 or -1. How many real roots do such polynomials typically have? This is one of the basic questions that we study in the field of random polynomials. In this talk, we will discuss the history and recent progress in the field. We will also discuss several current lines of research and intriguing open problems.

Contact Sean at SEnglish (at) illinois (dot) edu for Zoom information.

Tuesday, November 3, 2020

2:00 pm in Zoom,Tuesday, November 3, 2020

The threshold for the square of a Hamilton cycle

Jinyoung Park (Institute for )

Abstract: We will talk about a recent result of Jeff Kahn, Bhargav Narayanan, and myself stating that the threshold for the random graph $G(n,p)$ to contain the square of a Hamilton cycle is $1/\sqrt{n}$, resolving a conjecture of Kühn and Osthus from 2012. For context, we will first spend some time discussing a recent result of Keith Frankston and the aforementioned three authors on a conjecture of Talagrand (a fractional version of Kahn-Kalai "expectation-threshold conjecture").

For Zoom information, please contact Sean at SEnglish (at) illinois (dot) edu

Tuesday, November 10, 2020

2:00 pm in Zoom,Tuesday, November 10, 2020

Stability from symmetrisation arguments

Oleg Pikhurko (University of Warwick)

Abstract: We present a sufficient condition for the stability property of extremal graph problems that can be solved via Zykov's symmetrisation. Our criterion is stated in terms of a limit version of the problem. We present some of its application to the inducibility problem where one maximises the number of induced copies of a given complete partite graph $F$ in an $n$-vertex graph.

This is joint work with Hong Liu, Maryam Sharifzadeh and Katherine Staden.

Please contact Sean at SEnglish (at) illinois (dot) edu for Zoom information.

Tuesday, November 17, 2020

2:00 pm in Zoom,Tuesday, November 17, 2020

Further progress towards Hadwiger's conjecture

Luke Postle (University of Waterloo)

Abstract: Hadwiger conjectured that every graph with no $K_t$ minor is $(t-1)$-colorable for every $t\ge 1$. In the 1980s, Kostochka and Thomason independently proved that every graph with no $K_t$ minor has average degree $O(t\sqrt{\log t})$ and hence is $O(t\sqrt{\log t})$-colorable. Recently, Norin, Song and I showed that every graph with no $K_t$ minor is $O(t(\log t)^{\beta})$-colorable for every $\beta > 1/4$, making the first improvement on the order of magnitude of the $O(t\sqrt{\log t})$ bound. Here we show that every graph with no $K_t$ minor is $O(t (\log t)^{\beta})$-colorable for every $\beta > 0$; more specifically, they are $O(t (\log \log t)^{6})$-colorable.

For Zoom information please contact Sean at SEnglish (at) illinois (dot) edu