## Large monochromatic components in 3-edge-colored Steiner triple systems

Louis DeBiasio , Michael Tait 1 2

February 11, 2020

## 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´s [14] proved that (2 a 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 (that is, disjoint sets X ,X ,X 1 2 3 with | X 1 | = | X 2 | = | X 3 | such that no edge intersects all of X ,X ,X 1 2 3 ) in the Steiner triple system (Gy´ arf´s a 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.

## 1 Introduction

Given a hypergraph H , let H (2) be the shadow-graph of H ; that is, the 2-uniform hypergraph on V ( H ) where { x, y } ∈ E H ( (2) ) if and only if there exists e ∈ E H ( ) such that { x, y } ⊆ e . We say that H is connected if H (2) is connected. The components of H are the maximal connected subgraphs of H . Given an r -coloring of H (which for the purposes of this paper means a partition { E , . . . , E 1 r } of E H ( ) where we allow for some of the sets in the partition to be be empty) a monochromatic component of H is a component of the hypergraph H i = ( V ( H ,E ) i ) for some i ∈ [ r ].

1 Department of Mathematics, Miami University debiasld@miamioh.edu . Research supported in part by Simons Foundation Collaboration Grant # 283194.

2 Department of Mathematics &amp; Statistics, Villanova University michael.tait@villanova.edu . Research supported in part by National Science Foundation Grant DMS-2011553.

For a hypergraph H , let mc ( r H ) be the largest integer m such that in every r -coloring of the edges of H , there exists a monochromatic component on at least m vertices. It is well known [13] that for all r ≥ 2, mc ( r K r n ) = n where K r n is the complete r -uniform hypergraph on n vertices (when r = 2 this is equivalent to the statement 'a graph or its complement is connected').

First note that for any hypergraph H , we have mc ( r H ) ≥ mc ( r H (2) ). So if H has the property that every pair of vertices is contained in at least one edge, then mc ( r H ) ≥ mc ( r K n ) ≥ n r 1 , where the last inequality holds by a well-known result of Gy´rf´s [13]. a a

This question unexpectedly led to the consideration of the following independence-type parameter. Given a hypergraph H on n vertices, let α ∗ k ( H ) be the maximum integer a ∗ k such that there exist disjoint sets X ,X ,... , X 1 2 k ⊆ V ( H ) with | X 1 | = | X 2 | = · · · = | X k | = a ∗ k such that for all e ∈ E H ( ), e ∩ X i = ∅ for some i ∈ [ k ]. We call the sets X ,.. . , X 1 k a k -partite hole and we say α ∗ k is the k -partite-hole number of H . Note that since the sets are disjoint, we trivially have α ∗ k ( H ) ≤ n k .

-A Steiner triple system is a 3-uniform hypergraph in which each pair of vertices is contained in exactly one edge, and it is well-known that a Steiner triple system on n vertices exists if and only if n ≡ 1 3 mod 6. Given a Steiner triple system , S , we sometimes write | S | to denote the number of vertices in S and we note that the number of edges in S is exactly 1 3 ( | S | 2 ) = | S | ( | S |-1) 6 . For n ≡ 1 3 mod 6, let , S n be the family of all Steiner triple systems on n vertices. The purpose of this paper is to address the following question: Given S ∈ S n , what is the value of mc ( 3 S )? Note that by the observation in the previous paragraph, we trivially have mc ( 3 S ) ≥ n 2 for all S ∈ S n .

We begin by noting the following simple upper bound on mc ( k H ) for all k -uniform hypergraphs H (essentially, this example was observed earlier in a more restricted form for the case of Steiner triple systems by Gy´rf´s [14, Lemma 3]). a a

Proposition 1.1. For all k -uniform hypergraphs H , mc ( k H ) ≤ n -α ∗ k ( H ) .

Proof. Let a k := α ∗ k ( H ). Let X ,X ,... , X 1 2 k ⊆ V ( H ) with | X 1 | = | X 2 | = · · · = | X k | = a k such that for all e ∈ E H ( ), e ∩ X i = ∅ for some i ∈ [ r ]. Color every edge which avoids X i with color i for all i ∈ [ k ]. Note that every component of color i avoids X i , so mc ( k H ) ≤ n -a k .

After a draft of this paper appeared on arXiv, we were made aware of the fact that this problem and the above connection between the two parameters had been studied earlier by Gy´ arf´s [14] (what we call a 3-partite hole, he calls a 'cross'). a He proved the following:

Theorem 1.2 (Gy´ arf´s [14, Theorem 1, Lemma 3, Theorem 4]) a .

- (i) For n ≡ 1 3 mod 6 , , min mc ( S ∈S n 3 S ) ≥ 2 n/ 3 + 1 .
- (iii) For n ≡ 3 mod 18 , max S ∈S n α ∗ 3 ( S ) = n/ 3 -1 ; consequently, min mc ( S ∈S n 3 S ) = 2 n/ 3 + 1 .
- (ii) For n ≡ 1 3 mod 6 , , min mc ( S ∈S n 3 S ) ≤ n -max S ∈S n α ∗ 3 ( S ) .

Our work can now be viewed as an extension of the results in [14]. In Theorem 1.2(i), Gy´ arf´s proves an absolute lower bound on mc ( a 3 S ). Our first main result is a lower bound on mc ( 3 S ) in terms of α ∗ 3 ( S ).

Theorem 1.3. For all S ∈ S n , mc ( 3 S ) ≥ n -2 α ∗ 3 ( S ) .

In Theorem 2.3 we will prove a stronger statement which, together with Proposition 1.1, shows that either mc 3 ( S ) = n -α ∗ 3 ( S ), or else the structure of S and the coloring of its edges are restricted in a certain way. As a corollary of Theorem 2.3 we recover Theorem 1.2(i).

We then use Theorem 1.3 together with some recent methods developed by Kwan [19] to prove that for almost every S ∈ S n , we have mc ( 3 S ) = (1 -o (1)) n .

Theorem 1.4. There exists a constant δ &gt; 0 such that for n ≡ 1 3 mod 6 , , if S ∈ S n is chosen uniformly at random, then a.a.s.

