Ryser’s conjecture

I am on a research visit in Rome, working with Valentina Pepe, and our joint paper on Ryser’s conjecture is on arXiv now. So this seems like the right time to talk about the conjecture and the problems related to it that I have been obsessing over for past few months.

In graph theory, the classical result of Kőnig says that in any (finite) bipartite graph the minimum number of vertices that cover all edges (the so-called vertex cover number) is equal to the maximum number of pairwise disjoint edges in the graph (matching number). This result is clearly not-true for non-bipartite graphs (think of some obvious counter examples), where the best one can do is have the vertex cover number equal to twice the matching number since the vertices contained in any maximum matching must cover all the edges. Ryser’s conjecture is a proposed generalisation of this result to $r$-partite hypergraphs, that is, for hypergraphs whose vertex set can be partitioned into $r$ parts (let’s call them sides from now on), such that each edge of the hypergraph contains a unique vertex from each of the sides. In particular, every $r$-partite hypergraph is $r$-uniform, that is, each edge has exactly $r$ vertices in it. If we have any $r$-uniform hypergraph $\mathcal{H}$ (not necessarily $r$-partite), then the following follows as before, $\tau(\mathcal{H}) \leq r \nu(\mathcal{H})$, where $\tau$ denotes the vertex cover number and $\nu$ the matching number. Ryser’s conjectured that if $\mathcal{H}$ is $r$-partite, then we must have $\tau(\mathcal{H}) \leq (r - 1) \nu(\mathcal{H})$. This conjecture first appeared in the Ph.D. thesis of Ryser’s student, J.R. Henderson, and it has often been misattributed to a 1967 paper of Ryser (see this).

Despite the time span of about 50 years, our current knowledge about this conjecture is abysmal. The only other case of this conjecture which is known to be true in general is $r = 3$, which was proved by Aharoni using topological methods! If we impose some further restrictions on the hypergraph, then we know a bit more, but not much. The conjecture is true for intersecting hypergraphs (matching number equal to $1$) if $r \leq 5$, as proved by Tuza, and for $r \leq 9$ if the hypergraph is also linear, as proved in the recent paper by Francetić, Herke, McKay and Wanless.

In view of our inability to prove this conjecture, some natural questions to ask are, (1) is it even true?, and (2) why is it so hard to prove?. While it’s quite possible that the conjecture is false, let’s focus on (2) for now. Sometimes what makes an extremal problem in combinatorics hard to prove is that there are many different kinds of extremal examples, and a “combinatorial” proof must somehow consider all of these examples (I should thank Tibor Szabó for this intuition). So let’s see what we know about hypergraphs meeting the bound in Ryser’s conjecture.

Until recently, the only known family of $r$-partite hypergraphs with vertex cover number equal to $r - 1$ times the matching number, called $r$-Ryser hypergraphs, came from finite projective planes of order $r - 1$ (which is what sparked my interest in this problem), and hence they were known to exist whenever $r - 1$ is equal to a prime power ($2, 3, 4, 5, 6, 8, 9, 10, \dots$). Once you know the definition of projective planes, the construction is easy: remove a point and all lines through it. These hypergraphs are hence known as truncated projective planes. Note that this gives us intersecting $r$-Ryser hypergraphs, and to get such hypergraphs with matching number $\nu$ one can simply take $\nu$ disjoint copies of the intersecting hypergraphs (more on this later!). Inspired by the lack of examples, several people gave constructions for small values of $r$ where projective planes did not exist (or were not known to exist), and then Abu-Khazneh, Barát, Pokrovskiy and Szabó, came up with a clever construction which gave a new infinite family of intersecting $r$-Ryser hypergraphs whenever $r - 2$ is a prime power. In fact, they were able to construct many non-isomorphic examples of such hypergraphs! Note that while it is known that there are plenty of non-isomorphic projective planes of a given order, it is not clear what the rate of growth of this function is, and that’s a fascinating problem on its own. Another interesting family of $r$-Ryser hypergraphs was obtained by Haxell and Scott, whenever both $(r - 1)/2$ and $(r + 1)/2$ are prime powers (whether this gives infinitely many new values of $r$ for which we have a Ryser hypergraph or not is in fact related to a nice open problem in number theory, which a careful reader should be able to deduce :)). Both of these constructions rely on finite projective or affine planes.

Valentina and I have constructed new infinite families of non-intersecting $r$-Ryser hypergraphs, whenever $r - 1$ is a prime power bigger than $3$, which looks fundamentally different from just taking disjoint copies of intersecting Ryser hypergraphs. The condition on $r$ being at least $4$ cannot be relaxed since a result of Haxell, Narins and Szabo, says that every $3$-Ryser hypergraph is essentially obtained by taking disjoint copies of intersecting $3$-Ryser hypergraphs. For $r = 4$ it was already known that such a characterisation cannot be true, because of a computer-generated example of Abu-Khazneh. Our constructions show that for any $r \geq 4$ and $\nu > 1$, such that $r - 1$ is a prime power, there exists an $r$-Ryser hypergraph with matching number equal to $\nu$ which does not contain two vertex disjoint copies of intersecting $r$-Ryser hypergraphs.

The constructions are again finite geometric, and we were quite happy about the fact that many non-trivial results on blocking sites of finite projective planes came into play when proving that these hypergraphs are Ryser extremal. Here is a description of the first family, with $\nu = 2$, along with a picture:

Let $\pi_1$ and $\pi_2$ be two copies of classical projective planes of order $q$ with a common point $P$, which will be truncated at the the points $Q_1$ and $Q_2$. Let $\mathcal{C}$ be a conic in the second plane passing through $q$, and $v$ an extra vertex. The edges of the hypergraph are (1) all lines in the first plane not through $Q_1$ or $P$, and a line $\ell$ through $P$ which does not contain $Q_1$; (2) all the lines of the second projective plane not through $Q_2$ that contain a point of the conic $\mathcal{C}$; (3) two new (weird) edges $e_1$ and $e_2$ with $e_1 = \ell \setminus \{P\} \cup \{R\}$ and $e_2 = C \setminus \{Q_2\} \cup \{v\}$.

The fact that this is a $(q + 1)$-Ryser hypergraph of matching number $2$ with the required properties, whenever $q$ is an odd prime, is proved in the paper. For other values of $q$, there is a second, more involved, construction (which also comes with a picture!).

Our new constructions show that the non-intersecting Ryser hypergraphs can have a richer structure, and perhaps it’ll be useful to construct more such hypergraphs for either disproving the conjecture or understanding the extremal cases better. Some other interesting questions, that have also been mentioned before by others, are as follows:

Open problem 1: Find the minimum number of edges an $r$-Ryser hypergraph can have. It is not known, but conjectured, that linearly many edges should suffice.

Open problem 2: What is the largest vertex cover number of an $r$-partite intersecting hypergraph, if the “trivial” covers containing a side or an edge are not allowed?

This seems to be related to the problem of finding the smallest non-trivial blocking set in finite projective planes.

Open problem 3: Prove, or disprove!, Ryser’s conjecture.