  A $k$-path is a hypergraph P_k = e_1,e_2,...,e_k such that |e_i \cap e_j| = 1
if |j - i| = 1 and e_i \cap e_j is empty otherwise. A k-cycle is a hypergraph
C_k = e_1,e_2,.. ,e_k obtained from a (k-1)-path e_1,e_2,...,e_{k-1} by adding
an edge e_k that shares one vertex with e_1, another vertex with e_{k-1} and is
disjoint from the other edges.
  Let ex_r(n,G) be the maximum number of edges in an r-graph with n vertices
not containing a given r-graph G. We determine ex_r(n, P_k) and ex_r(n, C_k)
exactly for all k \ge 4 and r \ge 3 and $n$ sufficiently large and also
characterize the extremal examples. The case k = 3 was settled by Frankl and
F\"{u}redi.
  This work is the next step in a long line of research beginning with
conjectures of Erd\H os and S\'os from the early 1970's. In particular, we
extend the work (and settle a recent conjecture) of F\"uredi, Jiang and Seiver
who solved this problem for P_k when r \ge 4 and of F\"uredi and Jiang who
solved it for C_k when r \ge 5. They used the delta system method, while we use
a novel approach which involves random sampling from the shadow of an r-graph.

Combinatorics