Large monochromatic components in 3‐edge‐colored Steiner triple systems
2020
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?
Gyarfas proved that $(2n+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 \emph{3-partite hole} (that is, 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 (Gyarfas previously observed that the upper bound depends on this parameter). Furthermore, we show that this lower bound is tight unless the coloring has a particular structure.
We also suggest a variety of other Ramsey problems in the setting of Steiner triple systems.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
18
References
3
Citations
NaN
KQI