Combinatorial Theory Seminar

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.

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.

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.