Pith. sign in

REVIEW

Ryser's Conjecture for t-intersecting hypergraphs

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2001.04132 v2 pith:DI2O66K2 submitted 2020-01-13 math.CO

Ryser's Conjecture for t-intersecting hypergraphs

classification math.CO
keywords conjectureintersectingcoverhypergraphsmathcalnumberhypergraphbounds
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved
0 comments
read the original abstract

A well-known conjecture, often attributed to Ryser, states that the cover number of an $r$-partite $r$-uniform hypergraph is at most $r - 1$ times larger than its matching number. Despite considerable effort, particularly in the intersecting case, this conjecture remains wide open, motivating the pursuit of variants of the original conjecture. Recently, Bustamante and Stein and, independently, Kir\'{a}ly and T\'{o}thm\'{e}r\'{e}sz considered the problem under the assumption that the hypergraph is $t$-intersecting, conjecturing that the cover number $\tau(\mathcal{H})$ of such a hypergraph $\mathcal{H}$ is at most $r - t$. In these papers, it was proven that the conjecture is true for $r \leq 4t-1$, but also that it need not be sharp; when $r = 5$ and $t = 2$, one has $\tau(\mathcal{H}) \leq 2$. We extend these results in two directions. First, for all $t \geq 2$ and $r \leq 3t-1$, we prove a tight upper bound on the cover number of these hypergraphs, showing that they in fact satisfy $\tau(\mathcal{H}) \leq \lfloor(r - t)/2 \rfloor + 1$. Second, we extend the range of $t$ for which the conjecture is known to be true, showing that it holds for all $r \leq \frac{36}{7}t-5$. We also introduce several related variations on this theme. As a consequence of our tight bounds, we resolve the problem for $k$-wise $t$-intersecting hypergraphs, for all $k \geq 3$ and $t \geq 1$. We further give bounds on the cover numbers of strictly $t$-intersecting hypergraphs and the $s$-cover numbers of $t$-intersecting hypergraphs.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.