Tuza’s Conjecture

One of my favourite open problems in Tuza’s Conjecture, which relates triangle packings and triangle hitting sets in graphs.

Let $G$ be a graph. A triangle packing is a set of triangles in $G$ no two of which have an edge in common. The maximum size of a triangle packing is called the triangle packing number of $G$, for which we write $\nu(G)$.

A triangle-hitting set is a subset $X \subseteq E(G)$ with the property that removing $X$ from $G$ results in a triangle-free graph. We write $\tau(G)$ for the size of the smallest triangle-hitting set in $G$.

A straightforward argument shows that $\nu(G) \le \tau(G) \le 3\nu(G)$. Tuza conjectured that the upper bound can be improved.

Conjecture (Tuza, 1981): $\tau(G) \le 2\nu(G)$ for all graphs $G$.

In other words, a graph without $t+1$ edge-disjoint triangles can be made triangle-free by removing at most $2t$ edges.

The factor 2 in the conjecture, if true, is best possible: $K_4$ and $K_5$ are examples for which $\tau(G) = 2\nu(G)$.

Geometric Tuza’s Conjecture

Tuza’s Conjecture, being formulated in terms in terms of edges and triangles only, can be naturally generalised to matroids. A triangle in a matroid $M$ is a restriction isomorphic to $U_{2,3}$. We define $\nu(M)$ to be the maximum number of disjoint triangles in $M$, and $\tau(M)$ to be the minimum size of a set $X$ such that $M\backslash X$ does not contain any triangles.

Unfortunately, the geometric version of Tuza’s Conjecture fails for matroids in general: For the Fano plane, $F_7 = \mathrm{PG}(2,2)$, we have $\tau(F_7) = 3$ and $\nu(F_7) = 1$.

Kazu Nomoto and I believe that, at least for binary matroids, the Fano plane is the only obstruction to a geometric version of Tuza’s Conjecture.

Conjecture (Nomoto–Van der Pol, 2021): Let $M$ be a simple binary matroid with no restriction isomorphic to $F_7$. Then $\tau(M) \le 2\nu(M)$.

As graphic matroids do not have restrictions isomorphic to $F_7$, the geometric version of Tuza’s conjecture implies the graphic version. We verified the conjecture for cographic matroids and several other classes of matroids.

Projective planes

Moving beyond binary matroids, one could ask if Tuza’s Conjecture holds for other classes of matroids. Here, we ask if it holds for projective planes. We’ve already seen that the conjecture fails for the Fano plane. It fails spectacularly for all other finite projective planes as well. This result is closely related to classical results in projective geometry.

A finite projective plane is a set system $\Pi = (E,\mathcal{L})$ — the elements of $E$ are called points, and the elements of $\mathcal{L}$ are called lines — with the following properties:

1. Any pair of distinct points is contained in exactly one line;
2. Any pair of lines intersects in exactly one point; and
3. There are four points such that no line contains more than two of them.

For each finite projective plane $\Pi$ there is a number $q \ge 2$, the order of $\Pi$, such that every point is contained in $q+1$ lines, and every line contains $q+1$ points. It follows that a projective plane of order $q$ contains exactly $q^2 + q + 1$ points.

Well-known examples are the Desarguesian planes $\mathrm{PG}(2,q)$, whose points and lines are the 1- and 2-dimensional subspaces of $\mathbb{F}_q^3$, respectively, but there are other examples as well.

Arcs

The lines in $\mathcal{L}$ form the collection of hyperplanes of a rank-3 matroid on $E$, so it makes sense to talk of $\tau(\Pi)$ and $\nu(\Pi)$ for finite projective planes $\Pi$.

An arc in $\Pi$ is a set $A$ of points such that no line intersects $A$ in more than two points. In our terminology, $A$ is a triangle-free restriction of $\Pi$. (Confusingly, the term triangle is also used for an arc of size 3, which is the opposite of our use of the term.)

The following result is well known in projective geometry.

Lemma: Let $\Pi$ be a projective plane of order $q$ and let $A$ be an arc. Then $|A| \le q+2$. If $q$ is odd, then $|A| \le q+1$.

Proof. Let $p \in A$ be any point, and let $\ell_1, \ell_2, \ldots, \ell_{q+1}$ be an enumeration of the lines incident with $p$. Each point in $\Pi$ is on one of those $q+1$ lines, and each line contains at most one point from $A$ other than $p$, so $|A| \le 1 + (q+1)$.

