The exact linear Turán number of the sail

Beka Ergemlidze¹ ; Ervin Győri² ; Abhishek Methuku³

¹Renyi Institute
²Alfréd Rényi Institute of Mathematics
³University of Birmingham

The electronic journal of combinatorics, Tome 28 (2021) no. 4

Résumé

A hypergraph is linear if any two of its edges intersect in at most one vertex. The sail (or $3$-fan) $F^3$ is the $3$-uniform linear hypergraph consisting of $3$ edges $f_1, f_2, f_3$ pairwise intersecting in the same vertex $v$ and an additional edge $g$ intersecting each $f_i$ in a vertex different from $v$. The linear Turán number $\mathrm{ex}_{\mathrm{lin}}(n, F^3)$ is the maximum number of edges in a $3$-uniform linear hypergraph on $n$ vertices that does not contain a copy of $F^3$. Füredi and Gyárfás proved that if $n = 3k$, then $\mathrm{ex}_{\mathrm{lin}}(n, F^3) = k^2$ and the only extremal hypergraphs in this case are transversal designs. They also showed that if $n = 3k+2$, then $\mathrm{ex}_{\mathrm{lin}}(n, F^3) = k^2+k$, and the only extremal hypergraphs are truncated designs (which are obtained from a transversal design on $3k+3$ vertices with $3$ groups by removing one vertex and all the hyperedges containing it) along with three other small hypergraphs. However, the case when $n =3k+1$ was left open. In this paper, we solve this remaining case by proving that $\mathrm{ex}_{\mathrm{lin}}(n, F^3) = k^2+1$ if $n = 3k+1$, answering a question of Füredi and Gyárfás. We also characterize all the extremal hypergraphs. The difficulty of this case is due to the fact that these extremal examples are rather non-standard. In particular, they are not derived from transversal designs like in the other cases.

Détail

DOI : 10.37236/9904

Classification : 05C30, 05C65
Mots-clés : \(3\)-uniform linear hypergraph