Online talk: Tony Huynh

Mon, August 31, 3pm ET (8pm BST, 7am Tue NZST)
Tony Huynh, Monash University
Subgraph densities in a surface

We consider the following problem at the intersection of extremal and structural graph theory. Given a fixed graph $H$ and surface $\Sigma$, what is the maximum number of copies of $H$ in an $n$-vertex graph that embeds in $\Sigma$? Here a copy means a subgraph isomorphic to $H$. Exact answers are known for some $H$ when $\Sigma$ is the sphere. Our main result answers the question for all $H$ and $\Sigma$ (up to a constant factor). We show that the answer is $\Theta(n^{f(H)})$ where $f(H)$ is a graph invariant called the flap number of $H$, which is independent of the surface $\Sigma$.

This is joint work with Gwenaël Joret and David Wood.

Online talk: Ahmad Abdi

Mon, August 24, 3pm ET (8pm BST, 7am Tue NZST)
Ahmad Abdi, London School of Economics
Ideal clutters and dyadic fractional packings

A clutter is a finite family of finite sets where no set contains another one. Clutters form a very broad class of objects generalizing graphs and matroids in more than one way, and are also accompanied by notions of duality (more specifically, the blocking relation) and minor theory.

Most questions about clutters can be traced back to the study of three key parameters: the covering number, the fractional packing number, and the packing number, ordered from largest to smallest. The first two parameters are known to be equal, and efficiently computable, for the class of ideal clutters, an important class of clutters rooted in Combinatorial Optimization and Polyhedral Combinatorics.

In 1975, Seymour conjectured that for every ideal clutter, the fractional packing number can be attained not just by a fractional vector, but by a vector whose entries are dyadic rational numbers. As a first step, we prove this conjecture in the case when the fractional packing number is equal to 2; we also provide a quasi-polynomial time algorithm for finding the dyadic vector. Our proof techniques rely on the key insight that ideal clutters are so-called clean, i.e. they forbid two infinite classes of clutters as a minor, one coming from projective planes, and another coming from odd holes.

In this self-contained talk, after contextualizing Seymour’s conjecture, I shall motivate clean clutters and survey two important subclasses other than ideal clutters, namely, binary clutters (coming from binary matroids), and clutters without an intersecting family as a minor.

Based on joint work with Gérard Cornuéjols, Bertrand Guenin, and Levent Tunçel.


P.S. Upcoming speakers for the next month are now listed at the talks page.

Online talk: Sophie Spirkl

Mon, August 17, 3pm ET (8pm BST, 7am Tue NZST)
Sophie Spirkl, University of Waterloo
A graph-based introduction to the chromatic symmetric function

The chromatic symmetric function is a generalization of the chromatic polynomial, and has been studied extensively, mostly in algebraic combinatorics. I’ll give an introduction to the chromatic symmetric function from a graph theory point of view, including some results and open questions.

Joint work with Logan Crew.

Almost every sparse paving matroid contains $M(K_4)$ or $W^3$ as a minor

Two conjectures and a theorem

One conjecture that I quite like is the following, due to Mayhew, Newman, Welsh, and Whittle.

Conjecture 1. Let $N$ be a sparse paving matroid. Almost every matroid has an $N$-minor.

We say that almost every matroid has an $N$-minor when the fraction of matroids on ground set $\{1,2,\ldots,n\}$ that does not have an $N$-minor tends to 0 as $n$ tends to infinity. A sparse paving matroid is a matroid in which every dependent hyperplane is a circuit; equivalently, every $r(M)$-set is either a basis or a circuit-hyperplane. Such matroids are combinatorially more benign than general matroids, although it has been conjectured that almost every matroid is sparse paving.

The conjecture is known to hold in only a few special cases: when $N$ is a uniform matroid and when $N$ is a matroid of rank 3 on 6 elements with at most two dependent hyperplanes. The two smallest cases that remain open are $N=M(K_4)$ and $N=W^3$.

The complete-graphic matroid M(K4).

The matroid $M(K_4)$.

The whirl W3 has six points and three dependent hyperplanes.

The matroid $W^3$.


The conjecture remains hard even when we restrict our attention to sparse paving matroids.

Conjecture 2. Let $N$ be a sparse paving matroid. Almost every sparse paving matroid has an $N$-minor.

Conjecture 2 holds for all the cases for which we know that Conjecture 1 holds. A few additional cases, including $N = W^3$, are proved by Critchlow in his PhD thesis. Here, I want to give a quick proof that almost every sparse paving matroid contains an $M(K_4)$- or $W^3$-minor.

Theorem. Almost every sparse paving matroid has an $M(K_4)$- or $W^3$-minor.

It may be much harder to prove the corresponding claim for general matroids.

Reduction to rank 3

