Mathematics

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.

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

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

Please contact Sean at SEnglish (at) illinois (dot) edu for Zoom information.

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.

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

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.

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.

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

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.

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

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.

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

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.

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

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.

Please contact Sean at SEnglish (at) illinois (dot) edu for the Zoom information.

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.

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

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)

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