$$\mathrm m c _ { 3 } ( S ) \geq n - 2 n ^ { 1$$

Additionally, in the process of proving Theorem 1.4, we answer a problem raised in [14, Problem 8] (see Theorem 3.1 and the discussion which follows for more details) by showing that for all sufficiently large n ≡ 1 3 mod , n , there exists S ∈ S n such that α ∗ ( S ) is small (sublinear) and there exists S ∈ S n such that α ∗ ( S ) is large (linear).

In Corollary 2.1, we observe that for all S ∈ S n , mc ( 3 S ) ≤ n -. 417 3 √ n log n . Thus it would be interesting to determine whether the lower bound in Theorem 1.4 can be improved to n -O ( √ n log n ) (see Problem 3.6).

## 1.1 Overview of the paper

In Section 2, we prove some general results giving bounds on mc ( r H ) for H an r -uniform hypergraph. We deduce an upper bound on mc ( 3 S ) for all Steiner triple systems S . We also prove a result which we will later use to deduce lower bounds on mc ( 3 S ). We additionally give results on mc ( r H ) when H is a random r -uniform hypergraph.

In Section 3, we prove Theorem 1.4, that almost all Steiner triple systems S satisfy mc ( 3 S ) = (1 -o (1)) | S | .

In Section 5, we prove that there exists an infinite family of Steiner triple systems S such that mc ( 3 S ) = (2 / 3 + o (1)) | S | for all S ∈ S .

In Section 4, we prove an absolute lower bound on mc ( 3 S ) for all Steiner triple systems S , namely that mc ( 3 S ) ≥ 2 | S | 3 +1.

In Section 6, we discuss bounds on mc ( 3 S ) for Bose and Skolem triple systems S .

Finally, in Section 7, we raise a number of Ramsey-type problems in the setting of Steiner triple systems.

## 2 General bounds for hypergraphs

/negationslash

An independent set in a hypergraph H is a set A ⊆ V ( H ) such for all e ∈ E H ( ), e ⊆ A . Given a hypergraph H , let α H ( ) be the maximum integer a such that H contains an independent set of order a . Note that for any k -uniform hypergraph H we have α ∗ k ( H ) ≥ /floorleft α H /k ( ) /floorright , since an independent set in H of order α H ( ) contains k disjoint sets of each of order /floorleft α H /k ( ) /floorright . However, there are hypergraphs H for which α ∗ k ( H ) is arbitrarily larger

than α H ( ). For instance, take k disjoint sets of size n/k and add all edges except those which touch all k of the sets, then α H ( ) = k , but α ∗ k ( H ) = n/k .

Note that for all n ≡ 1 3 mod 6 such that , n &gt; 3 and all S ∈ S n , we trivially have α ∗ 3 ( S ) ≥ 1 and thus mc ( 3 S ) ≤ n -1 (c.f. mc ( 3 K 3 n ) = n ). Phelps and R¨ odl [21] showed that there exists a constant c such that for all S ∈ S n , α S ( ) ≥ c √ n log n (in fact they proved this for all linear 3-uniform hypergraphs). The constant was improved in [7] and improved further to . 417 in [17]. Combining this lower bound with Proposition 1.1 we get the following corollary.

$$\begin{array} {$$

Grable, Phelps, and R¨dl [12] proved that the lower bound on the independence number o given above is best possible up to the constant term; that is, there exists an infinite family of Steiner triple systems S and a constant C such that α S ( ) ≤ C √ | S | log | S | , for all S ∈ S (in [9], it is mentioned that one can take C = √ 3).

Given a hypergraph H and { u, v } ∈ ( V ( H ) 2 ) , let d u, v ( ) = |{ S ∈ E H ( ) : { u, v } ⊆ S }| and let δ 2 ( H ) = min { d u, v ( ) : { u, v } ∈ ( V ( H ) 2 ) } . We will prove a lower bound on mc ( 3 H ) for all 3-uniform hypergraphs H with δ 2 ( H ) ≥ 1 (i.e. every pair of vertices is contained in at least one edge). We use the following lemma from [8] which we reproduce here for completeness (for technical reasons we allow for edges to receive multiple colors, so we have modified the statement of the lemma accordingly).

More recently, Linial and Luria [20, Theorem 1.6] proved (using different terminology) that exists an infinite family of Steiner triple systems S such that α ∗ 3 ( S ) ≤ 100 √ | S | log | S | for all S ∈ S .

Lemma 2.2. Let K be a complete graph. For every 3-multicoloring of the edges of K , either

- (L ) 1 there exists a spanning monochromatic component, or
- (L ) 2 there exists a partition { W,X,Y,Z } of V ( K ) (all parts non-empty), such that every edge in [ W,X ] and [ Y, Z ] is colored only with blue, every edge in [ W,Y ] and [ X,Z ] is colored only with red, and every edge in [ W,Z ] and [ X,Y ] is colored only with green.
- (L ) 3 there exists a partition { W,X,Y,Z } of V ( K ) with X,Y,Z non-empty such that B := W ∪ X ∪ Y is connected in blue, R := W ∪ X ∪ Z is connected in red, and G := W ∪ Y ∪ Z is connected in green. Furthermore, every edge in [ X,Y ] is colored only with blue, every edge in [ X,Z ] is colored only with red, and every edge in [ Y, Z ] is colored only with green, whereas no edge in [ W,X ] is green, no edge in [ W,Y ] is red, and no edge in [ W,Z ] is blue.

Proof. Suppose B is a monochromatic, say blue, component which is maximal - in the sense that it is not properly contained in a monochromatic component of any color - and set U = V ( K ) \ B . If U = ∅ then we are in case (L ); so suppose not. 1 Note that none of the edges from B to U are colored blue. Let R be a maximal, say red, component which intersects both B and U . By the maximality of B , we have B \ R = . ∅

/negationslash

/negationslash

First suppose U \ R = . In this case, all of the edges in [ ∅ B ∩ R,U \ R ] and [ B R,U \ ∩ R ] are colored only with green. This implies all of the edges in [ B ∩ R,U ∩ R ] and [ B R,U \ \ R ]

are colored only with red, and all of the edges in [ B ∩ R,B \ R ] and [ U ∩ R,U \ R ] are colored only with blue. So, setting W := B ∩ R X , := B \ R Y , := U ∩ R , and Z := U \ R , we are in case (L 2 ).

Finally, suppose U \ R = ∅ . In this case the edges in [ B \ R,U ] are colored only with green, so there is a maximal green component G containing U ∪ ( B \ R ). Then, setting W := B ∩ R ∩ G X , := B \ G Y , := B \ R , and Z := U , we are in case (L 3 ).

Theorem 2.3. For all 3 -uniform hypergraphs H on n vertices with δ 2 ( H ) ≥ 1 , either (T ) 1 mc ( 3 H ) ≥ n -α ∗ 3 ( H ) , or

- (T ) 2 there exists a 3-coloring of the edges of H and a partition { V , V 1 2 , V 3 , V 4 } of V ( H ) with | V 1 | ≥ | V 2 | ≥ | V 3 | ≥ | V 4 | , α ∗ 3 ( H ) ≥ | V 2 | ≥ | V 3 | ≥ | V 4 | , and consequently | V 1 | + | V i | ≥ n -2 α ∗ 3 ( H ) for all i ∈ { 2 3 4 , , } such that no triple touches three of the sets V , V 1 2 , V 3 , V 4 , every triple which touches both V 1 and V 2 and every triple which touches both V 3 and V 4 is blue, every triple which touches both V 1 and V 3 and every triple which touches both V 2 and V 4 is red, and every triple which touches both V 1 and V 4 and every triple which touches both V 2 and V 3 is green.

In particular, for all 3 -uniform hypergraphs H on n vertices with δ 2 ( H ) ≥ 1 , we have mc ( 3 H ) ≥ n -2 α ∗ 3 ( H ) .

Proof. Let a 3 := α ∗ 3 ( H ). Given a 3-coloring of the edges of H , let K be the complete graph on V ( H ) with a 3-multicoloring obtained by coloring uv ∈ E K ( ) with color i if and only if there exists an edge e of color i in H such that { u, v } ⊆ e . Now apply Lemma 2.2 to K .

If we are in case (L ), 1 then we have a monochromatic component of order n in H which means (T ) holds; so suppose that we are not in case (L ). 1 1

Suppose that we are in case (L ) and without loss of generality, suppose 2 | W | ≥ | X | ≥ | Y | ≥ | Z | . Because of the structure of case (L ), no edge from 2 H intersects three of the sets W,X,Y,Z which implies | Y | ≤ a 3 . If | X &gt; a | 3 , then again since no edge from H intersects three of the sets W,X,Y,Z we must have | Y ∪ Z | ≤ a 3 , in which case there is a blue component on | W | + | X | = n -| Y ∪ Z | ≥ n -a 3 vertices which means (T ) holds; so 1 suppose | X | ≤ a 3 . In this case (T 2 ) holds, as there is a blue component on | W | + | X | = n -| Y | - | Z | ≥ n -2 a 3 vertices, a red component on | W | + | Y | = n -| X | - | Z | ≥ n -2 a 3 vertices, and a green component on | W | + | Z | = n -| X | - | Y | ≥ n -2 a 3 vertices.

Finally, suppose we are in case (L 3 ) and without loss of generality, suppose | X | ≥ | Y | ≥ | Z | . Because of the structure of case (L 3 ), no edge from H intersects all three of X,Y,Z which implies | Z | ≤ a 3 . But now there is a blue component in H on | W | + | X | + | Y | = n -| Z | ≥ n -a 3 vertices which means (T ) holds. 1

Let H k ( n, p ) be the binomial random k -uniform hypergraph on n vertices where each edge appears independently with probability p . Krivelevich and Sudakov [18] proved that provided p = ω ( 1 n k -1 ) and p = (1), then a.a.s. o

$$\alpha ( H _ { k } ( n, p ) ) = ( 1 + o ( 1 )$$

Note that the lower bound is the difficult part of the above estimate, whereas the upper bound is a straightforward first moment calculation. A similar first moment calculation (c.f. [17, Section 3.2]) shows that a.a.s.

$$\alpha _ { k } ^ { * } ( H _ { k } ( n, p ) )$$

And another straightforward calculation shows that if c &gt; 2 and p &gt; c log n n , then a.a.s. we have δ 2 ( H n,p 3 ( )) ≥ 1. Thus we obtain the following corollary.

## Corollary 2.4.

$$& \text{$\text{$corr$any $24$}.} \\ & \$$

Proof. (i) We have α ∗ k ( H k ( n, p )) ≥ /floorleft α H ( k ( n,p )) k /floorright (1) ≥ (1+ (1)) o k ( k ! log n p ) 1 ( / k -1) a.a.s. and thus the result follows from Proposition 1.1.

$$& \left ( \text{ii} \right ) \ I f \, c > 2 \ a n d \ p > \frac { c \log n } { n }, \ t h e n \ a. a. s. \ m c _ { 3 } ( H _ { 3 } ( n, p ) ) \geq n - 2 \left ( \frac { 3 \log n } { p } \right ) ^ { 1 / 2 }. \\ & \quad \, - \quad \dots \, \dots \, \quad \dots \, \quad \dots \, \quad \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \colon \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cd. \end{array} \right )$$

$$\begin{array} { c } \left ( i i \right ) \, \text{By } ( 2 ), \, \text{we have } \alpha _ { 3 } ^ { * } ( H _ { 3 } ( n, p ) ) \leq \left ( \frac { 3 \log n } { p } \right ) ^ { 1 / 2 } \, \text{a.a.s.\, Also for $c>2$ and $p>\frac{c\log n}{n}$, we} \\ \text{have } \delta _ { 2 } ( H _ { 3 } ( n, p ) ) \geq 1 \, \text{a.a.s.\, Thus the result follows from Theorem $2.3$.} \end{array}$$

Note that in [3], the authors prove that if p = ω ( 1 n k -1 ) , then a.a.s. mc k ( H k ( n, p )) ≥ (1 -o (1)) n . So the above corollary, for certain ranges of p , provides quantitative upper bounds for all k and provides a more precise quantitative lower bound in the case k = 3.

## 3 Random Steiner triple systems

In this section we prove Theorem 1.4. That is, we show that with probability approaching 1 as n → ∞ , a randomly chosen Steiner triple system S ∈ S n has the property that mc ( 3 S ) ≥ (1 -o (1)) n . We obtain this as a consequence of Theorem 1.3 and the following discrepancy-type result. 1

Theorem 3.1. There exists a constant δ &gt; 0 such that for n ≡ 1 3 mod 6 , if S ∈ S n is chosen uniformly at random, then a.a.s.

$$\alpha _ { 3 } ^ { * } ( S ) \leq n ^ { 1 - \delta }.$$

Corollary 3.2. There exists a constant δ &gt; 0 such that for n ≡ 1 3 mod 6 , if S ∈ S n is chosen uniformly at random, then a.a.s.

$$\underset { \dots } { \ m c _ { 3 } } ( S ) \geq n - 2 n ^ { 1 - \delta }.$$

1 We note that in a very recent paper, Ferber and Kwan implicitly prove a more general discrepancy theorem [10, Theorem 8.1] which implies α ∗ 3 ( S ) = o n ( ) a.a.s. for S ∈ S n chosen uniformly at random. While their discrepancy result is more general, the upper bound on α ∗ 3 ( S ) which follows from their result would be weaker than in Theorem 3.1.

Gy´ arf´s a [14, Problem 8] asks if min S ∈S n α ∗ 3 ( S ) is significantly smaller than max S ∈S n α ∗ 3 ( S ).

We prove Theorem 3.1 using the recent results of Kwan [19] which say that if one can show that a particular property happens with extremely high probability in an appropriately defined random 3-uniform hypergraph, then it also happens with high probability in a randomly chosen Steiner triple system. Before making this precise we need several definitions.

When n ≡ 3 mod 18, Gy´rf´s proves that max a a S ∈S n α ∗ 3 ( S ) = n 3 -1; furthermore, for all n ≡ 1 3 mod 6, there exists , S ∈ S n with α ∗ 3 ( S ) ≥ 2 /floorleft n/ 9 /floorright (see Section 6). So Theorem 3.1 provides an affirmative answer to [14, Problem 8] for all sufficiently large n ≡ 1 3 mod 6. ,

A partial Steiner triple system is a linear 3-uniform hypergraph; that is, a 3-uniform hypergraph in which every pair of vertices is contained in at most one edge. Let S n,m be the set of partial systems on n vertices which have m edges. Given a partial Steiner triple system, we may order its edges, and we let O n be the set of ordered Steiner triple systems on n vertices and O n,m be the set of ordered partial Steiner triple systems on n vertices with m edges. Given S ∈ O n,m and i ≤ m we let S i be the ordered partial system consisting of the first i edges of S .

Next we define two random processes which we will relate to choosing a random Steiner triple system.

First, the triangle removal process is a distribution on O n,m ∪ {∗} . We start with the complete graph K n and iteratively delete a triangle chosen uniformly from all triangles remaining in the graph. We continue this process until m triangles are removed or there are no more triangles. If the process stops before m triangles are removed, then the output is ' ∗ ' and otherwise the output is the ordered partial system in O n,m given by the m deleted triangles in the order they were deleted. Denote this resulting distribution as R ( n, m ).

Second, given an edge probability p let G ( n, p ) be the random distribution on 3-uniform hypergraphs given by independently selecting each triple of [ n ] with probability p . Let G ∗ ( n, p ) be the distribution on partial systems given by choosing a graph from G ( n, p ) and deleting all edges which intersect another edge in more than 1 vertex.

To analyze what happens in a randomly chosen Steiner triple system, we analyze what happens in G ( n, p ) using the following results of Kwan [19].

/negationslash

/negationslash

Theorem 3.3 (Theorem 2.4 of [19] using Q = O n and α = 1 2) / . Fixing a sufficiently small a &gt; 0 , there exists b = b a &gt; 0 such that the following holds. Let P ⊂ O n, 1 6 ( n 2 ) be a monotone property of ordered partial systems. Let S ∈ O n be a uniformly random ordered Steiner triple system and let S ′ ∈ R ( n, 1 6 ( n 2 ) ) . If S ′ = ∗ , say that S ′ ∈ P . If then

$$\Pr ( \mathbf S ^ { \prime } \not \in \mathcal { P } ) \leq \exp \left ( - n ^ { 2 - b } \right ),$$

/negationslash

Theorem 3.4 (Lemma 2.10 of [19] using α = 1 2 and / S = ∅ ) . Let P be a property of unordered partial systems that is monotone increasing (in the sense that S ∈ P and S ⊂ S ′

$$\Pr ( \mathbf S _ { \frac { 1 } { 6 } \binom { n } { 2 } } \not \in \mathcal { P } ) \leq \exp \left ( - \Omega \left ( n ^ { 1 - 2 a } \right ) \right ). \\ \text{ama 2.10 of } [ 1 9 ] \, \text{ using } \alpha = 1 / 2 \text{ and } S = \emptyset ) \text{.} \ L e$$

implies S ′ ∈ P ). Let S ∈ R ( n, 1 6 ( n 2 ) ) and S ∗ ∈ G ∗ ( n, 1 2 n ) . Then

$$\Pr ( \mathbf S \not \in \mathcal { P } ) = O \left ( \Pr ( \mathbf S ^ { * } \not \in \mathcal { P } ) \right ).$$

/negationslash

/negationslash

The end result of these two theorems is that if we can show that a monotone increasing property holds with probability at least 1 -exp ( -n 2 -b ) in the distribution G ∗ ( n, 1 2 n ) then it will also happen with probability tending to 1 in a randomly chosen Steiner triple system. In particular, we will use the following lemma from [19] to show that α ∗ 3 ( G ∗ ( n, 1 2 n )) ≤ n 1 -δ . As pointed out in [10], the following lemma can also be derived from [22, Theorem 1.3].

Lemma 3.5 ([19, Lemma 2.11] and [22, Theorem 1.3]) . Let ω = ( ω , . . . , ω 1 N ) be a sequence of independent, identically distributed random variables with Pr( ω i = 1) = p and Pr( ω i = 0) = 1 -p . Let f : { 0 1 , } N → R satisfy the Lipschitz condition | f ( ω ) -f ( ω ′ ) | ≤ K for all pairs ω, ω ′ ∈ { 0 1 , } N differing in exactly one coordinate. Then

$$\Pr ( | f ( \omega ) - \mathbb { E } f ( \omega ) | > t ) & \leq \exp \left ( - \frac { t ^ { 2 } } { 4 K ^ { 2 } N p + 2 K t } \right ). \\ \tilde { \lambda } \cdot \tilde { \lambda } \cdot \tilde { \lambda } \cdot \tilde { \lambda } \cdot \tilde { \lambda } \cdot \tilde { \lambda } \cdot \tilde { \lambda } \cdot \tilde { \lambda } \cdot \tilde { \lambda } \cdot \tilde { \lambda } \cdot \tilde { \lambda } \cdot \tilde { \lambda } \cdot \tilde { \lambda } \cdot \tilde { \lambda } \cdot \tilde { \lambda } \cdot \tilde { \lambda } \cdot \tilde { \lambda } \cdot \tilde { \lambda } \cdot \tilde { \lambda } \cdot \tilde { \lambda } \cdot \tilde { \lambda } \cd.$$

Proof of Theorem 3.1. Let A,B,C be fixed disjoint subsets of [ n ] of size n 1 -δ where δ is a small positive constant that will be chosen later. Let P A,B,C be the property that exists a triple which intersects all of A B , , and C . Note that P A,B,C is monotone increasing.

First we estimate the probability that a fixed set of three vertices appears as an edge in the distribution G ∗ ( n, 1 2 n ). Let x, y, z be fixed vertices. Then

$$\Pr ( x y z \text{ forms an edge} ) = \frac { 1 } { 2 n } \left ( 1 - \frac { 1 } { 2 n } \right ) ^ { 3 ( n - 3 ) } \sim \frac { 1 } { 2 n } e ^ { - 3 / 2 }. \\ \ell \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad \sim \sim \sim \sim \sim \Gamma ^ { \prime } \quad 1 \cdot \cdots \quad.$$

Therefore, the expected number of edges induced by A,B,C in G ∗ ( n, 1 2 n ), which we denote by e ∗ ( A,B,C ) is

$$\mathbb { E } ( e ^ { * } ( A, B, C ) ) = | A | | B | | C | \Pr ( x y z \text{ forms an edge} ) \sim \frac { e ^ { - 3 / 2 } } { 2 } n ^ { 2 - 3 \delta }.$$

Let the triples on [ n ] be ordered arbitrarily and let Z , 1 · · · , Z ( n 3 ) indicator random variables where Z i = 1 indicates that the i 'th triple appears in G ( n, p ). Let f A,B,C be the function where f A,B,C ( Z , 1 · · · , Z ( n 3 ) ) equals the number of edges in the resulting output of G ∗ ( n, p ) each with one endpoint in each of A B , , and C . Note that f A,B,C is 3-Lipschitz, since changing one triple in G ( n, p ) may add at most one edge or remove at most three edges from the resulting output of G ∗ ( n, p ). Thus f A,B,C satisfies the hypotheses of Lemma 3.5 (with K = 3).

Now using Lemma 3.5 with t = E ( e ∗ ( A,B,C )) ∼ e -3 / 2 2 n 2 -3 δ and the fact that

/negationslash we have

$$& \Pr \left ( \mathbb { G } ^ { * } \left ( n, \frac { 1 } { 2 n } \right ) \not \in \mathcal { P } _ { A, B, C } \right ) = \Pr \left ( e ^ { * } ( A, B, C ) = 0 \right ) = \Pr \left ( f _ { A, B, C } \left ( Z _ { 1 }, \cdots, Z _ { \binom { n } { 3 } } \right ) \leq 0 \right ), \\ & \text{we have}$$

/negationslash

$$\Pr \left ( \mathbb { G } ^ { * } \left ( n, \frac { 1 } { 2 n } \right ) \not \in \mathcal { P } _ { A, B, C } \right ) \leq \exp \left ( \frac { - t ^ { 2 } } { 3 n ^ { 2 } + 6 t } \right ) \leq \exp \left ( - \Omega \left ( n ^ { 2 - 6 \delta } \right ) \right ).$$

Now let P be the property that for all disjoint sets A B , , and C each of size n 1 -δ there is at least one edge which touches all three sets. Since there are at most 2 n choices for each of these sets, by the union bound we have

/negationslash

$$\Pr \left ( \mathbb { G } ^ { * } \left ( n, \frac { 1 } { 2 n } \right ) \not \in \mathcal { P } \right ) \leq 2 ^ { 3 n } \cdot \exp \left ( - \Omega \left ( n ^ { 2 - 6 \delta } \right ) \right ) = \exp \left ( - \Omega \left ( n ^ { 2 - 6 \delta } \right ) \right ). \\ T h o n d \colon \text{$1$+$ in $k$ to $a$ to $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ and $a$ respectively.$$

Therefore, letting b be the constant given by Theorem 3.3 and δ any positive constant less than b/ 6, we have by Theorems 3.3 and 3.4 that if S ∈ O n is a randomly chosen ordered Steiner triple system, then the first half of its edges induce at least 1 edge on any 3 disjoint sets A,B,C of size n 1 -δ almost surely, and so α ∗ 3 ( S ) ≤ n 1 -δ almost surely.

We close this section by raising the following problem, part (i) would strongly imply the existence result of Linial and Luria [20] and part (ii) would strongly imply the existence result of Grable, Phelps, and R¨dl [12] (both of which are discussed in Section 2). o

Problem 3.6. Is it true that for n ≡ 1 3 mod 6 , , if S ∈ S n is chosen uniformly at random, then a.a.s.

- (ii) α S ( ) = O ( √ n log n ) ?
- (i) α ∗ 3 ( S ) = O ( √ n log n ) and

We note that a positive answer to part (i) would imply a positive answer to part (ii) because, as previously observed, we have /floorleft α S ( ) 3 /floorright ≤ α ∗ 3 ( S ).

## 4 A lower bound for all Steiner triple systems

We begin with an upper bound on the 3-partite hole number of Steiner triple systems (which slightly improves the trivial upper bound). This was previously observed by Gy´ arf´s a in the introduction of [14], but in order to keep the paper self-contained and to make the calculation explicit, we provide a proof.

## Proposition 4.1. For all S ∈ S n , α ∗ 3 ( S ) ≤ n 3 -1 .

Proof. Let S ∈ S n and suppose for contradiction that α ∗ 3 ( S ) ≥ n -2 3 . Let V , V 1 2 , V 3 ⊆ [ n ] be disjoint sets with | V 1 | , | V 2 | , | V 3 | ≥ n -2 3 such that no triple in S touches all three of V , V 1 2 , V 3 .

If n ≡ 3 mod 6, then | V 1 | , | V 2 | , | V 3 | ≥ n -2 3 implies | V 1 | = | V 2 | = | V 3 | = n 3 . Since each triple touches at most two of the parts, we have

$$\frac { n ( n - 1 ) } { 6 } = e ( S ) \leq \binom { | V _ { 1 } | } { 2 } + \binom { | V _ { 2 } | } { 2 } + \binom { | V _ { 3 } | } { 2 } = 3 \binom { n / 3 } { 2 } = \frac { n ( n - 3 ) } { 6 },$$

a contradiction.

So suppose n ≡ 1 mod 6, in which case | V 1 | , | V 2 | , | V 3 | ≥ n -2 3 implies | V 1 | , | V 2 | , | V 3 | ≥ n -1 3 . So let {{ v } , V 1 , V 2 , V 3 } be a partition of [ n ] with | V 1 | = | V 2 | = | V 3 | = n -1 3 such that

no triple touches all three of V , V 1 2 , V 3 . In this case, we have

$$\frac { n ( n - 1 ) } { 6 } = e ( S ) & \leq \binom { | V _ { 1 } | } { 2 } + \binom { | V _ { 2 } | } { 2 } + \binom { | V _ { 3 } | } { 2 } + \frac { n - 1 } { 2 } \\ & = 3 \binom { ( n - 1 ) / 3 } { 2 } + \frac { n - 1 } { 2 } = \frac { ( n - 1 ) ( n - 4 ) } { 6 } + \frac { n - 1 } { 2 } = \frac { ( n - 1 ) ^ { 2 } } { 6 }, \\ \text{asin a contradiction}$$

again a contradiction.

Now we use Proposition 4.1 and Theorem 2.3 to prove a general lower bound on the size of a largest monochromatic component in every 3-coloring of every S ∈ S n . Again, this was previously proved by Gy´rf´s [14, Theorem 1], but since our proof is different, a a we include it here.

Theorem 4.2. For all S ∈ S n , mc ( 3 S ) ≥ 2 n 3 +1 .

Proof. Let S ∈ S n . Note that since n is congruent to either 1 or 3 mod 6 and mc ( 3 S ) is an integer, in order to show that mc ( 3 S ) ≥ 2 n 3 +1 it suffices to show that mc ( 3 S ) &gt; 2 n +1 3 . By Proposition 4.1 we have α ∗ 3 ( S ) ≤ n 3 -1. Now we apply Theorem 2.3 and either get mc ( 3 S ) ≥ n -α ∗ 3 ( S ) ≥ 2 n 3 + 1, or 3-coloring of S and a partition { V , V 1 2 , V 3 , V 4 } of V ( S ) satisfying (T 2 ). If we are in this situation, then V 1 ∪ V 2 induces a monochromatic component and thus mc ( 3 S ) ≥ | V 1 | + | V 2 | . Since no edge intersects three of the sets V , V 1 2 , V 3 , V 4 we have

$$\frac { n ( n - 1 ) } { 6 } = e ( S ) \leq \sum _ { i = 1 } ^ { 4 } \binom { | V _ { i } | } { 2 } \\ ( S ) > z _ { 1 } \text{ where } z _ { 2 } \text{ is the solution to the fc}$$

This implies that mc ( 3 S ) ≥ z 1 where z 1 is the solution to the following integer program.

$$<_YAML_> minimize
subject to$$

$$\leq \sum _ { i = 1 } ^ { 4 } \binom { x _ { i } } { 2 }.$$

$$z _ { 1 } = f ( x _ { 1 }, x _ { 2 }, x _ { 3 }, x _ { 4 } ) = x _ { 1 } + x _ { 2 } \\ x _ { 1 } + x _ { 2 } + x _ { 3 } + x _ { 4 } = n \\ x _ { 1 } \geq x _ { 2 } \geq x _ { 3 } \geq x _ { 4 } \\ \frac { n ( n - 1 ) } { 6 } \leq \sum _ { i = 1 } ^ { 4 } \binom { x _ { i } } { 2 }.$$

Instead we solve a slightly more relaxed integer program:

$$\minimize & z _ { 2 } = g ( x _ { 1 }, x _ { 2 } ) = x _ { 1 } + x _ { 2 } \\ \text{subject to} & x _ { 1 } + 3 x _ { 2 } \geq n \\ & \frac { x _ { 1 } \geq x _ { 2 } } { 6 } \leq \binom { x _ { 1 } } { 2 } + 3 \binom { x _ { 2 } } { 2 }.$$

Note that z 2 ≤ z 1 since for any ( x , x 1 2 , x 3 , x 4 ) which is feasible for the first problem we have ( x , x 1 2 ) is feasible for the second problem, and f ( x , x 1 2 , x 3 , x 4 ) = g x , x ( 1 2 ). Therefore, mc ( 3 S ) ≥ z 2 and it suffices to show that z 2 &gt; 2 n +1 3 for n ≥ 3.

To show this, assume that ( x , x 1 2 ) is an optimal solution for the second problem. Then we have x 1 ≥ n -3 x 2 and so

$$\frac { n ( n - 1 ) } { 6 } & \leq \binom { n - 3 x _ { 2 } } { 2 } + 3 \binom { x _ { 2 } } { 2 }. \\. & \quad \, \cdots \, \sim \, \cdots \, \cdots \, \cdots \,. \,. \,. \,. \,.$$

This implies 18 x 2 2 -9 nx 2 + n n ( -1) ≥ 0, which implies that either

$$\nu \nwarrow \nu _ { 0 } \leq \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \colon \\ x _ { 2 } \geq \frac { 9 n + \sqrt { 9 n ^ { 2 } + 7 2 n } } { 3 6 }.$$

or

If x 2 ≥ 9 n + √ 9 n 2 +72 n 36 , then z 2 = x 1 + x 2 ≥ 2 ( 9 n + √ 9 n 2 +72 n 36 ) = n 2 + n 6 √ 1 + 8 n . If x 2 ≤ 9 n -√ 9 n 2 +72 n 36 , then z 2 = x 1 + x 2 ≥ n -2 x 2 ≥ n 2 + n 6 √ 1 + 8 n . Since n 2 + n 6 √ 1 + 8 n &gt; 2 n +1 3 for all n ≥ 2, we are done in either case.

$$x _ { 2 } \leq \frac { 9 n - \sqrt { 9 n ^ { 2 } + 7 2 n } } { 3 6 }.$$

## 5 An upper bound for infinitely many Steiner triple systems

In this section we prove the following result which shows that Theorem 4.2 is asymptotically best possible.

Theorem 5.1. There exists an infinite family of Steiner triple systems S n k on n k vertices with

$$\ m c _ { 3 } ( S _ { n _ { k } } ) \leq ( 2 / 3 + o ( 1 ) ) n _ { k }. \quad \. \quad \. \quad \.$$

As mentioned in the introduction, a stronger (non-asymptotic) statement was proved by Gy´ arf´s [14, Theorem 4], which shows that Theorem 4.2 is actually best possible for a certain values of n . Regardless, we provide a proof of Theorem 5.1 as it turns out that Theorem 5.1 was alluded to in the abstract and introduction of [14]; however, as far as we know, a proof of this fact doesn't appear in the literature.

We begin with the following definition from [5]. Given a Steiner triple system ( V, B ), a 3-coloring of the vertex set φ : V → { 1 2 3 , , } is called a bicoloring if for all B ∈ B we have

∣ ∣ that is, every triple contains exactly 2 colors. We say that a Steiner triple system is ( a, b, c )-bicolorable if there is a bicoloring φ with

$$\left | \bigcup _ { v \in B } \phi ( v ) \right | = 2 ; \\ \text{tly } 2 \text{ colors.} \ \text{We } s \\ \text{loring } \phi \text{ with }$$

$$| \phi ^ { - 1 } ( 1 ) | = a \quad | \phi ^ { - 1 } ( 2 ) | = b \quad | \phi ^ { - 1 } ( 3 ) | = c.$$

In [5] the following recursive construction of bicolorings is given.

Theorem 5.2 ([5] Theorem 2.4) . If there exists an ( a, b, c ) -bicolorable Steiner triple system with c = max { a, b, c } and c ≤ a + b , and if there exists an ( x, y, z ) -bicolorable Steiner triple system, then there exists an ( ay + bz + cx, az + bx + cy, ax + by + cz ) -bicolorable Steiner triple system.

We use bicolorable Steiner triple systems to produce edge colorings with small monochromatic components.

Lemma 5.3. If S ∈ S n is ( a, b, c ) -bicolorable with a ≤ b ≤ c , then mc ( 3 S ) ≤ b + c .

Proof. Since S is ( a, b, c )-bicolorable, we have that α ∗ 3 ( S ) ≥ a and thus by Theorem 1.1, we have mc ( 3 S ) ≤ n -a = b + . c

Theorem 5.1 now follows immediately as a corollary from Lemma 5.3 and the following proposition.

Proposition 5.4. For each k ∈ N there exists a ( M ,M ,N k k k ) -bicolorable Steiner triple system where M ,N k k →∞ and M k N k → 1 as k →∞ .

Proof. It is easy to see that the unique Steiner triple system on 9 vertices is a (1 4 4)-, , bicolorable Steiner triple system. Applying Theorem 5.2 with a = x = 1 and b = c = y = z = 4 gives a (24 24 33)-bicolorable Steiner triple system. , ,

Let M 0 = 24 and N 0 = 33 and for all k ∈ N let

$$N _ { k } = 2 M _ { k - 1 } ^ { \ell } + N _ { k - 1 } ^ { \ell }. \\ \ell \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu.$$

$$M _ { k } & = M _ { k - 1 } ^ { 2 } + 2 M _ { k - 1 } N _ { k - 1 } \text{ \ and } \\ N _ { k } & = 2 M _ { k - 1 } ^ { 2 } + N _ { k - 1 } ^ { 2 }.$$

By induction, we have M k ≤ N k ≤ 2 M k for all k , since

Therefore, we may apply Theorem 5.2 with a = b = x = y = M k -1 and c = z = N k -1 and have that for each k there is a ( M ,M ,N k k k )-bicolorable Steiner triple system. It is clear that M k and N k go to infinity, and it remains to show that their ratio tends to 1. Define

M 2 k -1 +2 M k -1 N k -1 ≤ 2 M 2 k -1 + N 2 k -1 ≤ 2 M 2 k -1 +(2 M k -1 ) 2 ≤ 2( M 2 k -1 +2 M k -1 N k -1 ) .

$$r _ { k } = \frac { M _ { k } } { N _ { k } }, \\......$$

and note that r k ≤ 1 for all k . Also note that

Now since 0 ≤ r k ≤ 1 we have 2 r 2 k -1 +1 ≤ r 2 k -1 +2 ≤ r k -1 +2 which implies

$$r _ { k } = \frac { \overset { \cdot \cdot } { M } _ { k - 1 } ^ { 2 } + 2 M _ { k - 1 } N _ { k - 1 } } { 2 M _ { k - 1 } ^ { 2 } + N _ { k - 1 } ^ { 2 } } = \frac { r _ { k - 1 } ^ { 2 } N _ { k - 1 } ^ { 2 } + 2 r _ { k - 1 } N _ { k - 1 } ^ { 2 } } { 2 r _ { k - 1 } ^ { 2 } N _ { k - 1 } ^ { 2 } + N _ { k - 1 } ^ { 2 } } = r _ { k - 1 } \left ( \frac { r _ { k - 1 } + 2 } { 2 r _ { k - 1 } ^ { 2 } + 1 } \right ). \quad ( 4 ) \\ \intertext { n o w c i m o o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o n c o }$$

$$r _ { k - 1 } \leq r _ { k - 1 } \left ( \frac { r _ { k - 1 } + 2 } { 2 r _ { k - 1 } ^ { 2 } + 1 } \right ) = r _ { k } \\ \text{orassim and bound above there can}$$

by (4). Since r k is nondecreasing and bounded above, there is some r such that r k → r as k →∞ . By (4), we have which is satisfied if and only if r ∈ {-1 2 0 1 / , , } . Since r 0 &gt; 0 we must have r = 1.

$$\theta _ { \mu } ^ { \mu } \\ r = \lim _ { k \to \infty } r _ { k } = \lim _ { k \to \infty } \frac { r _ { k - 1 } ^ { 2 } + 2 r _ { k - 1 } } { 2 r _ { k - 1 } ^ { 2 } + 1 } = r \left ( \frac { r + 2 } { 2 r ^ { 2 } + 1 } \right ), \\ \text{isified if and only if } r \in \{ - 1 / 2 \, 0 \, 1 \} \, \text{ Since } r _ { \mu } > 0 \, \text{ we must have } r$$

## 6 Bose and Skolem triple systems

There are unique Steiner triple systems S 7 and S 9 on 7 and 9 vertices respectively and it is straightforward to directly show that mc 3 ( S 7 ) = 6 and mc 3 ( S 9 ) = 7 (and α ∗ 3 ( S 7 ) = 1 and α ∗ 3 ( S 9 ) = 2). These triple systems are the first non-trivial cases of two common constructions of Steiner triple systems by Bose and Skolem. A quasigroup is a pair ( Q, ◦ ) where Q is a set of size k and ◦ is a binary operation on Q such that the multiplication table is a latin square. That is, the equations a ◦ x = b and y ◦ a = b each have a unique solution for all a, b ∈ Q . A quasigroup is called idempotent if a ◦ a = a for all a ∈ Q and is called commutative if a ◦ b = b ◦ a for all a, b ∈ Q . A quasigroup is called half-idempotent if k is even and Q can be ordered in a way that cells ( i, i ) and ( k + i, k + ) contain i i in the multiplication table for all 1 ≤ i ≤ k .

Bose construction: Let n = 6 k +3 and let ( Q, ◦ ) be a commutative, idempotent quasigroup of order 2 k + 1. Define ( V, B ) as V = Q × { 0 1 2 , , } and B contains two types of triples.

Type 1: For all a ∈ Q let { ( a, 0) ( , a, 1) ( , a, 2) } be a triple.

Type 2: For all distinct a, b ∈ Q and i ∈ { 0 1 2 , , } let { ( a, i ) , ( b, i ) , ( a ◦ b, i + 1) } be a triple where addition in the second coordinate is done mod 3.

Because Q is commutative and idempotent, one can check that this forms a Steiner triple system on 6 k +3 vertices (see [6] for more details).

Let n = 6 k + 3 and let S be a Bose triple system on n points. Then we may color the Type 1 triples with 3 colors as evenly as possible, and color the Type 2 triples { ( a, i ) , ( b, i ) , ( a ◦ b, i + 1) } with color i -1 mod 3. Then each color will touch at most 4 k +2+ ⌈ 2 k +1 3 ⌉ ∼ 7 n 9 vertices, and so we have mc ( 3 S ) /lessorsimilar 7 n 9 .

Skolem construction: Let n = 6 k +1 and let ( Q, ◦ ) be a half-idempotent commutative quasigroup with Q = { 0 , · · · , 2 k - } 1 . Define ( V, B ) by V = {∞} ∪ ( Q ×{ 0 1 2 , , } ) and B as triples of three types.

Type 1: For all 0 ≤ a ≤ k -1, the triple { ( a, 0) ( , a, 1) ( , a, 2) } .

Type 3: For all distinct a, b ∈ Q and i ∈ { 0 1 2 , , } , the triple { ( a, i ) , ( b, i ) , ( a ◦ b, i +1) } with addition in the second coordinate done mod 3.

Type 2: For all 0 ≤ a ≤ k -1 the triples {∞ , ( k ◦ a, 0) ( , k, 1) } , {∞ , ( k ◦ a, 1) ( , k, 2) } , and {∞ , ( k ◦ a, 2) ( , k, 0) }

One may check that this forms a Steiner triple system on 6 k +1 vertices (see [6] for more details).

Given S , a Skolem triple system on 6 k + 1 vertices, we may color Type 1 triples as evenly as possible with 3 colors. Then we may color Types 2 and 3 triples with the color that is not represented in the second coordinate in any vertex of the triple. Each color class touches at most ⌈ k 3 ⌉ +4 k +1 ∼ 13 n 18 vertices, and so mc ( 3 S ) /lessorsimilar 13 n 18 .

It seems likely that these colorings are best-possible for some or maybe 'most' Bose and Skolem triple systems, so we pose the following problems.

Problem 6.1. Is there an infinite sequence S of Bose triple systems such that mc ( 3 S ) ∼ 7 | S / | 9 for all S ∈ S ?

Problem 6.2. Is there an infinite sequence S of Skolem triple systems such that mc ( 3 S ) ∼ 13 | S / | 18 for all S ∈ S ?

In light of Theorem 2.3, in order to address say Problem 6.1 we can try to show that the following is impossible: Given a Bose triple system S = ( V, B ) on n points, there is a partition of V into four sets with | V 1 | ≥ | V 2 | ≥ | V 3 | ≥ | V 4 | and 2 n 9 ∼ α ∗ 3 ( S ) ≥ | V 2 | ≥ | V 3 | ≥ | V 4 | and no triple touches three of the sets V , V 1 2 , V 3 , V 4 . There are at least two possible approaches here. First, one can define an explicit quasigroup that defines the Bose triple system. For example, for 2 k + 1 prime we may define the quasigroup by Q = Z 2 k +1 and a ◦ b = 1 2 ( a + ) where addition is done in the field. b In [4], this Steiner triple system was shown to have nice expansion properties. Second, one could define a quasigroup 'randomly'. Let K be the complete graph on [2 k +1]. Then we may associate multiplication tables of a quasigroup of order 2 k +1 to decompositions of K into matchings of size k ; that is, matchings which cover all but one vertex of K (For each x ∈ [2 k +1], let M x be the perfect matching which is not incident with x . Place an x in the i th row and j th column and the j th row and i th column for all { i, j } ∈ M x ). Choosing such a decomposition randomly (or choosing some amount of nearly perfect matchings randomly and then completing the decomposition) should yield a quasigroup with nice expansion properties.

## 7 Conclusion

We begin this section by drawing the reader's attention to the following conjecture which is best possible if true by Theorem 1.2(i) (Theorem 4.2) and Proposition 4.1, and is known to be true when n ≡ 3 mod 18 by Theorem 1.2(iii).

Conjecture 7.1 (Gy´ arf´s [14, Conjecture 2, Conjecture 5]) a . For all n ≡ 1 3 mod 6 , ,

$$( \text{ii} ) \, \min _ { S \in \mathcal { S } _ { n } } \, \mathrm m c _ { 3 } ( S ) = \left \lceil \frac { 2 n } { 3 } \right \rceil + 1. \\ \text{v} \quad. \quad. \quad. \quad \dots \quad.$$

$$\text{Conjecture } T. 1 ( \text{Gyartas } \lfloor 1 4, \text{Conje} \\ ( i ) \ \max _ { S \in \mathcal { S } _ { n } } \alpha _ { 3 } ^ { * } ( S ) = \left \lfloor \frac { n } { 3 } \right \rfloor - 1 \ a n d \\ \int _ { \left \langle \colon \right \rangle \ \dots \ \dots \ \right \rangle \ \left \langle \, c \right \rangle \, \int _ { \left \langle \colon \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \langle \, c \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \ rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \, \right \rangle \,.$$

We note that a positive answer to Conjecture 7.1(i) would imply a positive answer to Conjecture 7.1(ii).

If we let C be the set of real numbers c such that there exists a sequence of Steiner triple systems S n k on n k vertices with

$$\lim _ { k \to \infty } \frac { \mathrm m c _ { 3 } ( S _ { n _ { k } } ) } { n _ { k } } = c,$$

then the results in this paper together with the results in [14] show that { 2 3 1 / , } ⊆ C . Answering Problems 6.1 and 6.2 affirmatively would show that 7 9 and 13 18 are also in C . It would be interesting to determine other real numbers in C .

By combining Theorem 1.1 and Theorem 2.3, we have for all S ∈ S n , mc ( 3 S ) = n -α ∗ 3 ( S ) unless there is a partition { V , V 1 2 , V 3 , V 4 } of V ( H ) with | V 1 | ≥ | V 2 | ≥ | V 3 | ≥ | V 4 | , α ∗ 3 ( H ) ≥ | V 2 | ≥ | V 3 | ≥ | V 4 | , and | V 1 | + | V 2 | &lt; n -α ∗ 3 ( S ) such that no edge of

H intersects three of the sets V , V 1 2 , V 3 , V 4 . This raises the question of determining some sufficient condition that a Steiner triple system can satisfy which would rule out this latter possibility.

Problem 7.2. Does there exist an infinite family of Steiner triple systems S such that α ( S ) = ( 1 + (1)) o S and mc ( S ) = (2 / 3 + o (1)) S for all S ?

∗ 3 6 | | 3 | | ∈ S More generally, does there exist an infinite family of Steiner triple systems S such that mc ( 3 S ) = | S | -2(1 -o (1)) α ∗ 3 ( S ) ?

At the moment, we don't even have an example of a Steiner triple system S ∈ S n such that mc ( 3 S ) &lt; n -α ∗ 3 ( S ), although we suspect they exist.

Gy´ arf´s [13] and Gy´rf´s and Haxell [15] proved mc ( a a a 4 K 3 n ) ≥ 3 n/ 4, mc ( 5 K 3 n ) ≥ 5 n/ 7, mc ( 6 K 3 n ) ≥ 4 n/ 6 and these bounds are tight when n is divisible by 4, 7, and 6 respectively. In general, F¨redi and Gy´rf´s [11] showed that mc ( u a a r K 3 n ) ≥ n/q where q is the smallest integer such that r ≤ q 2 + q + 1 and this is sharp when q 3 divides n , r = q 2 + q + 1, and an affine space of dimension 3 and order q exists. As mentioned in the introduction, for S ∈ S n we have mc ( r S ) ≥ mc ( r K n ) ≥ n r -1 . Surprisingly, Gy´rf´s [14, Proposition 7] a a proved that if r -1 ≡ 1 3 mod 6 and , r -1 is a prime power, then for infinitely many n , min mc ( S ∈S n r S ) = n r -1 . It would be interesting to extend Theorem 1.3 to more colors, where a main obstacle would be a generalization of Lemma 2.2. Likewise, it would be interesting to extend Theorem 1.4 to more colors.

## Problem 7.3. Let S ∈ S n and let r ≥ 4 .

- (i) Determine bounds on mc ( r S ) in terms of α ∗ 3 ( S ) (or some related parameter).
- (ii) Determine a lower bound on mc ( r S ) which holds a.a.s. when S ∈ S n is chosen uniformly at random.

It is known (see [1], [2]) that in any 2-coloring of the edges of K 3 n , there is a monochromatic matching on at least 3 n/ 4 vertices and a monochromatic loose cycle (and consequently a loose path) on (4 / 5 -o (1)) n vertices [16]. We propose studying these problems in the setting of Steiner triple systems. As we did for monochromatic components, it would be interesting to get an absolute lower bound for all S ∈ S n , an upper bound for an infinite family S n k , and also to consider the case of a uniformly random S ∈ S n .

Problem 7.4. Let S ∈ S n . For an arbitrary 2-coloring of the edges of S ,

- (i) what is the largest monochromatic matching?
- (ii) what is the longest monochromatic loose path/cycle?

## Acknowledgements

We thank Tom Bohman, Charlie Colbourn, and Asaf Ferber for helpful discussions. We also thank the referees for their constructive feedback.

## References

- [1] N. Alon and P. Frankl. Families in which disjoint sets have large union. Annals of the New York Academy of Sciences 555 , no. 1 (1989), 9-16.
- [2] N. Alon, P. Frankl, and L. Lov´ asz. The chromatic number of Kneser hypergraphs. Transactions of the American Mathematical Society 298 , no. 1 (1986), 359-370.
- [3] P. Bennett, L. DeBiasio, A. Dudek, and S. English. Large monochromatic components and long monochromatic cycles in random hypergraphs. European Journal of Combinatorics 76 (2019), 123-137.
- [4] Z. Bl´zsik and Z. Nagy, Spreading linear triple systems and expander triple systems, a arXiv:1906.03149
- [5] C. J. Colbourn, J. H. Dinitz, and A. Rosa. Bicoloring Steiner triple systems. The Electronic Journal of Combinatorics 6 , no. 1 (1999), P.25.
- [6] C.J. Colbourn and A. Rosa. Triple systems. Oxford University Press , 1999.
- [7] R. Duke, H. Lefmann and V. R¨ odl. On uncrowded hypergraphs. Random Structures and Algorithms 6 , (1995), 209-212.
- [8] L. DeBiasio, P. McKenney. Density of monochromatic infinite subgraphs. Combinatorica , (2019). https://doi.org/10.1007/s00493-018-3724-2
- [9] A. Eustis and J. Verstra¨te. On the independence number of Steiner systems. e Combinatorics, Probability and Computing 22 , no. 2 (2013), 241-252.
- [10] A. Ferber and M. Kwan, Almost all Steiner triple systems are almost resolvable, arXiv:1907.06744
- [11] Z. F¨redi and A. Gy´rf´s. Covering u a a t -element sets by partitions. European Journal of Combinatorics 12 , no. 6 (1991), 483-489.
- [12] D.A. Grable, K. T. Phelps, and V. R¨dl. The minimum independence number for o designs. Combinatorica 15 , no. 2 (1995), 175-185.
- [13] A. Gy´ arf´s. a Partici´fed´sek o e ´ es lefog´halmazok o hipergr´fokban, a Tanulm´ anyok-MTA Sz´ amit´stechn. Automat. Kutat´ Int. Budapest a o 62 , (1977).
- [14] A. Gy´ arf´s. Large cross-free sets in Steiner triple systems. a Journal of Combinatorial Designs 23 , no. 8 (2015), 321-327.
- [15] A. Gy´ arf´s and P. Haxell. Large monochromatic components in colorings of complete a 3-uniform hypergraphs. Discrete Mathematics 309 , no. 10 (2009), 3156-3160.
- [16] P. E. Haxell, T. /suppress Luczak, Y. Peng, V. R¨dl, A. Ruci´ski, M. Simonovits, and J. Skokan. o n The Ramsey number for hypergraph cycles I. Journal of Combinatorial Theory, Series A 113 , no. 1 (2006), 67-83.

- [17] A. Kostochka, D. Mubayi, and J. Verstra¨te. On independent sets in hypergraphs. e Random Structures &amp; Algorithms 44 , no. 2 (2014), 224-239.
- [18] M. Krivelevich and B. Sudakov. The chromatic numbers of random hypergraphs. Random Structures &amp; Algorithms 12 , no. 4 (1998), 381-403.
- [19] M. Kwan. Almost all Steiner triple systems have perfect matchings. arXiv preprint arXiv:1611.02246 (2016).
- [20] N. Linial and Z. Luria. Discrepancy of high-dimensional permutations, Discrete Analysis 2016:11, 8pp.
- [21] K. T. Phelps and V. R¨dl. Steiner triple systems with minimum independence numo ber. Ars Combin. 21 (1986), 167-172.
- [22] L. Warnke. On the method of typical bounded differences. Combinatorics, Probability and Computing 25 , no. 2 (2016), 269-299.
Louis DeBiasio Michael Tait
Large monochromatic components in 3-edge-colored Steiner triple systems
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.