Department of

# Mathematics

Seminar Calendar
for Graph Theory and Combinatorics seminar events the year of Monday, October 18, 2021.

.
events for the
events containing

Questions regarding events or the calendar should be directed to Tori Corkery.
    September 2021          October 2021          November 2021
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                   1  2       1  2  3  4  5  6
5  6  7  8  9 10 11    3  4  5  6  7  8  9    7  8  9 10 11 12 13
12 13 14 15 16 17 18   10 11 12 13 14 15 16   14 15 16 17 18 19 20
19 20 21 22 23 24 25   17 18 19 20 21 22 23   21 22 23 24 25 26 27
26 27 28 29 30         24 25 26 27 28 29 30   28 29 30
31


Tuesday, January 26, 2021

2:00 pm in Zoom,Tuesday, January 26, 2021

#### Coding Theory and Sidon Sequences

###### Zoltan Furedi (Renyi Institute for Mathematics)

Abstract: A sequence ${a_1, a_2,\dots, a_k}$ of integers is called a $B_2$ sequence if all the sums $a_i + a_j$, $1 \leq i \leq j \leq k$, are different. Let $F_2(n)$ be the maximum number of elements that can be selected from the set ${1,2,\dots,n}$ so as to form a $B_2$ sequence. Among others we give a new elementary proof for the result of Erdos and Turan (1941) that $F_2(n)= \sqrt{n} + O(n^{1/4})$.

Tuesday, February 2, 2021

2:00 pm in Zoom,Tuesday, February 2, 2021

#### Acyclic graphs with at least 2L + 1 vertices are L-recognizable

###### Dara Zirlin (UIUC)

Abstract: The $(n-L)$-deck of an $n$-vertex graph is the multiset of subgraphs obtained from it by deleting $L$ vertices. A family of $n$-vertex graphs is $L$-recognizable if every graph having the same $(n-L)$-deck as a graph in the family is also in the family. We prove that the family of $n$-vertex graphs having no cycles is $L$-recognizable when $n\geq 2L+1$ (except when $(n,L)=(5,2)$). It is already known that this fails when $n=2L$ and when $(n,L)=(5,2)$.

This is joint work with Alexandr V. Kostochka, Mina Nahvi, and Douglas B. West.

Tuesday, February 9, 2021

2:00 pm in Zoom,Tuesday, February 9, 2021

#### Maximum Number of Almost Similar Triangles in the Plane

###### Felix Clemen (UIUC)

Abstract: A triangle $T'$ is $\epsilon$-similar to another triangle $T$ if their angles pairwise differ by at most $\epsilon$. Given a triangle $T$, $\epsilon>0$ and a natural number $n$, Bárány and Füredi asked to determine the maximum number of triangles being $\epsilon$-similar to $T$ in a planar point set of size $n$. We determine this quantity for almost all triangles $T$ and sufficiently small $\epsilon$. Exploring connections to hypergraph Turán problems, we use flag algebras and stability techniques for the proof. This is joint work with József Balogh and Bernard Lidický.

Tuesday, February 16, 2021

2:00 pm in Zoom,Tuesday, February 16, 2021

#### A proof of the Erdős–Faber–Lovász conjecture

###### Abhishek Methuku (University of Birmingham)

Abstract: The celebrated Erdős–Faber–Lovász conjecture (posed in 1972) states that the chromatic index of any linear hypergraph on $n$ vertices is at most $n$. In this talk, I will sketch a proof of this conjecture for every large n.

Joint work with D. Kang, T. Kelly, D. Kühn and D. Osthus.

Tuesday, February 23, 2021

2:00 pm in Zoom,Tuesday, February 23, 2021

#### The Feasible Region of Hypergraphs

###### Dhruv Mubayi (University of Illinois, Chicago)

Abstract: Many extremal hypergraph problems seek to maximize the number of edges subject to some local constraints. We aim to gain a more detailed understanding of such problems by studying the maximum subject to an additional global constraint, namely the size of the shadow. Put differently, we seek the pairs $(x,y)$ in the unit square such that there are $F$-free hypergraphs whose shadow density approaches $x$ and edge density approaches $y$. I will give some general results about the shape of this "feasible region" and also extend and improve some classical Turan-type results for particular choices of $F$. This is joint work with Xizhi Liu.

For Zoom information, please email Sean at SEnglish (at) illinois (dot) edu.

Tuesday, March 2, 2021

2:00 pm in Zoom,Tuesday, March 2, 2021

#### Sparse random graphs with overlapping community structure

###### Sam Petti (Harvard University)

