The extremal conjecture for tight paths and cycles in uniform hypergraphs

Let kk-graphs be kk-uniform hypergraphs, and let nn and \ell be positive integers. A tight path on \ell vertices is a sequence of \ell distinct vertices in which every set of kk consecutive vertices forms an edge; a tight cycle is defined cyclically in the analogous way.

Extremal conjecture for tight paths and cycles. For any \ell, every nn-vertex kk-graph with more than

kk(nk1)\frac{\ell-k}{k}\binom{n}{k-1}

edges contains a tight path on \ell vertices, and every nn-vertex kk-graph with more than

1k(n1k1)\frac{\ell-1}{k}\binom{n-1}{k-1}

edges contains a tight cycle of length at least \ell.

This is proposed as the exact analogue for tight paths and cycles of the Erdős–Gallai theorem, complementing the paper's approximate extremal result. The conjecture concerns the sharp edge thresholds for forcing these structures; its resolution is not specified in the source.

Sources & referencesView supporting material

Primary source

Peter Allen, Julia Böttcher, Oliver Cooley and Richard Mycroft, “Tight cycles and regular slices in dense hypergraphs”, arXiv:1411.4957 (2014).

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.