The Exact Linear Turán Number of the Sail

Beka Ergemlidze, Ervin Győri, Abhishek Methuku

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Article numberP4.39
JournalElectronic Journal of Combinatorics
Volume28
Issue number4
DOIs
StatePublished - 2021
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'The Exact Linear Turán Number of the Sail'. Together they form a unique fingerprint.

Cite this