Abstract: In this talk we introduce two different random graph models that produce sparse graphs with overlapping community structure and discuss community detection in each context. The Random Overlapping Community (ROC) model produces a sparse graph by constructing many Erdos Renyi random graphs (communities) on small randomly selected subsets of vertices. By varying the size and density of these communities, ROC graphs can be tuned to exhibit a wide range normalized of closed walk count vectors, including those of hypercubes. This is joint work with Santosh Vempala. In the second half of the talk, we introduce the Community Configuration Model (CCM), a variant of the configuration model in which half-edges are assigned colors and pair according to a matching rule on the colors. The model is a generalization of models in the statistical physics literature and is a natural finite analog for classes of graphexes. We describe a hypothesis testing algorithm that determines whether a graph came from a community configuration model or a traditional configuration model. This is joint work with Christian Borgs, Jennifer Chayes, Souvik Dhara, and Subhabrata Sen.

Tuesday, March 9, 2021

2:00 pm in Zoom,Tuesday, March 9, 2021

#### Ramsey numbers of Sparse Digraphs

###### Xiaoyu He (Stanford University)

Abstract: The Ramsey number $r(H)$ of a digraph $H$ is the minimum $N$ such that every $N$-vertex tournament contains $H$ as a subgraph. Note that $r(H)$ only exists if $H$ has no oriented cycle, so we will assume H is acyclic. In 1934, Rédei showed that every tournament has a Hamiltonian path, which implies $r(H)=n$ when $H$ is the oriented path on $n$ vertices. For which other $n$-vertex digraphs $H$ is it true that $r(H) = O(n)$?

A famous result of Lee, proving a conjecture of Burr and Erdős, says that any sparse undirected graph has Ramsey number linear in $n$. It is natural to ask whether the analogous statement also holds for digraphs, and surprisingly we show that it is false. For any $C > 1$, we construct a family of bounded-degree digraphs $H$ with $r(H) > n^C$. In the other direction, we prove linear and nearly-linear upper bounds for $r(H)$ for several natural families of bounded-degree digraphs, including random digraphs and digraphs of bounded height.

Joint work with Jacob Fox and Yuval Wigderson.

Tuesday, March 16, 2021

2:00 pm in Zoom,Tuesday, March 16, 2021

#### Expressing graphs as symmetric differences of cliques of the complete graph

###### Puck Romback (University of Vermont)

Abstract: Any finite simple graph $G = (V,E)$ can be represented by a collection $\mathcal{C}$ of subsets of $V$ such that $uv\in E$ if and only if $u$ and $v$ appear together in an odd number of sets in $\mathcal{C}$. We are interested in the minimum cardinality of such a collection. In this talk, we will discuss properties of this invariant and its close connection to the minimum rank problem. This talk will be accessible to students. Joint work with Calum Buchanan and Christopher Purcell.

Tuesday, March 23, 2021

2:00 pm in Zoom,Tuesday, March 23, 2021

#### Extremal results for convex geometric hypergraphs

###### Jacques Verstraete (University of California, San Diego)

Abstract: A convex geometric hypergraph or cgh is a hypergraph whose vertex set comprises the vertices of a convex polygon in the plane. The extremal problem consists in determining, given an $r$-uniform cgh $F$, the maximum number of edges $\mbox{ex}(n,F)$ in an $r$-uniform cgh on $n$ vertices that does not contain $F$. In the case of graphs, this problem has a rich history with applications to a variety of problems in combinatorial geometry. In this talk, we survey some of the known results for convex geometric graphs, and determine tight bounds for the extremal function for most configurations consisting of a pair of triangles, using a variety of different methods. For instance, we show that the maximum number of triangles that can be formed amongst $n \geq 3$ points in the plane so that any two of the triangles share an interior point is $n(n - 1)(n + 1)/24$ if $n$ is odd and $n(n - 2)(n + 2)/24$ if $n$ is even. Our results generalize old work of Kupitz, Perles, Capoyleas-Pach, Brass, Brass-Karolyi-Valtr and recent work of Aronov-Dujmovic-Morin-Ooms-da Silveira, and answer recent questions of Frankl, Holmsen and Kupavskii.

Joint work with Z. Furedi, T. Jiang, A. Kostochka, D. Mubayi and J. O'Neill.

Tuesday, March 30, 2021

2:00 pm in Zoom,Tuesday, March 30, 2021

#### Lower Bounds for Generalized Ramsey Numbers Through Color Energy Graphs

###### Sean English (UIUC)

Abstract: Let the generalized Ramsey number $f(n,p,q)$ denote the least integer $c$ such that $K_n$ can be edge-colored with $c$ colors such that every set of $p$ vertices spans a clique with at least $q$ colors. in this talk, we will discuss the method of color energy graphs, which borrows some ideas from the concept of additive energy used in additive combinatorics to find new lower bounds on generalized Ramsey numbers, and the connections between generalized Ramsey numbers and other interesting problems in extremal combinatorics.