To prove the second bound, suppose for the sake of contradiction that $q$ is odd and $|A| = q+2$. Every line of $\Pi$ intersects $A$ in either $0$ or $2$ points; this is in particular true for all lines through a fixed point $p \not\in A$. It follows that $|A|$ is twice the number of lines incident with $p$ that intersect $A$, so $|A|$ must be even: a contradiction, so $|A| < q+2$. $\Box$

Arcs of size $q+1$ are called ovals, while arcs of size $q+2$ are called hyperovals. Constructions for ovals and hyperovals exist for the planes $\mathrm{PG}(2,q)$; Segre proved that in $\mathrm{PG}(2,q)$ of odd order, all ovals are nondegenerate conic sections.

By the lemma, sets containing more than $q+2$ points must contain a triangle, so $\tau(\Pi)$ is large.

Lemma: Let $\Pi$ be a projective plane of order $q$. If $q$ is even, then $\tau(\Pi) \ge q^2 – 1$. If $q$ is odd, then $\tau(\Pi) \ge q^2$.

Trivially, $\nu(\Pi) \le \frac{1}{3}(q^2+q+1)$. This is sufficient to show that Tuza’s conjecture fails for projective planes of sufficiently large order, as $\tau(\Pi) \sim 3\nu(\Pi)$ as $q \to \infty$.

The trivial upper bound on $\nu$ is correct, as can be shown by a simple construction.

Lemma: Let $\Pi$ be a projective plane of order $q \ge 3$. Then $\Pi$ can be decomposed into disjoint triangles and at most one point. Consequently, $\nu(\Pi) = \lfloor\frac{1}{3}(q^2+q+1)\rfloor$.

Proof. The exact construction depends on the remainder of $q$ modulo 3. Here, we only give the construction for the case $q = 3k+1$; the case $q = 3k+2$ allows a similar construction, while the case $q=3k$ is easier. See the figure following the proof for an illustration in the case $q=4$.

Let $p \in \Pi$ be any point, and let $\ell_0, \ell_1, \ldots, \ell_q$ be an enumeration of the lines incident with $p$. Let $e \in \ell_0$ be a point distinct from $p$, and let $\ell’ = {e, e’_1, \ldots, e’_q}$ and $\ell” = {e, e”_1, \ldots, e”_q}$ be two distinct lines incident with $e$ such that $e’_i, e”_i \in \ell_i$ for $i = 1, 2, \ldots, q$.

Consider the $(q+2)/3$ disjoint triangles

$\{e’_2, e’_3, e’_4\}, \{e’_5, e’_6, e’_7\}, \ldots, \{e’_{q-2}, e’_{q-1}, e’_q\},\quad\text{and}\quad\{e,e”_1, e”_2\}$,

and let $Z$ be the set of all points in those triangles. $Z$ contains exactly one point on each of the lines $\ell_i$, except that it contains two points of $\ell_2$. It follows that each of the sets $\ell_i\setminus (Z \cup {e})$ (for $i \neq 2$) and $\ell_2\setminus Z$ can be partitioned into triangles. $\Box$

It follows from the above results that

$\frac{\tau(\Pi)}{\nu(\Pi)} \ge \frac{q^2-1}{\frac{1}{3}(q^2+q+1)} \ge \frac{15}{7} > 2$

whenever the order $q$ of $\Pi$ is at least 4. For the (unique) projective geometry $\Pi = \mathrm{PG}(2,3)$ of order $q = 3$, we have $\tau(\Pi) = 9$ and $\nu(\Pi) = 4$, while for the (unique) projective geometry $\Pi = \mathrm{PG}(2,2)$ or order $q=2$ we have $\tau(\Pi)=3$ and $\nu(\Pi) = 1$, so Tuza’s Conjecture fails for all finite projective planes.

Covering a graph by forests

Given a loopless graph $G = (V,E)$ with at least one edge, what is the smallest possible number of forests needed to cover all edges? This number is known as the arboricity $a(G)$ of $G$.

For example, consider the following 6-vertex graph, which is obtained from the complete graph $K_5$ by removing one edge, and adding a new pendant edge to one of the vertices of degree 3.