A few years ago, Rudi Pendavingh and I wrote about using entropy to bound the number of matroids in minor-closed classes. The main technical result in that post is the following, which allows one to translate a bound on the number of matroids of rank $s$ to a bound on the number of matroids of rank $r$.

Matroid Entropy Lemma. If $\mathcal{M}$ is a class of matroid that is closed under isomorphism and contraction, then for all $s \le r$ $$\log\left(m_{\mathcal{M}}(n,r)+1\right)/\binom{n}{r} \le \log\left(m_{\mathcal{M}}(n-r+s,s) + 1\right)/\binom{n-r+s}{s}.$$

Here we write $m_{\mathcal{M}}(n,r)$ for the number of matroids in $\mathcal{M}$ on ground set $\{1,2,\ldots,n\}$ that have rank $r$.

The Matroid Entropy Lemma (used with $s=2$) is sufficiently strong to prove a near-optimal upper bound on the number of matroids. Moreover, when the lemma is used with $s=3$, it can be used that almost every matroid contains a $U_{2,k}$- or $U_{3,6}$-minor.

As Rudi and I described in our blog post, the Matroid Entropy Lemma is useful for problems of enumeration, since it reduces general counting problems to counting problems in fixed rank. In particular, when we use $s=3$, counting problems reduce to counting problems involving points and lines. Specialising the lemma to the case of excluding rank-3 sparse paving matroids, we obtain the following general result.

Lemma 1. Let $\mathcal{X}$ be a set of sparse paving matroids of rank 3, and let $s_{\mathcal{X}}(n)$ be the number of sparse paving matroids of rank 3 on ground set $\{1,2,…,n\}$ that do not have any minor contained in $\mathcal{X}$. If there exists a constant $c < 1/2$ such that $\log s_{\mathcal{X}}(n) \le \frac{c}{n}\binom{n}{3}$ for all sufficiently large $n$, then almost every sparse paving matroid has an element of $\mathcal{X}$ as a minor.

Sparse paving matroids of rank 3 are extremely friendly objects. Their dependent hyperplanes (or long lines) form the edges of linear 3-uniform hypergraph, or equivalently the blocks of a partial Steiner triple system.

Unfortunately, when $\mathcal{X} = \{M(K_4)\}$, Lemma 1 is of no use to us.

In design theory literature, $M(K_4)$ is known as the Pasch configuration or quadrilateral, and it is well known that there exist “anti-Pasch” or “quadrilateral-free” Steiner triple systems whenever $n = 1,3 \mod 6$ and $n \ge 15$. As a full Steiner triple system contains $n(n-1)/6$ blocks, the Lemma does not apply.

When $\mathcal{X} = \{W^3\}$, Lemma 1 requires us to bound the number of 3-uniform linear hypergraphs without $W^3$ as an induced subgraph, which may be an interesting class to study.

The Ruzsa–Szemerédi problem

Something interesting happens when $\mathcal{X} = \{W^3, M(K_4)\}$. Lemma 1 now requires us to bound the number of 3-uniform linear hypergraphs that do not contain $W^3$ are a subgraph. Equivalently, the union of any three edges of such a hypergraph contains at least seven vertices. Let us call such a hypergraph a Ruzsa–Szemerédi hypergraph.

The Ruzsa–Szemerédi problem or (6,3)-problem asks for the maximum number of edges in such a hypergraph. Let us write $\text{rs}(n)$ for this number; Rusza and Szemerédi showed that $\text{rs}(n) = o(n^2)$ using the Szemerédi Regularity Lemma.

We now show that this implies that we can use Lemma 1 to prove the Theorem.

Lemma 2. Let $\mathcal{X} = \{W^3, M(K_4)\}$. Then $s_{\mathcal{X}}(n) = 2^{o(n^2)}$.

Proof. Let $H$ be a Ruzsa–Szemerédi hypergraph on $n$ vertices. Let $G(H)$ be the graph on the same vertex set, whose edges correspond to pairs of elements that are contained in an edge of $H$. Such a graph has the property that every edge is in a unique triangle, which means that $H$ can be reconstructed from $G(H)$. As $G(H)$ has at most $3\text{rs}(n)$ edges, it follows that the number of Ruzsa–Szemerédi hypergraphs on $n$ vertices is at most $\binom{\binom{n}{2}}{\le 3\text{rs}(n)}$. A standard bound on binomial coefficients tells us that this is at most $2^{h\left(\text{rs}(n)/\binom{n}{2}\right)\binom{n}{2}}$, where $h$ is the binary entropy function. The lemma now follows from the fact that $\text{rs}(n) = o(n^2)$ and $h(\varepsilon)\downarrow 0$ as $\varepsilon \downarrow 0$. $\Box$