Joint work with Jozsef Balogh, Emily Heath and Robert A. Krueger.

Tuesday, April 6, 2021

2:00 pm in Zoom,Tuesday, April 6, 2021

#### Size of Sidon sets revisited

###### Jozsef Balogh (UIUC)

Abstract: Earlier in this semester, Zoltan Furedi gave a talk, where he presented a proof for the best known upper bound on sizes of Sidon subsets of $\{1,\dots,n\}$. In this talk we repeat his proof, and explore the differences from other proofs of the same bound.

The talk is based on discussions with Zoltan Furedi and Souktik Roy.

Tuesday, April 13, 2021

2:00 pm in Zoom,Tuesday, April 13, 2021

#### Hexagon-Free Planar Graphs

###### Ervin Gyori (Renyi Institute for Mathematics)

Abstract: In this talk, we concentrate on determining the maximum number of edges in a hexagon-free planar graphs and we would like to show the nature of these problems (difficulties, necessary results and conjectures). Let $\mathrm{ex}_\mathcal{P}(n, H)$ denote the maximum number of edges in an $n$-vertex planar graph which does not contain $H$ as a subgraph. Dowden obtained exact results for $\mathrm{ex}_\mathcal{P}(n, C_4)$ and $\mathrm{ex}_\mathcal{P}(n, C_5)$, but the case of longer cycles remained open. Later on, Y. Lan, et al. proved that $\mathrm{ex}_\mathcal{P}(n, C_6)\leq \frac{18(n−2)}7$. In this talk I plan to sketch the proof of the tight result $\mathrm{ex}_\mathcal{P}(n, C_6)\leq \frac{5}2n-7$, for all $n\geq 18$, and show infinitely many examples when it is tight. Based on them, we raise a conjecture on $\mathrm{ex}_\mathcal{P}(n, C_k)$, for $k\geq 7$.

Joint work with Debarun Ghosh (CEU), Ryan R. Martin (Iowa State Univ.), Addisu Paulos (CEU), Chuanqi Xiao(CEU)

Tuesday, April 20, 2021

2:00 pm in Zoom,Tuesday, April 20, 2021

#### Isomorphic bisections of cubic graphs

###### Shagnik Das (FU Berlin)

Abstract: Graph partitioning is the division of a graph into two or more parts based on certain combinatorial conditions, and problems of this kind of have been studied extensively. In the 1990s, Ando conjectured that the vertices of every cubic graph can be partitioned into two parts that induce isomorphic subgraphs. Using probabilistic methods together with delicate recolouring arguments, we prove Ando's conjecture for large connected graphs.

This is joint work with Alexey Pokrovskiy and Benny Sudakov.

Tuesday, April 27, 2021

2:00 pm in Zoom,Tuesday, April 27, 2021

#### An improvement on Łuczak's connected matching method

###### Shoham Letzter (University College London)

Abstract: A connected matching in a graph $G$ is a matching contained in a connected component of $G$. A well-known method due to Łuczak reduces Ramsey-type problems about paths and cycles in complete graphs to Ramsey-type problems about connected matchings in almost complete graphs. We show that these can be further reduced to Ramsey-type problems about connected matchings in complete graphs.

Tuesday, May 4, 2021

2:00 pm in Zoom,Tuesday, May 4, 2021

#### On sizes of 1-cross intersecting set pair systems

###### Mina Nahvi (UIUC)

Abstract: Let $\{(A_i,B_i)\}_{i=1}^m$ be a set pair system. Furedi, Gyarfas and Kiraly called it $1$-cross intersecting if the size of intersection of $A_i$ and $B_j$ is $1$ when $i$ and $j$ are distinct, and $0$ if $i=j$. They studied such systems and their generalizations, and in particular considered $m(a,b,1)$, the maximum size of a $1$-cross intersecting set pair system in which $|A_i|\leq a$ and $|B_i|\leq b$ for all $i$.

Answering one of their questions, Holzman recently proved that if $a,b\geq 2$, then $m(a,b,1)\leq (29/30)((a+b) \text{ choose } a)$. He also conjectured that the factor $29/30$ in his bound can be replaced by $5/6$. The goal of this talk is to sketch the proof of this improved bound.

This is joint work with Grace Mc.Court and Alexandr V Kostochka.

Tuesday, May 11, 2021

2:00 pm in Zoom,Tuesday, May 11, 2021

#### VC-dimension: a perspective on conjectures of Erdos, Rado, and Schur

###### Janos Pach (Renyi Institute for Mathematics)

