Premium
Large monochromatic components in 3‐edge‐colored Steiner triple systems
Author(s) -
DeBiasio Louis,
Tait Michael
Publication year - 2020
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/jcd.21707
Subject(s) - monochromatic color , combinatorics , mathematics , disjoint sets , upper and lower bounds , hypergraph , steiner system , triple system , discrete mathematics , colored , enhanced data rates for gsm evolution , pure mathematics , computer science , physics , mathematical analysis , telecommunications , optics , materials science , composite material
It is known that in any r ‐coloring of the edges of a complete r ‐uniform hypergraph, there exists a spanning monochromatic component. Given a Steiner triple system on n vertices, what is the largest monochromatic component one can guarantee in an arbitrary 3‐coloring of the edges? Gyárfás proved that( 2 n + 3 ) / 3 is an absolute lower bound and that this lower bound is best possible for infinitely many n . On the other hand, we prove that for almost all Steiner triple systems the lower bound is actually ( 1 − o ( 1 ) ) n . We obtain this result as a consequence of a more general theorem which shows that the lower bound depends on the size of a largest 3‐ partite hole (ie, disjoint sets X 1 , X 2 , X 3 with| X 1 | = | X 2 | = | X 3 |such that no edge intersects all of X 1 , X 2 , X 3 ) in the Steiner triple system (Gyárfás previously observed that the upper bound depends on this parameter). Furthermore, we show that this lower bound is tight unless the structure of the Steiner triple system and the coloring of its edges are restricted in a certain way. We also suggest a variety of other Ramsey problems in the setting of Steiner triple systems.