For almost all Steiner triple systems on n vertices, every 3-edge-coloring has a monochromatic component on (1-o(1))n vertices.
Spreading linear triple systems and expander triple systems
1 Pith paper cite this work. Polarity classification is still indexing.
abstract
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. 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\H{o}s' conjecture on locally sparse STSs, influence maximization, subsquare-free Latin squares and possible applications in finite geometry.
fields
math.CO 1years
2019 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Large monochromatic components in 3-edge-colored Steiner triple systems
For almost all Steiner triple systems on n vertices, every 3-edge-coloring has a monochromatic component on (1-o(1))n vertices.