Department of


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

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.