Linear-edge construction conjecture for sparse intersecting hypergraphs

For each positive integer rr, let f(r)f(r) be the minimum number of edges in an rr-partite intersecting hypergraph H\mathcal{H} satisfying τ(H)r1\tau(\mathcal{H}) \geq r-1.

Linear-edge construction conjecture. The function f(r)f(r) grows linearly:

f(r)=Θ(r).f(r)=\Theta(r).

The paper proves the lower bound f(r)(31/18)r(1o(1))2.764r(1o(1))f(r)\geq (3-1/\sqrt{18})r(1-o(1))\approx 2.764r(1-o(1)), but has no matching upper bound; the conjecture asks for constructions with a linear number of edges.

Sources & referencesView supporting material

Primary source

Toufik Mansour, Chunwei Song and Raphael Yuster, “A comment on Ryser's conjecture for intersecting hypergraphs”, arXiv:0709.3138 (2007).

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.