Combinatorial Theory Seminar

An interesting twist on classical subgraph containment problems in graph theory is the following: given a graph $H$ and a collection $\{G_1, \dots , G_m\}$ of graphs on a common vertex set $[n]$, what conditions on $G_i$ guarantee a copy of $H$ using at most one edge from each $G_i$? Such a subgraph is called transversal, and the above problem is closely related to the study of temporal graphs in Network Theory. In 2020 Joos and Kim showed that if $\delta(G_i)\geq n/2$, the collection contains a transversal Hamilton cycle. We improve on their result by showing that it actually contains every transversal Hamilton cycle if $\delta(G_i)\geq (1/2+o(1))n$. That is, for every function $\chi:[n]\to[m]$, there is a Hamilton cycle whose $i$-th edge belongs to $G_{\chi(i)}$.

This is joint work with Candida Bowtell, Patrick Morris and Katherine Staden.

Let $G$ be a $d$-regular graph of growing degree on $n$ vertices. Form a random subgraph $G_p$ of $G$ by retaining edge of $G$ independently with probability $p=p(d)$. Which conditions on $G$ suffice to observe a phase transition at $p=1/d$, similar to that in the binomial random graph $G(n,p)$, or, say, in a random subgraph of the binary hypercube $Q^d$?

We argue that in the supercritical regime $p=(1+\epsilon)/d$, $\epsilon>0$ a small constant, postulating that every vertex subset $S$ of $G$ of at most $n/2$ vertices has its edge boundary at least $C|S|$, for some large enough constant $C=C(\epsilon)>0$, suffices to guarantee likely appearance of the giant component in $G_p$. Moreover, its asymptotic order is equal to that in the random graph $G(n,(1+\epsilon)/n)$, and all other components are typically much smaller.

We also give examples demonstrating tightness of our main result in several key senses.

A joint work with Sahar Diskin, Joshua Erde and Mihyun Kang.

A cluster graph is a disjoint union of complete graphs. We consider the random $G(n,p)$ graph on $n$ vertices with connection probability $p$, conditioned on the rare event of being a cluster graph. There are three main motivations for our study.

1. For $p = 1/2$, each random cluster graph occurs with the same probability, resulting in the uniform distribution over set partitions. Interpreting such a partition as a graph adds additional structural information.
2. To study how the law of a well-studied object like $G(n,p)$ changes when conditioned on a rare event; an evidence of this fact is that the conditioned random graph overcomes a phase transition at $p=1/2$ (not present in the dense $G(n,p)$ model).
3. The original motivation was an application to community detection. Taking a random cluster graph as a model for a prior distribution of a partition into communities leads to significantly better community-detection performance.

This is joint work with Martijn Gösgens, Lukas Lüchtrath, Elena Magnanini and Élie de Panafieu.

The saturation number of a graph is a famous and well-studied counterpoint to the Turán number, and the rainbow saturation number is a generalisation of the saturation number to the setting of coloured graphs. Specifically, for a given graph $F$, an edge-coloured graph is $F$-rainbow saturated if it does not contain a rainbow copy of $F$, but the addition of any non-edge in any colour creates a rainbow copy of $F$. The rainbow saturation number of $F$ is the minimum number of edges in an $F$-rainbow saturated graph on $n$ vertices. Girão, Lewis, and Popielarz conjectured that, like the saturation number, for all $F$ the rainbow saturation number is linear in $n$. I will present our attractive and elementary proof of this conjecture, and finish with a discussion of related results and open questions.

We show that there exists $C>1$, such that if $A$ is a subset of a non-alternating finite simple group $G$ of density $|A|/|G|= \alpha$, then $AA^{-1}AA^{-1}$ contains a subgroup of density at least $\alpha^{C}$. We will also give a corresponding (slightly weaker) statement for alternating groups.

To prove our results we introduce new hypercontractive inequalities for simple groups. These allow us to show that the (non-abelian) Fourier spectrum of indicators of 'global' sets are concentrated on the high-dimensional irreducible representations. Here globalness is a pseudorandomness notion reminiscent of the notion of spreadness.

The talk is based on joint works with David Ellis, Shai Evra, Guy Kindler, Nathan Lindzey, and Peter Keevash, and Dor Minzer. No prior knowledge of representation theory will be assumed.

A colouring rule is a way to colour the points $x$ of a probability space according to the colours of finitely many measure preserving tranformations of $x$. The rule is paradoxical if the rule can be satisfied a.e. by some colourings, but by none whose inverse images are measurable with respect to any finitely additive extension for which the transformations remain measure preserving. We show that proper graph colouring as a rule can be paradoxical. And we demonstrate rules defined via optimisation that are paradoxical. A connection to measure theoretic paradoxes is established.

The positive discrepancy of a graph $G$ is the maximum surplus of edges in an induced subgraph of $G$ compared to its expected size. This quantity is closely related to other well studied parameters, such as the minimum bisection and the spectral gap. I will talk about the extremal behavior of the positive discrepancy among graphs with given number of vertices and average degree, uncovering a surprising pattern. This leads to an almost complete solution of a problem of Alon on the minimum bisection and let's us extend the Alon-Boppana bound on the second eigenvalue to dense graphs.

Joint work with Eero Räty and Benny Sudakov.

The directed landscape is a random directed metric on the plane that is the scaling limit for models in the KPZ universality class (i.e. last passage percolation on $\mathbb{Z}^2$, TASEP). In this metric, typical pairs of points are connected by a unique geodesic.  However, certain exceptional pairs are connected by more exotic geodesic networks. The goal of this talk is to describe a full classification for these exceptional pairs.

An $n$-vertex graph $G$ is a $C$-expander if $|N(X)|\geq C|X|$ for every $X\subseteq V(G)$ with $|X|< n/2C$ and there is an edge between every two disjoint sets of at least $n/2C$ vertices.

We show that there is some constant $C>0$ for which every $C$-expander is Hamiltonian. In particular, this implies the well known conjecture of Krivelevich and Sudakov from 2003 on Hamilton cycles in $(n,d,\lambda)$-graphs. This completes a long line of research on the Hamiltonicity of sparse graphs, and has many applications.

Joint work with R. Montgomery, D. Munhá Correia, A. Pokrovskiy and B. Sudakov.

Brown-Erdős-Sós initiated the study of the maximum number of edges in an $n$-vertex $r$-graph such that no $k$ edges span at most $s$ vertices. If $s=rk-2k+2$ then this function is quadratic in $n$ and its asymptotic was previously known for $k=2,3,4$. I will present joint work with Stefan Glock, Jaehoon Kim, Lyuben Lichev and Shumin Sun where we resolve the cases $k=5,6,7$.