Department of

Mathematics


Seminar Calendar
for Graph Theory and Combinatorics Seminar events the year of Monday, April 22, 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.
      March 2019             April 2019              May 2019      
 Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa
                 1  2       1  2  3  4  5  6             1  2  3  4
  3  4  5  6  7  8  9    7  8  9 10 11 12 13    5  6  7  8  9 10 11
 10 11 12 13 14 15 16   14 15 16 17 18 19 20   12 13 14 15 16 17 18
 17 18 19 20 21 22 23   21 22 23 24 25 26 27   19 20 21 22 23 24 25
 24 25 26 27 28 29 30   28 29 30               26 27 28 29 30 31   
 31                                                                

Tuesday, January 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

Fractalizers

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.