Department of


Seminar Calendar
for Graph Theory and Combinatorics events the year of Tuesday, January 1, 2019.

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

Tuesday, January 15, 2019

2:00 pm in 243 Altgeld Hall,Tuesday, January 15, 2019

Cut-edges and Regular Subgraphs in Odd-degree Regular Graphs

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

Abstract: Hanson, Loten, and Toft proved that every $(2r+1)$-regular graph with at most $2r$ cut-edges has a $2$-factor. We generalize this by proving for $k\le(2r+1)/3$ that every $(2r+1)$-regular graph with at most $2r-3(k-1)$ cut-edges has a $2k$-factor. The restrictions on $k$ and on the number of cut-edges are sharp. We characterize the graphs with exactly $2r-3(k-1)+1$ cut-edges but no $2k$-factor. For $k>(2r+1)/3$, there are graphs without cut-edges that have no $2k$-factor. (Joint work with Alexandr V. Kostochka, Andr\'e Raspaud, Bjarne Toft, and Dara Zirlin.)

We determine the maximum guaranteed size of a $2$-regular subgraph in a $3$-regular $n$-vertex graph. In particular, we prove that every multigraph with maximum degree $3$ and exactly $c$ cut-edges has a $2$-regular subgraph that omits at most $(3n-2m+c-1)/2$ vertices (or $0$ for $3$-regular graphs without cut-edges). The bound is sharp; we describe the extremal multigraphs. (Joint work with Ilkyoo Choi, Ringi Kim, Alexandr V. Kostochka, and Boram Park.)

Tuesday, January 22, 2019

2:00 pm in 243 Altgeld Hall,Tuesday, January 22, 2019

Ordered and convex geometric trees with linear extremal function

Alexandr Kostochka (Illinois Math)

Abstract: The extremal functions $\text{ex}_{\rightarrow}(n,F)$ and $\text{ex}_{\circ}(n,F)$ for ordered and convex geometric acyclic graphs $F$ have been extensively investigated by a number of researchers. Basic questions are to determine when $\text{ex}_{\rightarrow}(n,F)$ and $\text{ex}_{\circ}(n,F)$ are linear in $n$, the latter posed by Brass-Károlyi-Valtr in 2003. In this talk, we answer both these questions for every tree $F$.

We give a forbidden subgraph characterization for a family $\mathcal{ T}$ of ordered trees with $k$ edges, and show that $\text{ex}_{\rightarrow}(n,T) = (k - 1)n - {k \choose 2}$ for all $n \geq k + 1$ when $T \in {\mathcal T}$ and $\text{ex}_{\rightarrow}(n,T) = \Omega(n\log n)$ for $T \not\in {\mathcal T}$. We also describe the family ${\mathcal T}'$ of the convex geometric trees with linear Turán number and show that for every convex geometric tree $F\notin {\mathcal T}'$, $\text{ex}_{\circ}(n,F)= \Omega(n\log \log n)$.

This is joint work with Zoltan Füredi, Tao Jiang, Dhruv Mubayi and Jacques Verstraëte.

Tuesday, January 29, 2019

2:00 pm in 243 Altgeld Hall,Tuesday, January 29, 2019

Eigenvalues and graph factors

Suil O (Stony Brook University)

Abstract: An (even or odd) $[a,b]$-factor is a spanning subgraph $H$ such that ($d_H(v)$ is even or odd respectively, and) $a \le d_H(v) \le b$ for all $v \in V(G)$. When $a=b=k$, it is called a $k$-factor.

In this talk, we give sharp conditions for a graph to have an even $[a,b]$-factor. For a positive integer $k$, we also prove a sharp lower bound for the spectral radius in an $n$-vertex graph to have a $k$-factor. Furthermore, we give a sharp lower bound for the third largest eigenvalue in an $n$-vertex $r$-regular graph to have odd $[1,b]$-factor.

This is joint work partly with Eun-Kyung Cho, Jongyoon Hyun, Jeongrae Park, and Douglas B. West.

Tuesday, February 5, 2019

2:00 pm in 243 Altgeld Hall,Tuesday, February 5, 2019


Florian Pfender (University of Colorado Denver Math)

Abstract: A graph $H$ is a fractalizer if every graph $G$ maximizing the number of induced copies of $H$ is an iterated balanced blow-up of $H$. Fox, Hao and Lee, and independently Yuster, showed that almost every graph is a fractalizer considering random graphs. Nevertheless, no non-trivial explicit examples of fractalizers are known. We show that the cycle $C_5$ is almost a fractalizer, and conjecture that all longer cycles are fractalizers.

Tuesday, February 12, 2019

2:00 pm in 243 Altgeld Hall,Tuesday, February 12, 2019

On the number of edges in C_5-free 3-uniform hypergraphs

Dara Zirlin (Illinois Math)

Abstract: In a 3-uniform hypergraph, a Berge 5-cycle is formed by five distinct edges $e_1,\dots e_5$ and five distinct vertices $v_1,\dots, v_5$, such that $v_i,v_{i+1}\in e_i$, where indices count modulo 5.

In 2007, Bollobás and Györi gave upper bounds on the number of triangles in a $C_5$-free graph, and on the number of edges in a 3-uniform hypergraph containing no Berge 5-cycles.
We improve their second bound. This is joint work with Alexandr Kostochka.

Tuesday, February 19, 2019

2:00 pm in 243 Altgeld Hall,Tuesday, February 19, 2019

Small Doublings in Abelian Groups of Prime Power Torsion

Souktik Roy (Illinois Math)

Abstract: Let $A$ be a subset of $G$, where $G$ is a finite abelian group of torsion $r$. It was conjectured by Ruzsa that if $|A+A|\leq K|A|$, then $A$ is contained in a coset of $G$ of size at most $r^{CK}|A|$ for some constant $C$. The case $r=2$ received considerable attention in a sequence of papers, and was resolved by Green and Tao. Recently, Even-Zohar and Lovett settled the case when $r$ is a prime. In joint work with Yifan Jing (UIUC), we confirm the conjecture when $r$ is a power of prime.

Tuesday, February 26, 2019

2:00 pm in 243 Altgeld Hall,Tuesday, February 26, 2019

2-connected hypergraphs with no long cycles

Ruth Luo (Illinois Math)

Abstract: The Erdős–Gallai theorem gives an upper bound for the maximum number of edges in an $n$-vertex graph with no cycle of length $k$ or longer. Recently, many analogous results for $r$-uniform hypergraphs with no Berge cycle of length $k$ or longer have appeared. In this talk, we present a result for $2$-connected hypergraphs without long Berge cycles. For $n$ large with respect to $r$ and $k$, our bound is sharp and is significantly stronger than the bound without restrictions on connectivity. This is joint work with Zoltán Füredi and Alexandr Kostochka.

Tuesday, March 5, 2019

2:00 pm in 243 Altgeld Hall,Tuesday, March 5, 2019

Polynomial to exponential transition in hypergraph Ramsey theory

Lina Li (Illinois Math)

Abstract: Let $r_k(s, t; n)$ be the minimum $N$ such that every red/blue colorings of the edges of $K^k_N$ contains a blue $K^k_n$ or has $s$ vertices which induce at least $t$ red edges. The study of $r_k(s, t; n)$ is related to many other classical problems, such as classical Ramsey theory and Erdős–Szekeres problem.

The main problem of Erdős and Hajnal asks for the growth rate of $r_k(s, t; n)$ when $t$ changes from $1$ to $s \choose k$. In particular, they conjectured that for given $s$ and $k$, the threshold of $t$ which separates the polynomial growth rate and super polynomial growth rate can be calculated precisely by a recursive formula.

In this talk, I will present the history of this problem, and discuss the most recent progress made by Mubayi and Razborov, who resolve the above conjecture.

Tuesday, March 12, 2019

2:00 pm in 243 Altgeld Hall,Tuesday, March 12, 2019

Learning on hypergraphs: spectral theory and clustering with applications

Pan Li (Illinois ECE)

Abstract: Learning on graphs is an important problem in machine learning, computer vision, and data mining. Traditional algorithms for learning on graphs primarily take into account only low-order connectivity patterns described at the level of individual vertices and edges. However, in many applications, high-order relations among vertices are necessary to properly model a real-life problem. In contrast to the low-order cases, in-depth algorithmic and analytic studies supporting high-order relations among vertices are still lacking. To address this problem, we introduce a new mathematical model family, termed inhomogeneous hypergraphs, which captures the high-order relations among vertices in a very extensive and flexible way. Specifically, as opposed to classic hypergraphs that treats vertices within a high-order structure in a uniform manner, inhomogeneous hypergraphs allow one to model the fact that different subsets of vertices within a high-order relation may have different structural importance. We propose a series of algorithmic and analytic results for this new model, including inhomogeneous hypergraph clustering, spectral hypergraph theory, and novel applications ranging from food-web and ranking analysis to subspace segmentation. All proposed algorithms come with provable performance guarantees and are evaluated on real datasets; the results demonstrate significant performance improvements compared to classical learning algorithms.

Tuesday, March 26, 2019

2:00 pm in 243 Altgeld Hall,Tuesday, March 26, 2019

Linearity of Saturation for Berge Hypergraphs

Sean English (Ryerson University)

Abstract: For a graph $F$, we say a hypergraph $H$ is Berge-$F$ if it can be obtained from $F$ be replacing each edge of $F$ with a hyperedge containing it. We say a hypergraph is Berge-$F$-saturated if it does not contain a Berge-$F$, but adding any hyperedge creates a copy of Berge-$F$. The $k$-uniform saturation number of Berge-$F$, $\mathrm{sat}_k(n,\text{Berge-}F)$ is the fewest number of edges possible over all Berge-$F$-saturated $k$-uniform hypergraphs on $n$ vertices.

In this talk we will explore some specific saturation numbers for Berge hypergraphs. We will also see that at least for small uniformities, these numbers grow linearly with $n$, extending a classical result of Kászonyi and Tuza. Finally, we will mention many interesting open problems in this area of research.

Tuesday, April 2, 2019

2:00 pm in 243 Altgeld Hall,Tuesday, April 2, 2019

On two problems, related to additive combinatorics

Jozsef Balogh (Illinois Math)

Abstract: In the talk I will present two short results:

(a) Define $T=T(k)$ the minimal $t$ for which there is a rainbow arithmetic progression of length $k$ in every equinumerous $t$-coloring of the numbers $1,\dots, tn$ for all $n$, where equinumerous means that each color used the same number of times. Almost answering a question of Jungic, Licht (Fox), Mahdian, Nesetril and Radoicic, we almost determine the function $T$. It is a joint work with Linz.

(b) Graph-bootstrap percolation, also known as weak saturation, was introduced by Bollobas in 1968. In this process, we start with initial "infected" set of edges $E(0)$, and we infect new edges according to a predetermined rule. Given a graph $H$ and a set of previously infected edges $E(t)$ subset of $E(K_n)$, we infected a non-infected edge $e$ if it completes a new copy of $H$ in $G=([n],E(t) + e)$. A question raised by Bollobas asks for the maximum time the process can run before it stabilizes. In 2015, Bollobas, Przykucki, Riordan, and Sahasrabudhe considered this problem for the most natural case where $H$ is the $r$-vertex complete graph. They answered the question for $r > 3$ and gave a lower bound for every $r \ge 5$. In their paper, they also conjectured that the maximal running time is subquadratic for every integer $r$. In this paper we disprove their conjecture for every $r$ at least 6 and we give a better lower bound for the case that $r=5$. In the proof of the case $r=5$ we use the Behrend construction. Joint result with Kronenberg, Pokrovskiy and Szabo.

Tuesday, April 9, 2019

2:00 pm in 243 Altgeld Hall,Tuesday, April 9, 2019

Equitable colorings of infinite graphs

Anton Bernshteyn (Carnegie Mellon Math)

Abstract: A proper $k$-coloring of a finite graph $G$ is called equitable if every two color classes differ in size at most by one. In particular, if $G$ has $n$ vertices and $k$ divides $n$, then in an equitable $k$-coloring of $G$ every color class has size exactly $n/k$. There is a natural way to extend this definition to infinite graphs on probability spaces. Namely, if $G$ is a graph whose vertex set $V(G)$ is a probability space, then a proper $k$-coloring of $G$ is equitable when every color class has measure $1/k$. In this talk I will discuss extensions of some classical results about equitable colorings to this setting, including an infinite version of the Hajnal-Szemerédi theorem on equitable $k$-colorings for $k \geq \Delta(G) + 1$, and an analog of the Kostochka-Nakprasit theorem on equitable $\Delta$-colorings of graphs with small average degree. This is joint work with Clinton Conley.

Tuesday, April 16, 2019

2:00 pm in 243 Altgeld Hall,Tuesday, April 16, 2019

Monochromatic connected matchings, paths and cycles in 2-edge-colored multipartite graphs

Xujun Liu (Illinois Math)

Abstract: We solve four similar problems: For every fixed $s$ and large $n$, we describe all values of $n_1,\ldots,n_s$ such that for every $2$-edge-coloring of the complete $s$-partite graph $K_{n_1,\ldots,n_s}$ there exists a monochromatic
(i) cycle $C_{2n}$ with $2n$ vertices,
(ii) cycle $C_{\geq 2n}$ with at least $2n$ vertices,
(iii) path $P_{2n}$ with $2n$ vertices, and
(iv) path $P_{2n+1}$ with $2n+1$ vertices.

This implies a generalization of the conjecture by Gyárfás, Ruszinkó, Sárközy and Szemerédi that for every $2$-edge-coloring of the complete $3$-partite graph $K_{n,n,n}$ there is a monochromatic path $P_{2n+1}$. An important tool is our recent stability theorem on monochromatic connected matchings (A matching $M$ in $G$ is connected if all the edges of $M$ are in the same component of $G$). We will also talk about exact Ramsey-type bounds on the sizes of monochromatic connected matchings in $2$-colored multipartite graphs. Joint work with József Balogh, Alexandr Kostochka and Mikhail Lavrov.

Tuesday, April 23, 2019

2:00 pm in 243 Altgeld Hall,Tuesday, April 23, 2019

Partitions of hypergraphs under variable degeneracy constraints

Michael Stiebitz (TU Ilmenau)

Abstract: We use the concept of variable degeneracy of a hypergraph in order to unify the seemingly remote problems of determining the point partition numbers and the list chromatic number of hypergraphs. Our hypergraphs may have multiple edges, but no loops. Given a hypergraph $G$ and a sequence $f = (f_1, f_2, \dots , f_p)$ of $p \ge 1$ vertex functions $f_i : V(G) → \mathbb N_0$ such that $f_1(v) + f_2(v) + · · · + f_p(v) \ge d_G(v)$ for all $v \in V(G)$, we want to find a sequence $(G_1, G_2, \dots , G_p)$ of vertex disjoint induced subhypergraphs containing all vertices of $G$ such that each hypergraph G_i is strictly $f_i$-degenerate, that is, for every non-empty subhypergraph $G' \subseteq G_i$ there is a vertex $v \in V (G')$ such that $d_{G'}(v) < f_i(v)$. The main result says that such a sequence of hypergraphs exists if and only if $(G, f)$ is not a so-called hard pair. Hard pairs form a recursively defined family of configurations, obtained from three basic types of configurations by the operation of merging a vertex. For simple graphs this result was obtained by O. Borodin, A. V. Kostochka, and B. Toft in 2000. As a simple consequence of our result we obtain a Brooks-type result for the list chromatic number of digraphs due to A. Harautyunyan and B. Mohar. In a digraph coloring the aim is to color the vertices of a directed graph $D$ such that each color class induces an acyclic digraph of $D$, that is, a directed graph not containing any directed cycle. This coloring concept was introduced by V. Neumann-Lara in the 1980s.

Friday, June 14, 2019

2:00 pm in 243 Altgeld Hall,Friday, June 14, 2019

Decomposing graphs into edges and triangles

Bernard Lidicky (Iowa State Math)

Abstract: We prove the following 30-year old conjecture of Gyori and Tuza: the edges of every $n$-vertex graph $G$ can be decomposed into complete graphs $C_1,\ldots,C_\ell$ of orders two and three such that $|C_1|+\cdots+|C_\ell|\le (1/2+o(1))n^2$. This result implies the asymptotic version of the old result of Erdos, Goodman and Posa that asserts the existence of such a decomposition with $\ell\le n^2/4$. We also discuss removing $o(1)$ term sharpening the result and possible extensions. The talk is based on joint works with Blumenthal, Kral, Martins, Pehova, Pikhurko, Pfender, Vole.

Tuesday, August 20, 2019

2:00 pm in 343 Altgeld Hall,Tuesday, August 20, 2019

Refinements of Choice Number of Graphs

Xuding Zhu (Zheiang Normal University Math)

Abstract: In this talk, we discuss some refinements of choice number of graphs.
(1) We define a graph $G$ to be strongly fractional $r$-choosable if for any positive integer $m$, $G$ is $(\lceil rm \rceil, m)$-choosable, and define the strong fractional choice number $ch^∗_f(G)$ of $G$ to be the infimum $r$ for which G is strongly fractional $r$-choosable. The strong fractional choice number of a family $\mathcal G$ of graphs is defined to be the supremum of $ch^∗_f(G)$ for graph $G \in \mathcal G$. It is proved that the strong fractional choice number of planar graphs is at least $4+2/9$, and the strong fractional choice number of triangle free planar graphs is at least $3 + 1/17$.
(2) We say a graph $G$ is $(k + \epsilon)$-choosable if any subgraph $H$ of $G$ has a subset $X$ of vertices for which the following hold: (i) $|X| \le \epsilon|V (H)|$, (ii) for any list assignment $L$ of $G$ for which $|L(v)| = k+1$ for $v \in X$ and $|L(v)| = k$ for $v \in V (H)−X$, $H$ is $L$-colourable. It is proved that planar graphs are $(4 + 1/2)$-choosable and triangle free planar graphs are $(3 + 2/3)$-choosable.
(3) Assume $\lambda = (k_1, k_2, \dots, k_q)$ is a partition of an integer $k$. A $\lambda$-assignment of $G$ is a $k$-assignment $L$ of $G$ for which the colour set $\bigcup_{v \in V(G)} L(v)$ can be partitioned into $C_1 \cup C_2 \cup \dots \cup C_q$ such that $|L(v) \cap C_i| = k_i$ for every vertex $v$. We say $G$ is $\lambda$-choosable if $G$ is $L$-colourable for every $\lambda$-assignment $L$ of $G$. If $\lambda = \{k\}$, then $\lambda$-choosability is the same as $k$-choosability; if $\lambda = \{1,1,\dots,1\}$ then $\lambda$-choosability is the same as $k$-colourability. For other partitions $\lambda$ of $k$, $\lambda$-choosability form a complex hierachy of complexity of colourability. A recent result of Kermnitz and Voigt implies that for any partition $\lambda$ of $4$ other than $\{1,1,1,1\}$, there is a planar graph which is not $\lambda$-choosable (this is much stronger than the result that there are planar graphs that are not $4$-choosable). Some basic properties of $\lambda$-choosability and relation to some other colouring concepts will be discussed.

Tuesday, August 27, 2019

2:00 pm in 243 Altgeld Hall,Tuesday, August 27, 2019

The Alon-Tarsi number of subgraphs of a planar graph

Seog-Jin Kim (Konkuk University Math)

Abstract: This paper constructs a planar graph $G_1$ such that for any subgraph $H$ of $G_1$ with maximum degree $\Delta(H) \le 3$, $G_1-E(H)$ is not $3$-choosable, and a planar graph $G_2$ such that for any star forest $F$ in $G_2$, $G_2-E(F)$ contains a copy of $K_4$ and hence $G_2-E(F)$ is not $3$-colourable. On the other hand, we prove that every planar graph $G$ contains a forest $F$ such that the Alon-Tarsi number of $G - E(F)$ is at most $3$, and hence $G - E(F)$ is 3-paintable and 3-choosable. This is joint work with Ringi Kim and Xuding Zhu.

Tuesday, September 3, 2019

2:00 pm in 243 Altgeld Hall,Tuesday, September 3, 2019

Large Monochromatic Components in Sparse Random Hypergraphs

Sean English (Illinois Math)

Abstract: It is known, due to Gyárfás and Füredi, that for any $r$-coloring of the edges of $K_n$, there is a monochromatic component of order $(1/(r-1)+o(1))n$. Recently, Bal and DeBiasio, and independently Dudek and Prałat showed that the Erdős-Rényi random graph $\mathcal{G}(n,p)$ behaves very similarly with respect to the size of the largest monochromatic component. More precisely, it was shown that a.a.s. for any $r$-coloring of the edges of $\mathcal{G}(n,p)$ and arbitrarily small constant $\alpha>0$, there is a monochromatic component of order $(1/(r-1)-\alpha)n$, provided that the average degree goes to infinity with $n$. As before, this result is best possible.

In this talk we present a generalization of this result to hypergraphs. Specifically we show that in the $k$-uniform random hypergraph, $\mathcal{H}^{(k)}(n,p)$ a.a.s. for any $k$-coloring of the edges, there is a monochromatic component of order $(1-\alpha)n$. Furthermore, for any $k+1$ coloring, there is a monochromatic component of order $(1-\alpha)\frac{k}{k+1}n$. These results hold as long as the average degree goes to infinity.

It is also known Gyárfás, Sárközy and Szemerédi that the Ramsey number for loose cycles on $n$ vertices in $k$-uniform hypergraphs is asymptotically $\frac{2k-1}{2k-2}n$, which implies that in any $2$-coloring of $K^{(k)}_n$, for large $n$, we can find a loose cycle on about $\frac{2k-2}{2k-1}n$ vertices. We will present a generalization of this which shows that even if the host graph is $\mathcal{H}^{(k)}_{n,p}$, this result still holds a.a.s. provided that the average degree goes to infinity.

This project is joint work with Patrick Bennett, Louis Debiasio and Andrzej Dudek.

Tuesday, September 10, 2019

2:00 pm in 243 Altgeld Hall,Tuesday, September 10, 2019

The largest projective cube-free subsets of $\mathbb Z_{2^n}$

Adam Zsolt Wagner (ETH Zurich Math)

Abstract: What is the largest subset of $\mathbb Z_{2^n}$ that doesn't contain a projective $d$-cube? In the Boolean lattice, Sperner's, Erdos's, Kleitman's and Samotij's theorems state that families that do not contain many chains must have a very specific layered structure. We show that if instead of $\mathbb Z_2^n$ we work in $\mathbb Z_{2^n}$, analogous statements hold if one replaces the word $k$-chain by projective cube of dimension $2^{k-1}$. The largest $d$-cube-free subset of $\mathbb Z_{2^n}$, if $d$ is not a power of two, exhibits a much more interesting behaviour.

(Joint work with Jason Long)

Tuesday, September 17, 2019

2:00 pm in 243 Altgeld Hall,Tuesday, September 17, 2019

Connected Fair Detachments of Hypergraphs

Amin Bahmanian (ISU Math)

Abstract: Let $\mathcal G$ be a hypergraph whose edges are colored. An $(\alpha,n)$-detachment of $\mathcal G$ is a hypergraph obtained by splitting a vertex $\alpha$ into $n$ vertices, say $\alpha_1,\dots,\alpha_n$, and sharing the incident hinges and edges among the subvertices. A detachment is fair if the degree of vertices and multiplicity of edges are shared as evenly as possible among the subvertices within the whole hypergraph as well as within each color class. We find necessary and sufficient conditions under which a $k$-edge-colored hypergraph $\mathcal G$ has a fair detachment in which each color class is connected. Previously, this was not even known for the case when $\mathcal G$ is an arbitrary graph (i.e. 2-uniform hypergraph). We exhibit the usefulness of our theorem by proving a variety of new results on hypergraph decompositions, and completing partial regular combinatorial structures.

Tuesday, September 24, 2019

2:00 pm in 243 Altgeld Hall,Tuesday, September 24, 2019

Defective DP-colorings of sparse multigraphs

Fuhong Ma (Shangdong University)

Abstract: DP-coloring (also known as correspondence coloring) is a generalization of list coloring developed recently by Dvořák and Postle. We introduce and study defective DP-colorings of graphs and multigraphs with 2 colors. Each vertex $v$ of a multigraph $G$ has colors $\alpha(v)$ and $\beta(v)$ in its list. In an $(i,j)$-coloring of $G$, if $v$ is colored with $\alpha(v)$, then it can be incident to at most $i$ 'conflicting' edges, otherwise it can be incident to at most $j$ such edges. We concentrate on $(i,j)$-colorings of sparse multigraphs.

Let $f_{DP}(i,j,n)$ be the minimum number of edges that may have an $n$-vertex $(i,j)$-critical multigraph, that is, a multigraph $G$ that has no $(i,j)$-defective DP-coloring but whose every proper subgraph has such a coloring. For all $i$ and $j$, we find linear lower bounds on $f_{DP}(i,j,n)$ that are exact for infinitely many $n$.

Tuesday, October 1, 2019

2:00 pm in 243 Altgeld Hall,Tuesday, October 1, 2019

Long monochromatic paths and cycles in $2$-edge-colored graphs with large minimum degree

Mikhail Lavrov (Illinois Math)

Abstract: Our main result is a proof for sufficiently large $n$ of the conjecture by Benevides, Łuczak, Scott, Skokan and White that for every positive integer $n$ of the form $n=3t+r$ where $r \in \{0,1,2\}$ and every $n$-vertex graph $G$ with $\delta(G) \ge 3n/4$, in each $2$-edge-coloring of $G$ there exists a monochromatic cycle of length at least $2t+r$.

Our result also implies the conjecture of Schelp that for every sufficiently large $n$, every $(3n-1)$-vertex graph $G$ with minimum degree larger than $3|V(G)|/4$, in every $2$-edge-coloring of $G$, there is a monochromatic path with $2n$ vertices. Joint work with József Balogh, Alexandr Kostochka and Xujun Liu.

Tuesday, October 8, 2019

2:00 pm in 243 Altgeld Hall,Tuesday, October 8, 2019

Problems and results on $1$-cross intersecting set pair systems

Zoltán Füredi (Rényi Institute, Budapest, Hungary)

Abstract: The notion of cross intersecting set pair system of size $m$, $(\{A_i\}_{i=1}^m, \{B_i\}_{i=1}^m)$ with $A_i \cap B_i = \emptyset$ and $A_i \cap B_j \ne \emptyset$, was introduced by Bollobás and it became an important tool of extremal combinatorics. His classical result states that $m \le {{a+b} \choose a}$ if $|A_i|\le a$ and $|B_i| \le b$ for each $i$.

Our central problem is to see how this bound changes with the additional condition $|A_i \cap B_j|= 1$ for $i \ne j$. Such a system is called $1$-cross intersecting. We show that the maximum size of a $1$-cross intersecting set pair system is

  • at least $5^{n/2}$ for $n$ even, $a=b=n$,
  • equal to $(\lfloor \frac n2 \rfloor + 1)(\lceil \frac n2\rceil + 1)$ if $a=2$, $b=n \ge 4$,
  • at most $|\bigcup_{i=1}^m A_i|$,
  • asymptotically $n^2$ if $\{A_i\}$ is a linear hypergraph ($|A_i\cap A_j| \le 1$ for $i \ne j$),
  • asymptotically $\frac12 n^2$ if $\{A_i\}$, $\{B_i\}$ are both linear.

Tuesday, October 15, 2019

2:00 pm in 243 Altgeld Hall,Tuesday, October 15, 2019

Equiangular lines with a fixed angle

Zilin Jiang (MIT Math)

Abstract: An equiangular set of lines is a family of lines (through the origin) such that they are pairwise separated by the same angle. A central question in Algebraic Graph Theory is to determine the maximum cardinality of an equiangular set of lines in n-dimensional Euclidean space. In this talk, we will prove the key spectral result on the multiplicity of the second largest eigenvalue of a connected graph, and we will then connect it to the question on equiangular lines. Joint work with Jonathan Tidor, Yuan Yao, Shengtong Zhang and Yufei Zhao.

Tuesday, October 22, 2019

2:00 pm in 243 Altgeld Hall,Tuesday, October 22, 2019

River landscapes and Optimal Channel Networks

József Balogh (Illinois Math)

Abstract: We study tree structures termed Optimal Channel Networks (OCNs) that minimize the total gravitational energy loss in the system, an exact property of steady-state landscape configurations that prove dynamically accessible and strikingly similar to natural forms. Here, we show that every OCN is a so-called natural river tree, in the sense that there exists a height function such that the flow directions are always directed along steepest descent. We also study the natural river trees in an arbitrary graph in terms of forbidden sub-structures.

The talk is based on: P. Balister, J. Balogh, E. Bertuzzo, B. Bollobas, G. Caldarelli, A. Maritan, R. Mastrandrea, R. Morris, A Rinaldo: River landscapes and Optimal Channel Networks, Proceeding of the National Academy of Sciences U.S.A., 115, 6548--6553 (2018).

This paper is based on a true collaboration among mathematicians, theoretical computer scientists and physicists.

Tuesday, October 29, 2019

2:00 pm in 243 Altgeld Hall,Tuesday, October 29, 2019

A bandwidth theorem for locally dense graphs

Andrew Treglown (University of Birmingham Math)

Abstract: A fundamental topic in extremal graph theory is to find minimum degree conditions that force a spanning substructure in a graph. One of the most general results in this direction is the so-called Bandwidth Theorem of Boettcher, Schacht and Taraz. This result gives a minimum degree condition which forces a graph G to contain every spanning subgraph of bounded chromatic number, bounded degree and sublinear bandwidth. In this talk I will describe a version of the Bandwidth Theorem where now one substantially lowers the degree condition at the expense of ensuring the host graph G is "locally dense". This is joint work with Katherine Staden.

Tuesday, November 5, 2019

2:00 pm in 243 Altgeld Hall,Tuesday, November 5, 2019

Super-pancyclic hypergraphs and bipartite graphs

Dara Zirlin (Illinois Math)

Abstract: We find Dirac-type sharp sufficient conditions for a hypergraph $H$ with few edges to have a hamiltonian Berge cycle. Furthermore, these conditions yield that $H$ is super-pancyclic, i.e., for each $A \subseteq V(H)$ with $|A| \ge 3$, $H$ contains a Berge cycle with vertex set $A$. To do this, we exploit the language of bipartite graphs. In particular, we extend some results of Jackson on the existence of long cycles in bipartite graphs where the vertices in one part have high degrees, and prove his conjecture from 1981 on the topic.

This is joint work with Alexandr Kostochka and Ruth Luo.

Tuesday, November 12, 2019

2:00 pm in 243 Altgeld Hall,Tuesday, November 12, 2019

Extremal graphs without 4-cycles

Zoltán Füredi (Alfréd Rényi Institute of Mathematics and UIUC)

Abstract: Let $\text{ex}(n,C_4)$ denote the maximum number of edges of a graph on $n$ vertices which does not contain a cycle of length $4$. It is known since the 1930's (Erdos and E Klein) that $\text{ex}(n,C_4)=\Theta(n^{3/2})$, and Brown (1966) and independently Erdos, Renyi, and Sos (1966) showed that it is asymptotic to $(1/2) n^{3/2}$. The determination of the exact values seems to be hopeless, but the speaker established their conjecture and showed (1983, 1996) that $\text{ex}(q^2+q+1, C_4)= (1/2)q^2(q+1)$ for primepower $q$.

Firke, Kosek, Nash, and Williford (2013) found another infinite series of exact values ($n=q^2+q$, $q$ is a power of $2$).

In this talk we sketch the proofs and also show (in the case of $n=q^2+q+1 > 100$) that all the extremal graphs can be obtained from a polarity graph. If time permits, other related algebraic constructions are discussed.

Tuesday, November 19, 2019

2:00 pm in 243 Altgeld Hall,Tuesday, November 19, 2019

An overview of Erdős-Rothschild problems and their rainbow variants

Lina Li (Illinois Math)

Abstract: In 1974, Erdős and Rothschild conjectured that the complete bipartite graph has the maximum number of two-edge-colorings without monochromatic triangles over all n-vertex graphs. Since then, a new class of colored extremal problems has been extensively studied by many researchers on various discrete structures, such as graphs, hypergraphs, Boolean lattices and sets.

In this talk, I will first give an overview of some previous results on this topic. The second half of this talk is to explore the rainbow variants of the Erdős-Rothschild problem. With Jozsef Balogh, we confirm conjectures of Benevides, Hoppen and Sampaio, and Hoppen, Lefmann, and Odermann, and completes the characterization of the extremal graphs for the edge-colorings without rainbow triangles. Next, we study a similar question on sum-free sets, where we describe the extremal configurations for integer colorings with forbidden rainbow sums. The latter is joint work with Yangyang Cheng, Yifan Jing, Wenling Zhou and Guanghui Wang.

Tuesday, November 26, 2019

2:00 pm in 243 Altgeld Hall,Tuesday, November 26, 2019

Nonrepetitive Graph Coloring

André Kündgen (CSU San Marcus Math)

Abstract: A repetition in an edge-colored graph is a path in which the sequence of colors in the first half of the path is identical to that in the second half. In 2002 Alon, Grytczuk, Haluszczak, and Riordan showed that every $k$-ary tree has a repetition-free edge-coloring with at most $4k$ colors. We present a simple procedure for obtaining repetition-free edge-colorings of $k$-ary trees with at most $3k+1$ colors. We will also discuss some related vertex-coloring questions.

This is joint work with Tonya Talbot.

Tuesday, December 3, 2019

2:00 pm in 243 Altgeld Hall,Tuesday, December 3, 2019

Monochromatic cycles of given length in $2$-edge-colored graphs with large minimum degree

Xujun Liu (Illinois Math)

Abstract: We prove that if $n$ is sufficiently large and has the form $n=3t+r$ where $r \in \{0,1,2\}$, then for every $n$-vertex graph $G$ with $\delta(G) \ge (3n-1)/4$, in each $2$-edge-coloring of $G$, either there is a monochromatic subgraph containing cycles of every length $\{3, 4, 5, \dots, 2t+r\}$, or there is a monochromatic subgraph containing cycles of every even length $\{4, 6, 8, \dots, 2t+2\}$. This is tight and slightly sharpens for sufficiently large $n$ a conjecture by Benevides, Łuczak, Scott, Skokan and White that for every graph $G$ of order $n=3t+r$ where $r \in \{0,1,2\}$ with $\delta(G) \ge 3n/4$ and every $2$-edge-coloring of $G$, there exists a monochromatic cycle of length at least $2t+r$. Joint work with József Balogh, Alexandr Kostochka and Mikhail Lavrov.