Linear Turán numbers of acyclic triple systems. (January 2022)

• Record Type: Journal Article
• Authors: Gyárfás, András; Ruszinkó, Miklós; Sárközy, Gábor N.
• Is Part Of: European journal of combinatorics. Volume 99(2022)
• Publication Date: 2022-01
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2021.103435
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: The Turán number of hypergraphs has been studied extensively. Here we deal with a recent direction, the linear Turán number, and restrict ourselves to linear triple systems, a collection of triples on a set of points in which any two triples intersect in at most one point. For a fixed linear triple system F, the linear Turán number ex L ( n, F ) is the maximum number of triples in a linear triple system with n points that does not contain F as a subsystem. We initiate the study of the linear Turán number for an acyclic F . In this case ex L ( n, F ) is linear in n and we aim for good bounds. Since the case of trees is already difficult for graphs (Erdős–Sós conjecture), we concentrate on matchings, paths and small trees. In case of matchings, where M k is the set of k pairwise disjoint triples, we prove that for fixed k and large enough n, ex L ( n, M k ) = f ( n, k ) where f ( n, k ) is the maximum number of triples that can meet k − 1 points in a linear triple system on n points. This is an analogue of an old result of Erdős on hypergraph matchings. For the k -edge linear path P k we show (extending some standard path increasing methods used for graphs) that ex L ( n, P k ) ≤ 1 . 5 k n which is probably far from best possible. Finding ex L ( n, F ) relates to difficult problems on Steiner triple systems and interesting even for small trees. For example, for P 4, the path with four triples, ex L ( n, P 4 ) ≤ 4 n 3 with equality only for disjoint union of affine planes of order 3. On the other hand, for E 4, the tree having three pairwise disjoint triples and a fourth one meeting all of them, we have bounds only: 6 ⌊ n − 3 4 ⌋ ≤ ex L ( n, E 4 ) ≤ 2 n .