Győri–Katona–Lemons conjecture for Berge paths in uniform hypergraphs

From papers

Let rr and kk satisfy k=r+1>2k=r+1>2, and let H\mathcal{H} be an rr-uniform hypergraph, meaning that every hyperedge has size rr. A Berge path of length kk consists of kk distinct hyperedges e1,,eke_1,\dots,e_k and k+1k+1 distinct vertices v1,,vk+1v_1,\dots,v_{k+1} such that vi,vi+1eiv_i,v_{i+1}\in e_i for each 1ik1\leq i\leq k. Write e(H)=E(H)e(\mathcal{H})=|E(\mathcal{H})| and n=n(H)=V(H)n=n(\mathcal{H})=|V(\mathcal{H})|. Győri–Katona–Lemons conjecture. If H\mathcal{H} contains no Berge path of length kk, then

e(H)nk(kr)=n.e(\mathcal{H})\leq \frac{n}{k}\binom{k}{r}=n.

This conjecture is the remaining case of the Győri–Katona–Lemons extension of the Erdős–Gallai theorem for uniform hypergraphs; the paper settles it by proving that an rr-uniform hypergraph with more than nn edges contains a Berge path of length r+1r+1.

Progress summary

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

Sources & referencesView supporting material

Primary source

Akbar Davoodi, Ervin Győri, Abhishek Methuku and Casey Tompkins, “An Erdős-Gallai type theorem for uniform hypergraphs”, arXiv:1608.03241 (2017).

Solutions 0

No solutions have been posted yet.