In an earlier post, I talked about Ryser’s conjecture on -partite -uniform hypergraphs, that has stayed open for all 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 . Therefore, it is quite natural to look for simpler problems by adding more restrictions. One of the restrictions is to consider strictly -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 .
Here are two alternate conditions one could impose that are stronger than the hypergraph being intersecting:
- (-wise intersection) any collection of edges contains a common vertex.
- (-intersection) any two distinct edges have at least vertices in common.
Note that in (1.) we can have repetitions in the collection of edges, and thus in particular -wise intersection implies -wise intersection for any .
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 . 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:
where is the vertex cover number of , that is, the smallest number of vertices that cover all edges.
Ryser’s conjecture (for intersecting hypergraphs) states that (note that every edges is a vertex cover, and hence is trivially true). If true, this bound will be sharp for infinitely many values of .
The problem of determining was introduced a few years back independently by Bustamante–Stein, and Király–Tóthmérész, who made an analogous conjecture for this function that says . While Ryser’s conjecture is a special case of this one, it is in fact implied by Ryser’s conjecture, that is, . Therefore, one might hope to make progress over this new conjecture for larger values of , even though seems out of reach at the moment. This is what was done, as Bustamante and Stein proved the conjecture for whereas Király and Tóthmérész proved it for . Moreover, Bustamante and Stein observed that their conjecture is not sharp as instead of being equal to . 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:
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 , the correct value of is in fact half of what was conjectured:
Theorem 1. , for all .
Once we came back to Berlin from our workshop, Shagnik joined our team:
He proved that Theorem 1 in fact implies the following result on the function
Theorem 2. For any and , .
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 for a larger range of values of , and the same bound for strictly -intersecting hypergraphs for a much larger range of values of . We also pose some nice open problems, and make the following bold conjecture (that only a proper subset of us believe):
Conjecture. for all .
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 -covers, that is, every edge must share at least vertices with the covering set. Here we make some modest progress and hope that it will inspire some future work.