Back to Search
Start Over
Turán and Ramsey numbers in linear triple systems.
- Source :
-
Discrete Mathematics . Mar2021, Vol. 344 Issue 3, pN.PAG-N.PAG. 1p. - Publication Year :
- 2021
-
Abstract
- 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]
- Subjects :
- *RAMSEY numbers
*STEINER systems
*LINEAR systems
*HYPERGRAPHS
Subjects
Details
- Language :
- English
- ISSN :
- 0012365X
- Volume :
- 344
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 148045625
- Full Text :
- https://doi.org/10.1016/j.disc.2020.112258