Degree-sequence conditions for r-Hamiltonian hypergraphs

At least 11 years old · documented by

Let (d1,d2,…,dn)(d_1,d_2,\ldots,d_n) be an integer sequence with

d1≤d2≤⋯≤dn,d_1\leq d_2\leq \dots\leq d_n,

where n>2rn>2r and r≥3r\geq 3. A hypergraph is rr-Hamiltonian if it remains Hamiltonian after the deletion of any set of fewer than rr vertices. Degree-sequence conjecture. If

di>ifor 1≤i<r,d_i>i \qquad\text{for }1\leq i<r,

if

di≤(ir−1)thendn−i>(n−i−1r−1)for r≤i≤⌊n−12⌋,d_i\leq \binom{i}{r-1}\quad\text{then}\quad d_{n-i}>\binom{n-i-1}{r-1}\qquad\text{for }r\leq i\leq\left\lfloor\frac{n-1}{2}\right\rfloor,

and, when nn is even, if

dn−22≤(n−22r−1)+1,d_{\frac{n-2}{2}}\leq \binom{\frac{n-2}{2}}{r-1}+1,

then

dn+22>(n2−2r−1)+(n2+1)(n2−2r−2),d_{\frac{n+2}{2}}>\binom{\frac{n}{2}-2}{r-1}+\left(\frac{n}{2}+1\right)\binom{\frac{n}{2}-2}{r-2},

then the sequence is rr-Hamiltonian. This proposes degree-sequence conditions that would generalize Chvátal's theorem to hypergraphs; the authors expect Chvátal's condition to be sufficient but not necessary in this setting.

References

Primary source

Nika Salia, “Pósa-type results for Berge-hypergraphs”, arXiv:2111.06710 (2024).

Additional references

2 papers in this index state this conjecture (2014–2021). The statement above is taken from the most recent of them; the others are arXiv:1406.3229.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.