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:

Ryser

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.

Advertisements

About Anurag Bishnoi

A mathematician working at FU Berlin as a postdoc. I am broadly interested in combinatorics and finite geometry.
This entry was posted in Combinatorics, Extremal Combinatorics, Finite Geometry, Incidence Geometry and tagged , , , , , , , , . Bookmark the permalink.

One Response to Ryser’s conjecture

  1. Indeed this is a very nice construction! It is simple, but makes enterprising use of results from finite geometry. Thanks for sharing Anurag, and congratulations to you and your co-author!

    What I find interesting in the recent extremal discoveries, is that in my opinion one can look at them in two entirely different ways.

    On the one hand, the increase in extremals when r is more than 4 can perhaps be seen to give good intuition to why Aharon’s simple proof of the tripartite case cannot be extended beyond tripartite graphs. That is, when r is more than or equal to 4, the extremals grow sufficiently large in number and complexity that they cannot be ‘contained’ topologically in a neat manner. Let’s say this is the-glass-is-too-full position.

    On the other hand, almost all the extremals that have been found – including all the infinite families – seem to start with the projective plane construction. So one can argue they are modifications of this one construction. In other words, behind all these constructions, the conjecture seems to have only one true extremal, and the glass is too empty.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s