Abstract: According to the Erdos-Rado sunflower conjecture, for any integer $r>0$, there is a constant $c=c(r)>0$ such that any family of at least $c^k$ sets of size $k$ has $r$ members such that the intersection of every pair of them is the same. We come close to proving this conjecture for families of bounded Vapnik-Chervonenkis dimension. We use a similar approach to attack other Ramsey-type questions. Joint work with Jacob Fox and Andrew Suk.

Tuesday, August 24, 2021

1:00 pm in 345 Altgeld Hall,Tuesday, August 24, 2021

#### Cycles in Color-Critical Graphs

###### Douglas B. West (Zhejiang Normal University and UIUC)

Abstract: Tuza [1992] proved that a graph $G$ with no cycles of length congruent to $1$ modulo $k$ is $k$-colorable. For $2\le r\le k$, we prove that if $G$ has an edge $e$ such that $G-e$ is $k$-colorable and $G$ is not, then $e$ lies in at least $(k-1)!/(k-r)!$ cycles of length $1{\,\mathrm{mod}\,} r$ in $G$, and $G-e$ contains at least $(1/2)(k-1)!/(k-r)!$ cycles of length $0 {\,\mathrm{mod}\,} r$.

A $(k,d)$-coloring of $G$ is a homomorphism from $G$ to the graph with vertex set $Z_k$ defined by making $i$ and $j$ adjacent if $d\le j-i \le k-d$. Assume $\gcd(k,d)=1$, and let $s=d^{-1}{\,\mathrm{mod}\,} k$. Zhu [2002] proved that $G$ is $(k,d)$-colorable when $G$ has no cycle $C$ with length congruent to $is$ modulo $k$ for any $i\in \{1,...,2d-1\}$. In fact, only $d$ classes need be excluded: we prove that if $G-e$ is $(k,d)$-colorable and $G$ is not, then $e$ lies in at least one cycle with length congruent to $is {\,\mathrm{mod}\,} k$ for some $i$ in $\{1,...,d\}$.

These results are joint work with Benjamin R. Moore.

Tuesday, August 31, 2021

1:00 pm in Zoom,Tuesday, August 31, 2021

#### Maximal Independent Sets in Clique-free Graphs

###### Sam Spiro (University of California, San Diego)

Abstract: An independent set $I$ of a graph $G$ is said to be a maximal independent set (MIS) if it is maximal with respect to set inclusion. Nielsen proved that the maximum number of MIS's of size $k$ in an $n$-vertex graph is asymptotic to $(n/k)^k$, with the extremal construction being a disjoint union of $k$ cliques with sizes as close to $n/k$ as possible. In this talk we study how many MIS's of size $k$ an $n$-vertex graph $G$ can have if $G$ does not contain a clique $K_t$. We prove for all fixed $k$ and $t$ that there exist such graphs with $n^{\lfloor\frac{(t-2)k}{t-1}\rfloor-o(1)}$ MIS's of size $k$ by utilizing recent work of Gowers and B. Janzer on a generalization of the Ruzsa-Szemeredi problem. We prove that this bound is essentially best possible for triangle-free graphs when $k\le 4$. This is joint work with Xiaoyu He and Jiaxi Nie.

Tuesday, September 7, 2021

1:00 pm in 245 Altgeld Hall,Tuesday, September 7, 2021

#### Weighted Turan Numbers and Maximum Crossing Numbers of Trees

###### Sean English (UIUC)

Abstract: In extremal graph theory, the most natural question to consider involves finding the most edges in an $n$-vertex graph that does not contain any copy of some small forbidden graph $F$. We will explore a generalization of this to edge weighted graphs in which the edge weights are induced by a vertex weighting according to some rule. We will solve this problem for cliques when the rule involves weighting each edge by the product or the minimum of the weights of the endpoints.

The main motivation for the study of such problems is in applications to other combinatorial problems. In particular, we will use the product weighting to solve an extremal problem in which the $n$-vertex host graph is not complete, and we will use the minimum edge weighting to solve a problem involving the maximum rectilinear crossing number of trees.

This project was joint work with Patrick Bennett and Maria Talanda-Fisher.

Tuesday, September 14, 2021

1:00 pm in Zoom,Tuesday, September 14, 2021

#### Progress on pursuit-evasion games on graphs

###### Anthony Bonato (Ryerson University)

Abstract: In pursuit-evasion games, a set of pursuers attempts to locate, eliminate, or contain an evader in a network. The rules, specified from the outset, greatly determine the difficulty of the questions posed above. For example, the evader may be visible, but the pursuers may have limited movement speed, only moving to nearby vertices adjacent to them.

Central to pursuit-evasion games is the idea of optimizing certain parameters, whether they are the search number, burning number, or localization number, for example. We report on progress in several pursuit-evasion games on graphs and conjectures arising from their analysis. Finding the values, bounds, and algorithms to compute these graph parameters leads to topics intersecting graph theory, the probabilistic method, and geometry.