Turán problems and shadows I: Paths and cycles

A k-path   is a hypergraph Pk={e1,e2,…,ek}Pk={e1,e2,…,ek} such that |ei∩ej|=1|ei∩ej|=1 if |j−i|=1|j−i|=1 and ei∩ej=∅ei∩ej=∅ otherwise. A k-cycle   is a hypergraph Ck={e1,e2,…,ek}Ck={e1,e2,…,ek} obtained from a (k−1)(k−1)-path {e1,e2,…,ek−1}{e1,e2,…,ek−1} by adding an edge ekek that shares one vertex with e1e1, another vertex with ek−1ek−1 and is disjoint from the other edges.Let exr(n,G)exr(n,G) be the maximum number of edges in an r-graph with n vertices not containing a given r-graph G  . We prove that for fixed r≥3r≥3, k≥4k≥4 and (k,r)≠(4,3)(k,r)≠(4,3), for large enough n:exr(n,Pk)=exr(n,Ck)=(nr)−(n−⌊k−12⌋r)+{0if k is odd(n−⌊k−12⌋−2r−2)if k is even and we characterize all the extremal r  -graphs. We also solve the case (k,r)=(4,3)(k,r)=(4,3), which needs a special treatment. The case k=3k=3 was settled by Frankl and Füredi.This work is the next step in a long line of research beginning with conjectures of Erdős and Sós from the early 1970s. In particular, we extend the work (and settle a conjecture) of Füredi, Jiang and Seiver who solved this problem for PkPk when r≥4r≥4 and of Füredi and Jiang who solved it for CkCk when r≥5r≥5. They used the delta system method, while we use a novel approach which involves random sampling from the shadow of an r-graph.