As the graph is connected and has six vertices, each forest in $G$ contains at most five edges. As the graph has ten edges in total, we need at least two forests to cover all edges.

But try as we might, we’ll never be able to cover all edges with only two forests. The reason is that similar bounds must hold in every subgraph of $G$. If we remove the unique degree-1 vertex and the edge incident with it, we are left with a connected graph on five vertices and nine edges. As in this subgraph every forest has at most four edges, we need at least three forests to cover the whole graph. I’ll leave it as an exercise to show that the original graph can actually be covered by three forests.

So, each subgraph $G’$ of $G$ (with at least one edge) provides a lower bound for $a(G)$, as $a(G) \ge \left\lceil \frac{|E(G’)|}{|V(G’)|-c(G’)}\right\rceil$ (here, $c(G’)$ denotes the number of components of $G’$).

Nash-Williams showed that we don’t need more forests than suggested by the worst possible bound obtained in this way: $$a(G) = \max_{G’\subseteq G : E(G’) \neq \emptyset} \left\lceil \frac{|E(G’)|}{|V(G’)|-c(G’)} \right\rceil.$$

Colouring matroids by independent sets

Each of the definitions above can be generalised to matroids, in which case the corresponding question becomes: Given a matroid $M$, how many independent sets do we need to cover the entire ground set of $M$?

The minimum number of independent sets that we need is known as the colouring number (or covering number) of the matroid, and we write $\text{col}(M)$. As loops are not contained in any independent set, we will assume that $M$ has no loops. Edmonds showed (PDF) that the following generalisation of Nash-Williams’ formula holds: $$\text{col}(M) = \max_{E’ \subseteq E: r(E’) > 0} \left\lceil\frac{|E’|}{r_M(E’)}\right\rceil.$$

We say that $M$ is $k$-colourable if $\text{col}(M) \le k$. Note that $a(G) = \text{col}(M(G))$ for any graph $G$, so the colouring number is a proper generalisation of arboricity.

(I like to use “colouring number” rather than “covering number”, as the definition is analoguous to that of “chromatic number” in graphs, which, after all, is the smallest number of independent sets of vertices into which the graph can be partitioned.)

Colouring partition matroids

The colouring number of the uniform matroid $U_{r,n}$ is $\lceil n/r\rceil$. It is clear that this is a lower bound, as $U_{r,n}$ has $n$ elements, and each independent set contains at most $r$ elements.

It is also an upper bound, for we can arbitrarily partition $U_{r,n}$ into $\lfloor n/r\rfloor$ independent sets of size $r$ and, if $r$ does not divide $n$, one more independent set of size less than $r$.

It is an exercise to show that $\text{col}(M_1 \oplus M_2) = \max\{\text{col}(M_1), \text{col}(M_2)\}$.

A matroid is a partition matroid if it is a direct sum of uniform matroids. The following result follows immediately from the above observations:

Lemma.If $M = \bigoplus\limits_{i=1}^k U_{r_i, n_i}$, then $\text{col}(M) = \max\limits_{i=1}^k \lceil n_i / r_i \rceil$.

A 1-partition matroid is a partition matroid in which each of the summands $U_{r_i, n_i}$ has rank 1. The colouring number of a 1-partition matroid is just the size of its largest component.

While colouring 1-partition matroids sounds trivial, the problem occurs naturally in discrete optimisation. For example, edge-colouring bipartite graphs can be described as finding an optimal colouring of the intersection of two 1-partition matroids corresponding to the two sides of the bipartition:

Weak maps and bounds

Suppose that $M$ is some complicated matroid and we want to know or bound $\text{col}(M)$. If $N$ is another matroid on the same ground set such that every independent set in $N$ is independent in $M$ (that is, $N$ is a weak map image of $M$), then $\text{col}(M) \le \text{col}(N)$.

This is particularly useful when $N$ is a 1-partition matroid, as in that case $\text{col}(M)$ is bounded by the size of the largest uniform summand in $N$.

Thus, we have the problem of finding a 1-partition reduction: given a matroid $M$, can we find a 1-partition matroid $N$ that is a weak map image of $M$ whose colouring number is not much larger than that of $M$?

