Department of

# Mathematics

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

#### 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.