Search

The existence of Steiner triple systems STS(n) of order n containing no nontrivial subsystem is well known for every admissible n. We generalize this result in two ways. First we define the expander property of 3-uniform hypergraphs and show the existence of Steiner triple systems which are almost perfect expanders. Next we define the strong and weak spreading property of linear hypergraphs, and determine the minimum size of a linear triple system with these properties, up to a small constant factor. A linear triple system on a vertex set V has the spreading, or respectively weakly spreading property if any sufficiently large subset V 0 ⊂ V contains a pair of vertices with which a vertex of V rV 0 forms a triple of the system. Here the condition on V 0 refers to jV 0j 4 or V 0 is the support of more than one triples, respectively. This property is strongly connected to the connectivity of the structure the so-called inuence maximisation. We also discuss how the results are related to Erd}os' conjecture on locally sparse STSs, subsquare-free Latin-squares and possible applications in finite geometry. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

In this paper we study Turán and Ramsey numbers in linear triple systems, defined as 3-uniform hypergraphs in which any two triples intersect in at most one vertex. A famous result of Ruzsa and Szemerédi is that for any fixed c > 0 and large enough n the following Turán-type theorem holds. If a linear triple system on n vertices has at least c n 2 edges then it contains a triangle : three pairwise intersecting triples without a common vertex. In this paper we extend this result from triangles to other triple systems, called s -configurations. The main tool is a generalization of the induced matching lemma from a b a -patterns to more general ones. We slightly generalize s -configurations to extended s -configurations. For these we cannot prove the corresponding Turán-type theorem, but we prove that they have the weaker, Ramsey property: they can be found in any t -coloring of the blocks of any sufficiently large Steiner triple system. Using this, we show that all unavoidable configurations with at most 5 blocks, except possibly the ones containing the sail C 15 (configuration with blocks 123, 345, 561 and 147), are t -Ramsey for any t ≥ 1. The most interesting one among them is the wicket , D 4 , formed by three rows and two columns of a 3 × 3 point matrix. In fact, the wicket is 1-Ramsey in a very strong sense: all Steiner triple systems except the Fano plane must contain a wicket. [ABSTRACT FROM AUTHOR]

The existence of Steiner triple systems STS (n) of order n containing no nontrivial subsystem is well known for every admissible n. We generalize this result in two ways. First we define the expander property of 3-uniform hypergraphs and show the existence of Steiner triple systems which are almost perfect expanders. Next we define the strong and weak spreading properties of linear hypergraphs, and determine the minimum size of a linear triple system with these properties, up to a small constant factor. This property is strongly connected to the connectivity of the structure and of the so-called influence maximization. We also discuss how the results are related to Erdős' conjecture on locally sparse STS s, influence maximization, subsquare-free Latin squares and possible applications in finite geometry. [ABSTRACT FROM AUTHOR]