In particular, does there exist a constant $c$ such that we can always find a 1-partition reduction $N$ such that $\text{col}(M) \le \text{col}(N) \le c\cdot\text{col}(M)$? We call a matroid $(1,c)$-decomposable if admits such a 1-partition reduction.

A conjecture

This question was asked by Bérczi, Schwartz and Yamaguchi, who conjectured that every matroid is (1,2)-decomposable; that is, for every $k$-colourable matroid $M$, there exists a partition $E(M) = X_1 \cup X_2 \cup \ldots \cup X_\ell$ such that each $X_i$ contains at most $2k$ elements, and each transversal of $\{X_1, X_2, \ldots, X_\ell\}$ is independent.

While this sounds like a very strong statement, it is true for a large number of natural classes of matroids, including graphic matroids and transversal matroids. (In those cases, an actual 1-partition reduction can be found in polynomial time, based on the natural representations of such matroids).

Unfortunately, the general conjecture was recently shown to fail for large binary projective geometries by Abdolazimi, Karlin, Klein and Oveis Gharan (in fact, their argument shows that there are matroids that are not $(1,c)$-decomposable for arbitrary $c$; a stronger result was later obtained by Leichter, Moseley and Pruhs). I was later able to show the slightly stronger result that almost every $\mathbb{F}_q$-representable matroid is not $(1,c)$-decomposable.

However, not all is lost. While there are counterexamples to the conjecture, the number of such counterexamples may be small; more precisely, the conjecture may still hold for almost all matroids.

