Large monochromatic components in 3‐edge‐colored Steiner triple systems

DOI10.1002/JCD.21707MaRDI QIDQ6187431zbMATH OpenOpenAlexFDO

Authors Louis DeBiasio, Michael Tait

Publication date 31 January 2024

Published in Journal of Combinatorial Designs (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1908.00837

zbMATH Keywords

Ramsey problemSteiner triple system

Mathematics Subject Classification ID

Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55)

Abstract: 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'arf'as 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 (Gy'arf'as 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.

Recommendations

• Large monochromatic components in colorings of complete 3-uniform hypergraphs
• Large monochromatic components in colorings of complete hypergraphs
• Large monochromatic components in 3-colored non-complete graphs
• Large monochromatic components in expansive hypergraphs
• Monochromatic components in edge-coloured graphs with large minimum degree

Cites work

• Almost all Steiner triple systems are almost resolvable
• Almost all Steiner triple systems have perfect matchings
• Bicoloring Steiner triple systems
• Covering \(t\)-element sets by partitions
• Density of monochromatic infinite subgraphs
• Discrepancy of high-dimensional permutations
• scientific article; zbMATH DE number 4014740 (Why is no real title available?)
• scientific article; zbMATH DE number 15490 (Why is no real title available?)
• scientific article; zbMATH DE number 1314686 (Why is no real title available?)
• scientific article; zbMATH DE number 1380583 (Why is no real title available?)
• Large cross-free sets in Steiner triple systems
• Large monochromatic components and long monochromatic cycles in random hypergraphs
• Large monochromatic components in colorings of complete 3-uniform hypergraphs
• On independent sets in hypergraphs
• On the independence number of Steiner systems
• On the method of typical bounded differences
• On uncrowded hypergraphs
• The Chromatic Number of Kneser Hypergraphs
• The minimum independence number for designs
• The Ramsey number for hypergraph cycles. I.

Cited in

(2)

• Large monochromatic components in colorings of complete hypergraphs
• Large monochromatic components in expansive hypergraphs

This page was built for publication: Large monochromatic components in 3‐edge‐colored Steiner triple systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6187431)