Extending Ryser’s conjecture

In an earlier post, I talked about Ryser’s conjecture on r-partite r-uniform hypergraphs, that has stayed open for all r \geq 4 despite a considerable effort by several mathematicians over a period of 50 years. A bit more effort has been spent on the special case of intersecting hypergraphs, that is, hypergraphs in which every two edges share at least one common vertex. Here the wishful thinking is that this will shed some light on the original conjecture (which one might expect, but there are some surprises), or mathematicians are just following Pólya’s principle: “If you can’t solve a problem, then there is an easier problem you can solve: find it.”. Sadly, we can’t even solve this easier problem; the conjecture is open for intersecting hypergraphs for all r \geq 6. Therefore, it is quite natural to look for simpler problems by adding more restrictions. One of the restrictions is to consider strictly 1-intersecting, a.k.a., linear hypergraphs, that is, every two distinct edges share exactly one common vertex. This seems quite strong, but even in this situation we only know the conjecture to be true for r \leq 9.

Here are two alternate conditions one could impose that are stronger than the hypergraph being intersecting:

  1. (k-wise intersection) any collection of k edges contains a common vertex.
  2. (t-intersection) any two distinct edges have at least t vertices in common.

Note that in (1.) we can have repetitions in the collection of edges, and thus in particular k-wise intersection implies k'-wise intersection for any k' < k.

In this post I want to share some good news regarding these two new settings. In a joint work with my former colleagues, Shagnik Das, Patrick Morris and Tibor Szabó we have completely solved (1.) for all k \geq 3. Interestingly, we used some new results that we proved for (2.) in doing that. To describe our results, let us first define the following function which is central to Ryser’s conjecture:

\mathrm{Ryser}(r, t) = \max \{\tau(H) : H \text{ is a } t\text{-intersecting } r\text{-uniform } r\text{-partite hypergraph}\},

where \tau(H) is the vertex cover number of H, that is, the smallest number of vertices that cover all edges.

Ryser’s conjecture (for intersecting hypergraphs) states that \mathrm{Ryser}(r, 1) \leq r - 1 (note that every edges is a vertex cover, and hence \mathrm{Ryser}(r,1) \leq r is trivially true). If true, this bound will be sharp for infinitely many values of r.

The problem of determining \mathrm{Ryser}(r, t) was introduced a few years back independently by BustamanteStein, and KirályTóthmérész, who made an analogous conjecture for this function that says \mathrm{Ryser}(r, t) \leq r - t. While Ryser’s conjecture is a special case of this one, it is in fact implied by Ryser’s conjecture, that is, \mathrm{Ryser}(r,1) \leq r - 1 ~ \forall r \implies \mathrm{Ryser}(r,t) \leq r - t ~\forall r > t \geq 1. Therefore, one might hope to make progress over this new conjecture for larger values of t, even though t = 1 seems out of reach at the moment. This is what was done, as Bustamante and Stein proved the conjecture for t \geq (r - 2)/2 whereas Király and Tóthmérész proved it for t \geq (r + 1)/4. Moreover, Bustamante and Stein observed that their conjecture is not sharp as \mathrm{Ryser}(5, 2) = 2 instead of being equal to 5 - 2 = 3. This, was the starting point of our work. In fact, I have picture from the exact moment where we started working on proving that the conjecture might not be sharp for other values:

IMG_20180906_121630.jpg

Tibor and Patrick thinking hard about \mathrm{Ryser}(r,t)

This is from the 2018 research group workshop organised by Tibor where I had proposed this problem and the three of us worked on it for two days. We managed to prove that for large enough t, the correct value of \mathrm{Ryser}(r,t) is in fact half of what was conjectured:

Theorem 1. \mathrm{Ryser}(r,t) = \lfloor (r - t)/2 \rfloor + 1, for all t + 1 \leq r \leq 3t - 1.

Once we came back to Berlin from our workshop, Shagnik joined our team:

IMG_20180906_154233.jpg

This is him during the workshop when he was helping us cook Goulash, not realising that helping us on Ryser’s conjecture could also be fun!

He proved that Theorem 1 in fact implies the following result on the function

\mathrm{Ryser}(r, t, k) = \max \{\tau(H) : H \text{ is a } k\text{-wise } t\text{-intersecting } r\text{-uniform } r\text{-partite hypergraph}\}.

Theorem 2. For any k \geq 3 and t \geq 1, \mathrm{Ryser}(r,t,k) = \lfloor (r - t)/k \rfloor + 1.

It is quite interesting that the sharp bound that we prove in Theorem 1 is precisely what was needed for Theorem 2.

In our paper, we prove various other things, which includes showing the bound \mathrm{Ryser}(r,t) \leq r - t for a larger range of values of t, and the same bound for strictly t-intersecting hypergraphs for a much larger range of values of t. We also pose some nice open problems, and make the following bold conjecture (that only a proper subset of us believe):

Conjecture. \mathrm{Ryser}(r,t) = \lfloor (r - t)/2 \rfloor + 1 for all 2 \leq t \leq r - 1.

I can definitely say that despite our beliefs all of us would be happy to see a counterexample to this Conjecture.

We also introduce another variation of the problem where instead of a normal vertex cover, one looks at s-covers, that is, every edge must share at least s vertices with the covering set. Here we make some modest progress and hope that it will inspire some future work.

About Anurag Bishnoi

A mathematician working at TU Delft. I am broadly interested in combinatorics and finite geometry.
This entry was posted in Combinatorics, Extremal Combinatorics and tagged , , , , , , , . Bookmark the permalink.

1 Response to Extending Ryser’s conjecture

  1. Pingback: The dual version of Ryser’s conjecture | Anurag's Math Blog

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