Workshop

Zoom Link

Zoom Link

This talk will provide a broad introduction to graph structure theory, focusing on graph minors and recent advances in graph product structure theory.

Zoom Link

In the early 1980s, Erdős and Sós initiated the study of Turán problems with an additional uniformity condition: the uniform Turán density of a hypergraph H is the infimum over all d such for which any sufficiently large hypergraph with the property that all its linear-size subhypergraphs have density at least d contains H. In particular, Erdős and Sós raised the questions on determining the uniform Turán densities of the complete 4-vertex 3-uniform hypergraph and the complete 4-vertex 3-uniform hypergraph with an edge missing. The former remains open after almost 40 years since its statement while the latter was resolved about a decade ago only. We will survey recent progress in this area particularly focusing on corollaries of the major result of Lamaison who showed that the palette lower bound constructions are always optimal.

Zoom Link

A zero-one matrix M is said to contain another zero-one matrix A if we can delete some rows and columns of M and replace some 1-entries with 0-entries such that the resulting matrix is A. The extremal function of A, denoted ex(n, A), is the maximum number of 1-entries that an n×n zero-one matrix can have without containing A. The systematic study of this function for various patterns A goes back to the work of Füredi and Hajnal from 1992. The field has many connections to other areas such as classical Turán type extremal graph theory and Davenport-Schinzel theory and has many applications in mathematics and theoretical computer science.

The problem has been particularly extensively studied for so-called acyclic matrices and this talk is a survey of these results. After several refuted conjectures the one still standing (and wide open) states that the extremal function of any acyclic pattern is $n^{1+o(1)}$.

Zoom Link

For a subset A of vertices of the n-dimensional cube Q_n, let lambda(n,d,s,A) denote the fraction of d-dimensional subcubes of Q_n that contain exactly s points of A. Let lambda(n,d,s) denote the maximum possible value of lambda(n,d,s,A), as A ranges over all subsets of vertices of Q_n, and let lambda(d,s) denote the limit of this quantity as n tends to infinity. I will discuss the problem of determining or estimating the quantities lambda(d,s), describing several intriguing conjectures and some (modest) results. Joint work with Maria Axenovich and John Goldwasser.

Zoom Link

Given graphs F and G, the Erdos-Rogers function asks for the largest number of vertices in an F-free induced subgraph of every n-vertex G-free graph. These are generalizations of Ramsey numbers, and have been extensively researched in the literature. A key part of estimating these quantities is the same question in graphs of prescribed maximum degree. In this talk, we show that this quantity has two principal regimes, according as G is a subgraph of a blowup of F or not, and we use this result to give new bounds on Erdos-Rogers functions. 

Joint work with D. Mubayi and P. Morawski

Zoom Link

A family of lines passing through the origin in an inner product space is said to be equiangular if every pair of lines defines the same angle. In 1973, Lemmens and Seidel raised what has since become a central question in the study of equiangular lines in Euclidean spaces. They asked for the maximum number of equiangular lines in R^r with a common angle of arccos(1/(2k-1)) for any positive integer k. We show that the answer equals r-1+floor((r-1)/(k-1)), provided that r is at least exponential in a polynomial in k. This improves upon a recent breakthrough of Jiang, Tidor, Yao, Zhang, and Zhao, who showed that this holds for r at least doubly exponential in a polynomial in k. We also show that for any common angle arccos a, the answer equals r+o(r) already when r is superpolynomial in 1/a as it tends to infinity. The key new ingredient underlying our results is an improved upper bound on the multiplicity of the second-largest eigenvalue of a graph. In one of the regimes, this improves and significantly extends a result of McKenzie, Rasmussen, and Srivastava.

Zoom Link

Finding regular subgraphs can be useful. Many results assume a graph is regular or are easier to prove when they are. In 1975, Erdős and Sauer asked for an estimate, for any constant r, on the maximum number of edges an n-vertex graph can have without containing an r-regular subgraph. In 2023, Janzer and Sudakov gave an upper bound of the form C(r)n log log n, matching an earlier lower bound by Pyber, Rödl and Szemerédi and thus resolving the Erdős-Sauer problem.

We develop the methods for finding a regular subgraph, showing not only that we can take C(r)=O(r^2), which is optimal up to the implicit constant, but giving estimates for the maximum number of edges an n-vertex graph can have without containing an r-regular subgraph for all possible values of r, which are similarly tight except for around a small `transition point' at r=log n.

I will discuss the framework now developed to find regular subgraphs efficiently, which uses algebraic techniques of Alon, Friedland and Kalai, the recent breakthroughs on the sunflower conjecture, techniques to find almost-regular subgraphs developed from Pyber’s work, and, crucially, a novel random process that efficiently finds a very nearly regular subgraph in any almost-regular graph.

Joint work with Debsoumya Chakraborti, Oliver Janzer and Abhishek Methuku.

Zoom Link

The famous Dirac's Theorem states that for each $n\geq 3$ every $n$-vertex graph $G$ with minimum degree
$\delta(G)\geq n/2$ has  a hamiltonian cycle. When $\delta(G)< n/2$, this cannot be guaranteed, but the existence of some other specific subgraphs can be provided. Chen,  Ferrara, Hu,   Jacobson and  Liu proved  that for $n\geq 56$ every connected $n$-vertex graph $G$ with $\delta(G)\geq (n-2)/3$ contains a spanning {\em broom}, i.e.,  a spanning tree obtained by joining the center of a star to an endpoint of a path. They also were looking for a spanning {\em jellyfish} which is a graph obtained by gluing the center of a star to a vertex in a cycle disjoint from that star. Note that every spanning jellyfish contains a spanning broom.

The goal of this talk is to prove an exact Ore-type bound which guarantees the existence of a spanning jellyfish: We prove that if $G$ is a $2$-connected graph on $n$ vertices such that every non-adjacent pair of vertices $(u,v)$ satisfies $d(u) + d(v) \geq \frac{2n-3}{3}$, then $G$ has a spanning jellyfish. The bound is  sharp for infinitely many $n$.
One of the main ingredients of our proof is a modification of the Hopping Lemma due to Woodall from 1972. This is a joint work with Jaehoon Kim and Ruth Luo.

Zoom Link

We will discuss classical and recent results about phase transitions in random subgraphs of the hypercube and beyond. The focus will be on the giant component, long cycles, large matchings, and isoperimetric properties.

Zoom Link

We study an old question in combinatorial group theory which can be traced back to a problem of Graham from 1971, restated by Erd\H{o}s and Graham in 1980. Given a group $\Gamma$, and some subset $S\subseteq \Gamma$, is it possible to permute $S$ as $s_1,s_2,\ldots, s_d$ so that the partial products $\prod_{1\leq i\leq t} s_i$, $t\in [d]$ are all distinct? Most of the progress towards this problem has been in the case when $\Gamma$ is a cyclic group. We show that for any group $\Gamma$ and any $S\subseteq \Gamma$, there is a permutation of $S$ where all but a vanishing proportion of the partial products are distinct, thereby establishing the first asymptotic version of Graham's conjecture under no restrictions on $\Gamma$ or $S$.
    To do so, we explore a natural connection between Graham's problem and the following very natural question attributed to Schrijver. Given a $d$-regular graph $G$ properly edge-coloured with $d$ colours, is it always possible to find a rainbow path with $d-1$ edges? We settle this question asymptotically by showing one can find a rainbow path of length $d-o(d)$.  A certain natural directed analogue of Schrijver's question gives further implications for Graham's conjecture. 
This is based on joint work with Matija Bucic, Bryce Frederickson, Alp Müyesser and Alexey Pokrovskiy.