Let $\mathcal{P}$ be a matroid property that is closed under isomorphism. We say that almost every matroid has property $\mathcal{P}$ if the fraction of matroids on ground set $[n]$ that fail $\mathcal{P}$ vanishes as $n$ tends to infinity, that is $$\lim_{n \to \infty} \frac{\#\{\text{matroids on $[n]$ with $\mathcal{P}$}\}}{\#\{\text{matroids on $[n]$}\}} = 1.$$

Bérczi, Schwarcz, and Yamaguchi proved that paving matroids are (1,2)-decomposable. It is widely believed that almost every matroid is paving; proving this conjecture would imply that almost every matroid is (1,2)-decomposable.

In fact, since we know a little more about random matroids, the factor 2 can be improved slightly.

First, we know that almost every matroid has rank close to half its size. More precisely, for $\varepsilon > 0$, almost every matroid satisfies $$\left(\frac{1}{2}-\varepsilon\right)|E(M)| \le r(M) \le \left(\frac{1}{2}+\varepsilon\right)|E(M)|.$$

Second, Bérczi, Schwarcz and Yamaguchi proved that a paving matroid of rank $r \approx n/2$ is 2- or 3-colourable, and that if it is $k$-colourable, it has a $\lceil\frac{r}{r-1}k\rceil$-colourable partition reduction. This leads to the following updated version of the conjecture, which may still be true:

Conjecture. Almost every matroid is (1, 3/2)-decomposable.

Finite linear spaces

A finite linear space is a set $E$ of points together with a family $\mathcal{L}$ of lines with the property that

• every pair of points is on a line, and
• every line contains at least two points.

In matroidal terms, a finite linear space is a simple matroid of rank 3, given by its hyperplanes (unless all points are on a single line). We will drop the word “finite”, and simply talk about linear spaces instead.

How many lines must be in a linear space?

Let’s write $n = |E|$. As every pair of points defines a line, we immediately see that $|\mathcal{L}| \le \binom{n}{2}$. Equality holds when $\mathcal{L}$ is the family of all pairs in $E$; or equivalently, if $(E,\mathcal{L})$ is the rank-3 uniform matroid on $E$.

In $U_{3,n}$, all lines are as short as they can be. A more interesting question is: How many “long” lines can a linear space contain? Here, a line is long if it contains 3 or more points.

Proposition. A linear space on $n$ points contains at most $\frac{1}{3}\binom{n}{2}$ long lines.

Proof. Every pair of points is in at most one long line, and every long line contains at least three pairs of points. $\Box$

The proposition says that a simple rank-3 matroid on $n$ points has at most $\frac{1}{3}\binom{n}{2}$ long lines.

Equality holds if and only if each line contains exactly 3 points. In this case, $\mathcal{L}$ is the set of blocks of a Steiner triple system, and we necessarily have $n \equiv 1,3$ modulo 6.

In the other direction, we can ask: What is the smallest possible number of lines in a linear space? A reasonable guess is that this number is minimised when $\mathcal{L}$ consists one line containing all but one of the points, and $n-1$ two-point lines, each containing the remaining point of $E$. We know this as the matroid $U_{n-1,2} \oplus U_{1,1}$, but this linear space is also called a near-pencil.

• 

• 

Projective planes on $n$ points, when they exist, have $n$ lines as well. De Bruijn and Erdős showed that near-pencils and projective planes have the smallest number of lines among all linear spaces.

Theorem (De Bruijn–Erdős, 1948). A linear space on $n$ points, not all collinear, has at least $n$ lines. Equality holds if and only if the linear space is a near-pencil or a projective plane.

This translates to the following matroid version.

Theorem (De Bruijn–Erdős, matroid version). A simple rank-3 matroid $M$ on $n$ points has at least $n$ hyperplanes. Equality holds if and only if $M \cong U_{2,n-1} \oplus U_{1,1}$ or $M$ is a finite projective plane.

A slick proof due to Conway can be found in Jukna’s book Extremal Combinatorics. It was already noted by De Bruijn and Erdős that the Euclidean analogue of this theorem (i.e., when we assume that $M$ is real-representable) follows from the Sylvester–Gallai Theorem Jim Geelen discussed in a previous post.

Higher rank

Linear spaces can be generalised to higher dimensions. One such generalisation is known as a Hartmanis partition, which to the matroid theorist is probably better known as a paving matroid. A paving matroid is a matroid in which the only “interesting” flats are the hyperplanes: each flat of lower rank is an independent set (alternatively, each circuit has cardinality at least the rank of the matroid). For example, a matroid of rank 3 is paving if and only if it is simple, while the Vámos matroid is a paving matroid of rank 4.

The De Bruijn–Erdős Theorem is the base case of the following result.

Lemma. Let $3 \le r \le n$ and let $M$ be a paving matroid of rank $r$ on $n$ points. Then $M$ has at least $n$ hyperplanes.

Proof. For $r=3$, this is just the bound from the De Bruijn–Erdős Theorem. We proceed by induction on $r$. Suppose that the theorem holds for $r = s$, and let $M$ be a matroid of rank $s+1$. Let $e \in E(M)$. The hyperplanes of $M/e$ are in natural correspondence with the hyperplanes of $M$ that contain $e$. By induction, $M/e$ has at least $n-1$ hyperplanes, so $M$ has at least $n-1$ hyperplanes that contain $e$. Finally, as $e$ is not a loop, $M$ has at least one hyperplane that does not contain $e$. We conclude that $M$ has at least $n$ hyperplanes. $\Box$

It is not hard to construct rank-$r$ matroids with exactly $n$ hyperplanes—one example is $U_{2,n-r+2}\oplus U_{r-2,r-2}$. More generally, we can take any of the tight examples from the De Bruijn–Erdős Theorem on $n-r+3$ points and add $r-3$ coloops. However, the matroids obtained in this way are far from paving.

Question. For $r \ge 4$, is the bound on the number of hyperplanes in the previous lemma tight?

I suspect the answer is “no”. If I had to guess the correct number, it would be $1+\binom{n-1}{r-2}$, which is the number of hyperplanes of $U_{r-1,n-1}\oplus U_{1,1}$.

We now drop the assumption that $M$ is paving and write $f_k(r,n)$ for the minimal number of rank-$k$ flats in a simple matroid of rank $r$ on $n$ points. The De Bruijn–Erdős Theorem asserts that $f_2(3,n) = n$.

The following lemma shows that $f_k(r,n)$ is increasing in $r$. The truncation of a matroid is obtained by removing the hyperplanes from its lattice of flats; this operation decreases the rank of the matroid by 1.

Lemma. For all $2 \le k < r-1 < n$ we have $f_k(r,n) \ge f_k(r-1,n)$.

Proof. Let $M$ be a matroid of rank $r$ on $n$ points with $f_k(r,n)$ flats of rank $k$. The truncation of $M$ has rank $r-1$ and $f_k(r,n)$ flats of rank $k$. $\Box$

Let me conclude by asking about a higher-dimensional analogue of the De Bruijn–Erdős Theorem.

Question. For $2 \le k < r \le n$, what is $f_k(r,n)$?

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 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$