Turán Numbers for 3-Uniform Linear Paths of Length 3

Eliza Jackowska, Joanna Polcyn, Andrzej Ruciński


In this paper we confirm a special, remaining case of a conjecture of Füredi, Jiang, and Seiver, and determine an exact formula for the Turán number $\mathrm{ex}_3(n; P_3^3)$ of the 3-uniform linear path $P^3_3$ of length 3, valid for all $n$. It coincides with the analogous formula for the 3-uniform triangle $C^3_3$, obtained earlier by Frankl and Füredi for $n\ge 75$ and Csákány and Kahn for all $n$. In view of this coincidence, we also determine a `conditional' Turán number, defined as the maximum number of edges in a $P^3_3$-free 3-uniform hypergraph on $n$ vertices which is not $C^3_3$-free.


Hypergraphs, Linear paths, Turán numbers

Full Text: PDF