Gyárfás–Lehel covering conjecture for cross-intersecting partite hypergraphs

Let AA and BB be non-empty cross-intersecting hypergraphs: every edge of AA meets every edge of BB. Suppose both are rr-partite and share the same rr-partition. A cover of ABA\cup B is a set of vertices meeting every edge, and τ(AB)\tau(A\cup B) denotes its minimum size.

Gyárfás–Lehel conjecture. Then

τ(AB)2r2.\tau(A\cup B)\leqslant 2r-2.

The bound improves the elementary bound obtained from the union of one edge of each hypergraph. The source presents this as open and notes that the bound is tight if true.

Sources & referencesView supporting material

Primary source

Ron Aharoni, Eli Berger, Joseph Briggs, He Guo and Shira Zerbib, “Looms”, arXiv:2309.03735 (2024).

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.