Department of

# Mathematics

Seminar Calendar
for Graph Theory and Combinatorics Seminar events the year of Tuesday, February 19, 2019.

.
events for the
events containing

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.