Department of

Mathematics


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

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.