Abstract
A hypergraph is linear if any two of its edges intersect in at most one vertex. The sail (or 3-fan) F3 is the 3-uniform linear hypergraph consisting of 3 edges f1, f2, f3 pairwise intersecting in the same vertex v and an additional edge g intersecting each fi in a vertex different from v. The linear Turán number exlin(n, F3) is the maximum number of edges in a 3-uniform linear hypergraph on n vertices that does not contain a copy of F3. Füredi and Gyárfás proved that if n = 3k, then exlin(n, F3) = k2 and the only extremal hypergraphs in this case are transversal designs. They also showed that if n = 3k + 2, then exlin(n, F3) = k2 + 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 exlin(n, F3) = k2 + 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.
Original language | English (US) |
---|---|
Article number | P4.39 |
Journal | Electronic Journal of Combinatorics |
Volume | 28 |
Issue number | 4 |
DOIs | |
State | Published - 2021 |
Externally published | Yes |
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Applied Mathematics