Yuster's hypergraph independent transversal asymptotic conjecture

About 6 years old · traced to

For integers n,k,r,sn,k,r,s, let f(k,r,s)f(k,r,s) be the extremal function for independent transversals in (n,k,r,s)(n,k,r,s)-graphs. Fix r≥3r\ge 3. Yuster's conjecture. For all 1≤s≤k1\le s\le k,

f(k,r,s)=(r−1+ok(1))krsr−1.f(k,r,s)=(r-1+o_k(1))\sqrt[r-1]{\frac{k^r}{s}}.

The paper proves the asserted order of magnitude when s≥(r−1)!s\ge (r-1)!, and proves the corresponding upper bound for s≥Clog⁡ks\ge C\log k, but the full range, especially small ss, remains open.

References

Primary source

Stefan Glock and Benny Sudakov, “An average degree condition for independent transversals”, arXiv:2003.01683 (2022).

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.