Bicoloring Steiner Triple Systems

Charles J. Colbourn Computer Science

University of Vermont Burlington VT 05405

 colbourn@emba.uvm.edu

Jeffrey H. Dinitz Mathematics and Statistics University of Vermont Burlington VT 05405

                                  Jeff.Dinitz@uvm.edu

Alexander Rosa Mathematics and Statistics McMaster University Hamilton, Ontario, Canada L8S 4K1

               rosa@mcmail.cis.mcmaster.ca

Submitted: March 31, 1999; Accepted: May 24, 1999.

Abstract

A Steiner triple system has a bicoloring with m color classes if the points are partitioned into m subsets and the three points in every block are contained in exactly two of the color classes. In this paper we give necessary conditions for the existence of a bicoloring with 3 color classes and give a multiplication theorem for Steiner triple systems with 3 color classes. We also examine bicolorings with more than 3 color classes. Math Subject Clasification: 05B07

1 Introduction

Throughout this paper we use notation consistent with that found in [?]. Let D = (V, B) be a (v, k, λ)-design. A coloring of D is a mapping φ : V → C. The elements of C are colors; if |C| = m, we have an m-coloring of D. For each c ∈ C, the set φ^{−1}(c) = {x : φ(x) = c} is a color class. A coloring φ of D is weak (strong) if for all B ∈ B, | φ(B) |> 1 (φ(B) = k, respectively), where φ(B) = ∪_{v∈B}φ(v). Each color class in a weak or strong coloring is an independent set. In a weak coloring, no block is monochromatic (i.e., no block has all its elements the same color), while in a strong coloring, the elements of any block B get | B | distinct colors. The weak [strong] chromatic number of D is the smallest m for which D admits a weak [strong] m-coloring. Much work has been done on weak and strong colorings; for an extensive survey of these results, the reader is referred to [?].

For triple systems, the following results concerning weak colorings are known.

Theorem 1.1 [?]. For every admissible v ≥ 5 and any λ there exists a weakly 3-chromatic 2 − (v, 3, λ)-design.

A modification of Bose’s and Skolem’s constructions for Steiner triple systems was used to prove:

Theorem 1.2 [?, ?]. A weakly 4-chromatic ST S(v) exists for every v ≡ 1 or 3 (mod 6), v ≥ 21.

In this paper we consider a stronger coloring condition than weak coloring, termed a bicoloring. While a bicoloring is defined for any design, we examine only bicolorings of Steiner triple systems.

A coloring φ of D is a bicoloring if for all B ∈ B, | φ(B) |= 2, where φ(B) = ∪_{v∈B}φ(v). This definition implies that in a triple system every triple has two elements in one color class and one in another class, i.e. there are no monochromatic triples nor are there any triples receiving three colors. So, in some sense, a bicoloring of a triple system is an anti-strong weak coloring.

An m-bicoloring is a bicoloring with m color classes, and a design admitting an m-bicoloring is m-bicolorable. A design is m-bichromatic if it is m-bicolorable but not (m − 1)-bicolorable.

Example 1.3 A 3-bicolorable STS(13). First, construct an STS(13) by developing the base blocks {1, 3, 9}, {2, 5, 6} mod 13. The color classes are {0, 1}, {2, 6, 8, 10, 11}, {3, 4, 5, 7, 9, 12}

In the context of strict colorings of hypergraphs defined recently by Voloshin [?], a bicoloring of an STS is a strict coloring of an STS in which all triples are both edges and also co-edges. In [?, ?], Milazzo and Tuza discuss several properties of strict colorings of Steiner triple systems. An easy counting argument [?] establishes that there exist no nontrivial 2-colorable STS (or triple systems of any index λ for v > 4), and hence no 2-bichromatic triple systems. In the next section we consider 3-bicolorable (and hence 3-bichromatic) STSs.

While for a weak m-chromatic triple system there are some general bounds on the sizes of the color classes (see [?]), in an m−bichromatic triple system there is a divisibility condition that the sizes of the color classes must satisfy.

Proposition 1.4 Let (X, A) be an m−bicolorable triple system TS(v, λ) and assume that the m color classes have sizes c_{1}, c_{2}, …, c_{m}. Then

∑_{i=1}^{m} \binom{c_{i}}{2} = \binom{v}{2}/3.  (1)

Proof. (See also [?].) Since exactly one of the three pairs of elements covered by any triple of A has both its elements within one color class, the number of monochromatic pairs must be one third of the total number of pairs.

The divisibility condition is not sufficient. For example, if c_{i} = c_{j} = 2, and i ≠ j, there cannot exist an m-bicoloring no matter what the size of the other color classes. This is called the duplicity condition.

Since every triple must have two 2-colored pairs, the total number of 2-colored pairs must be even. Hence, we obtain the oddity condition:

Proposition 1.5 Let (X, A) be an m−bicolorable triple system TS(v, λ) and assume that the m color classes have sizes c_{1}, c_{2}, …, c_{m}, then at most one of numbers c_{1}, c_{2}, …, c_{m} can be odd.

If v is an admissible order for STS, every m-tuple (c_{1}, c_{2}, …, c_{m}) (with the c_{i}s in nonincreasing order by convention) satisfying the divisibility condition is an m-split for v.

Every 3-split satisfying the divisibility condition automatically satisfies the oddity condition as well. Indeed, if (a, b, c) is a 3-split satisfying the divisibility condition for an admissible order v, and a, b, c are all odd, then of the four numbers \binom{v}{2}, \binom{a}{2}, \binom{b}{2}, \binom{c}{2} either three are even and one is odd, or three are odd and one is even; in either case we have a contradiction.

A similar statement can be shown to be true for 4-splits. However, for m ≥ 5 there are many m-splits satisfying the divisibility condition which do not satisfy the oddity condition. Still, these conditions together are not sufficient. In fact, we have the following density condition:

Proposition 1.6 Let v ≡ 1, 3 (mod 6). If there exists an m-bicolorable STS(v) with m-split (c_{1}, …, c_{k}, d_{1}, …, d_{m−k}) (with 0 < k < m), then the inequality

0 ≤ [∑_{i=1}^{k} \binom{c_{i}}{2}] − \frac{1}{2} [∑_{i=1}^{k−1} ∑_{j=i+1}^{k} c_{i}c_{j}] ≤ \frac{1}{2} [∑_{i=1}^{k} c_{i}] · [∑_{i=1}^{m−k} d_{i}] − ℓ(∑_{i=1}^{m−k} d_{i})

holds, where

ℓ(x) = \{ \begin{matrix}x/2 & if & x ≡ 0, 2 (mod 6) \\ 0 & if & x ≡ 1, 3 (mod 6) \\ (x + 2)/2 & if & x ≡ 4 (mod 6) \\ 4 & if & x ≡ 5 (mod 6) \end{matrix}

Proof. Let (V, B) be a putative m-bicolorable STS(v) with the specified msplit. Partition the m color classes into two groups, the first with color class sizes {c_{1}, …, c_{k}} and the second with sizes {d_{1}, … d_{m−k}}. We concentrate on triples with one point in the first group and one point in the second (and the location of the third point unknown as yet). A pair with one endpoint in a class in the first group and the other endpoint in a different class of the first group appears in a triple that lies wholly in the first group. Hence we can count triples that lie wholly on the first group, and from this determine the number of triples with two points in a class of the first group and one point in a class of the second group. This count is the left hand side of the inequality given. Each such triple requires two of the pairs between the first and second group. However, some of these pairs may already be required in triples containing two points from a class in the first group and one in a class of the second. The ‘correction’ ℓ(…) is then the minimum number of such triples. If we examine a packing on the points of the second group, say with x points in the second group, we see that ℓ(x) is the smallest number of pairs left uncovered by any packing (i.e. the smallest number of edges in the leave graph of any packing). Thus the right hand side of the inequality reflects (one half of) the maximum number of pairs available to form triples with two points in a class of the first group and one point in a class of the second group.

We believe that the necessary conditions given in this section taken together are sufficient for the existence of m-bicolorable STSs, at least for m ≤ 5.

2 3-bichromatic STS

2.1 Necessary conditions

In order to establish necessary conditions for the existence of a 3-bicolorable STS we first need a number theoretic lemma.

Lemma 2.1 Let n be an integer and p ≥ 5 a prime factor of n^{2} + n + 1, then p ≡ 1 (mod 6).

Proof. Since 4(n^{2} + n + 1) = (2n + 1)^{2} + 3, if p divides n^{2} + n + 1, then −3 is a square modulo p. Then 1 = (\frac{−3}{p}), where (\frac{a}{b}) is the Legendre symbol. Now

(\frac{−3}{p}) = (\frac{−1}{p}) (\frac{3}{p}) = (−1)^{(p−1)/2} (\frac{p}{3}) (−1)^{(p−1)(3−1)/4} by quadratic reciprocity,

and hence 1 = (−1)^{p−1} (\frac{p}{3}). Since p is odd, 1 = (\frac{p}{3}), or equivalently, p ≡ 1 (mod 3). Again, since p is odd, p ≡ 1 (mod 6), the desired conclusion.

We are now in a position to prove the following.

Theorem 2.2 Given an STS(v), and a putative 3-bicoloring with classes of sizes a, b, and v − a − b. Let p be a prime, p ≡ 5 (mod 6), and assume p^{2i−1} divides v for some i ≥ 1. Then

(a) p^{i} divides a, b, and v − a − b, and

(b) p^{2i} divides v.

Consequently, if there exists a 3-bicolorable STS(v), then any prime p dividing v with p ≡ 5 (mod 6) must have an even power in the prime factorization of v.

Proof. By the divisibility condition,

\binom{a}{2} + \binom{b}{2} + \binom{v − a − b}{2} = \binom{v}{2}/3.

This simplifies to

3a(a − 1) + 3b(b − 1) + 3v(v − 1) − 3(2v − 1)(a + b) + 3(a + b)^{2} = v(v − 1).

Hence

3a^{2} + 3b^{2} + 3ab + v(v − 1) − 3v(a + b) = 0.  (2)

Now suppose that v is a multiple of p^{2i−1}, and treat this equation modulo p^{2i−1} to get that 3a^{2}+3b^{2}+3ab ≡ 0 (mod p^{2i−1}). Since 3 and p are relatively prime,

a^{2} + b^{2} + ab ≡ 0 (mod p^{2i−1}).  (3)

Now one obvious solution has a ≡ b ≡ 0 (mod p^{i}). If this is not the solution, then without loss of generality say a is not a multiple of p^{i}. We will obtain a contradiction in this case.

Let k be such that p^{k} divides a, but p^{k+1} does not divide a, with 0 ≤ k ≤ i − 1. From (??), p^{2k} divides b^{2} + ab = b(b + a). Since p^{k} divides a, it follows that p^{k} also must divide b. Let â = a/p^{k} and b̂ = b/p^{k}. Dividing (??) by p^{2k} yields the equation â^{2} + b̂^{2} + âb̂ ≡ 0 (mod p^{2i−2k−1}). Since p does not divide â we can multiply by â^{−1} modulo p^{2i−2k−1} to obtain

1 + n^{2} + n ≡ 0 (mod p^{2i−2k−1})

where n is b̂â^{−1} (mod p). But now by Lemma ??, this does not happen when p ≡ 5 (mod 6). Thus, p^{i} divides a, b and hence also v − a − b.

Now look at (??) again. Since p^{2i} is a divisor of the terms 3a^{2}, 3b^{2}, 3ab and 3v(a + b), we find that p^{2i} must divide v(v − 1). Since p divides v, then p and v − 1 are relatively prime, and hence p^{2i} must divide v. This completes the proof.

We conjecture that the necessary condition given in Theorem ?? is also sufficient for the existence of 3-bichromatic STS, and in the next section we find 3-bicolorable STS(v)s for many orders of v.

2.2 Existence

We begin this section with a multiplication theorem. One key ingredient of the construction is a special type of latin square. We first prove a theorem about these latin squares.

Write n = a + b + c. Let A, B and C be disjoint sets of sizes a, b and c, respectively. A latin square with rows, columns, and symbols indexed by A ∪ B ∪ C is called (a, b, c)−forbidden if in cell (r, g) we find symbol s satisfying:

r in A and g in A implies s not in C r in A and g in B implies s not in B r in A and g in C implies s not in A r in B and g in A implies s not in B r in B and g in B implies s not in A r in B and g in C implies s not in C r in C and g in A implies s not in A r in C and g in B implies s not in C r in C and g in C implies s not in B

Now (a, b, c)−, (b, c, a)− and (c, a, b)−forbidden latin squares are the same. Similarly, (b, a, c)−, (a, c, b)− and (c, b, a)−forbidden latin squares are the same.

Lemma 2.3 An (a, b, c)-forbidden latin square of order n exists if and only if max(a, b, c) ≤ n/2.

Proof. Necessity is obvious. To prove sufficiency, we assume without loss of generality that c = max(a, b, c), so that we need only treat cases when a ≤ b ≤ c, and when b < a ≤ c. Let X be a set of (a + b − c) symbols disjoint from A, B and C. We are going to form a partial latin square P. The construction differs slightly in the two cases.

If a ≤ b form an (a + b) × (a + b) latin square R with rows and columns indexed by A ∪ B, and symbols indexed by C ∪ X, so that R contains an a × a subsquare on the rows and columns indexed by A, and the symbols in the subsquare containing all symbols in X (and possibly some of the symbols in C). From R, form a partial latin square P as follows. Remove the a × a subsquare and place an a × a subsquare on the symbols in A in its place.

When a > b, instead first place an a × a square on symbols in A on the subsquare with rows and columns indexed by A; a b × a latin rectangle on a subset C_{a} of a symbols in C on the rectangle with rows indexed by B and columns by A; an a × b latin rectangle on the subset C_{a} of symbols on the rectangle with rows indexed by A and columns by B. Then fill the b × b subsquare with rows and columns indexed by B using a latin square on the symbols (C − C_{a}) ∪ X (this is indeed b symbols as required).

Now the two cases merge. Delete all occurrences of elements in X from the square; all appear in the subarray with rows and columns indexed by B. Form a bipartite graph, with one class being the rows indexed by B, the other being the columns indexed by B, with a row and column vertex made adjacent whenever the symbol was one of those in X. Color this bipartite graph in b colors, so that the coloring is equalized (proper and every color appearing the same number of times as every other, i.e. a + b − c times). This can be done by a theorem of de Werra [?]. Now whenever an edge of this bipartite graph gets the ith color, place in the corresponding cell the ith symbol in B. At this point, P is a partial latin square with symbols from A, B and C. In fact, every symbol in A appears a times, every one in B occurs a + b − c times, and every one in C is at least b times. It follows from Ryser’s Theorem [?] that P can be completed to a latin square, since n = a + b + c and so every symbol occurs at least (a + b) + (a + b) − (a + b + c) = a + b − c times as required.

That this forces the (a, b, c)−forbidden requirements (taking of course all rows and columns added in the embedding to be those indexed by C) is easy counting. To help check it, here are the counts on numbers of symbols from each of A, B and C in each of the subarrays:

Symbols from A :

A B  C
A a^{2} 0  0
B 0 0  ab
C 0 ab a(c − b)

Symbols from B :

A  B  C
A 0  0  ab
B 0 b(a + b − c) b(c − a)
C ab b(c − a)  0

Symbols from C :

A  B  C
A  0  ab  a(c − b)
B  ab  b(c − a)  0
C a(c − b)  0  c^{2} − a(c − b)

This finishes the existence proof for (a, b, c)-forbidden latin squares.

Next we make a simple observation, that in an (a, b, c)−bicolored STS, the size c satisfies c ≤ (a + b) unless (a, b, c) = (0, 1, 2) (and v = 3) or (a, b, c) = (1, 2, 4) (and v = 7). The proof is easy: By the divisibility condition, \binom{a}{2} + \binom{b}{2}+\binom{c}{2} must equal \binom{a+b+c}{2}/3. Simplify to get a^{2} +b^{2} +c^{2} −(a+b+c)−(ab+ ac + bc) = 0. Now assume that c > a + b. The left side of this expression is minimized when a = b, but then one can check that for this side to be less than or equal to 0, one must have v ≤ 16. Now these remaining orders can be checked by hand.

This underlies the one exceptional case in the direct product to follow.

Theorem 2.4 If there exists an (a, b, c)−bicolorable STS(u) with c = max(a, b, c) and c ≤ a + b, and if there exists an (x, y, z)−bicolorable STS(v), then there exists an (ax + by + cz, ay + bz + cx, az + bx + cy)−bicolorable STS(uv).

Proof. Define sets V_{ij} of elements with 0 ≤ i < v and j ∈ {0, 1, 2}, so that V_{ij} has a, b, c elements for j = 0, 1, 2 respectively, when 0 ≤ i < x; b, c, a elements for j = 0, 1, 2 respectively, when x ≤ i < x + y; and c, a, b elements for j = 0, 1, 2 respectively, when x+y ≤ i < v. The union of V_{ij} for 0 ≤ i < v then has ax + by + cz, bx + cy + az, and cx + ay + bz elements for j = 0, 1, 2, respectively.

For i = 0, …, v − 1, place on the union of V_{ij} for j = 0, 1, 2 an (a, b, c)− bicolored STS(u) in which the color classes are V_{i0}, V_{i1} and V_{i2}. Now choose an (x, y, z)−bicolored STS(v) in which the color classes are {0, ..., x−1}, {x, ..., x+ y−1}, {x+y, ..., v−1}, and let B be its blocks. Call the colors in this coloring 0, 1 and 2. Whenever {f, g, h} ∈ B, suppose without loss of generality that f and g have the same color k in the bicoloring of the STS(v). When h has color (k + 2) mod 3, form an (a, b, c)−forbidden latin square; when h has color (k + 1) mod 3, instead form a (b, a, c)−forbidden latin square. Use the latin square to construct triples in the obvious way (i.e., form the transversal design TD(3, u) from the latin square and align the row, column, and symbol classes of sizes a, b, c on the corresponding V′_{fj}s, V′_{gj}s and V′_{hj}s).

The result is a bicolorable STS(uv) whose color classes have the specified sizes.

Corollary 2.5 If there exists a 3-bicolorable STS(u) and a 3-bicolorable STS(v), then there exists a 3-bicolorable STS(uv).

Proof. The corollary follows from Theorem ?? except possibly when u and v both are 3 or 7. Examples of 3-bicolorable STS(9), STS(21), and STS(49) are easily found.

If there exists a 3-bicolorable STS(v) with a 3-split (a, b, c), then (??) must be satisfied. Using (??) for v ≡ 1, 3 (mod 6), v ≤ 97 yields the following solutions.

v a b c ∃? v a b c ∃? v a b c ∃? v a b c ∃?
7 4 2 1 yes 9 4 4 1 yes 9 5 2 2 dupl 13 6 5 2 yes
15 none 19 9 6 4 yes 21 9 8 4 yes 21 10 6 5 yes
25 10 10 5 yes 27 12 9 6 yes 31 14 9 8 yes 33  none
37 16 12 9 yes 39 16 14 9 yes 39 17 12 10 yes 43 17 16 10 yes
45  none  49 20 17 12 yes 49 21 14 14 yes 51  none
55  none  57 22 21 14 yes 57 24 17 16 yes 61 25 20 16 yes
63 25 22 16 yes 63 26 20 17 yes 67 26 24 17 yes 69  none
73 30 22 21 yes 75 30 25 20 yes 79 32 25 22 yes 81 30 30 21 yes
81 33 24 24 yes 85 none 87 none 91 34 33 24 yes
91 36 30 25 yes 93 36 32 25 yes 93 37 30 26 yes 97 37 34 26 yes

We have obtained solutions for all of these meeting the duplicity condition, using Stinson’s hill-climbing algorithm for triple systems [?] (or see [?], p. 730) modified so that only 2-colored triples could be constructed. We have also constructed a 3-bicolorable STS(v)s for all v ≡ 1, 3 (mod 6), 99 ≤ v < 1000, satisfying the condition given in Theorem ?? and every possible 3-split satisfying the divisibility condition.

Theorem 2.6 For every v ≡ 1, 3 (mod 6), v < 1000 satisfying the necessary condition given in Theorem ?? and for all 3-splits (a, b, c) satisfying the divisibility condition, there exists a 3-bicolorable STS(v) with color classes of sizes a, b, and c.

Conjecture 2.7 For every v ≡ 1, 3 (mod 6), satisfying the condition in Theorem ?? and for all 3-splits (a, b, c) for v satisfying the divisibility and duplicity conditions, there exists a 3-bicolorable STS(v) with color classes of sizes a, b, and c.

¿From Theorem ?? and Corollary ??, we have our main result on the existence of 3-bicolorable STSs:

Theorem 2.8 Let v ≡ 1, 3 (mod 6) and assume that in the prime factorization of v no prime congruent to 5 (mod 6) appears with an odd exponent. Further assume that all prime factors p congruent to 1 (mod 6) are less than 1000 and that all prime factors p congruent to 5 (mod 6) satisfy p^{2} < 1000, then there exists a 3-bicolorable STS(v).

3 4- and 5-bicolorable STS

The following has been observed, in effect, in [?].

Theorem 3.1 If there exists an m-bicolorable STS(v) with m-split (c_{1}, …, c_{m}), then there exists an (m + 1)-bicolorable STS(2v + 1) with an (m + 1)-split (v + 1, c_{1}, …, c_{m}).

Proof. Apply the well-known 2v + 1 construction (cf. [?], Chapter 3), and color all elements not in the sub-STS(v) with a new color.

A variant of this gives a different (m + 1)-split:

Theorem 3.2 If there exists an m-bicolorable STS(v) with m-split (c_{1}, …, c_{m}), then there exists an (m + 1)-bicolorable STS(2v + 1) with an (m + 1)-split (2c_{1}, 2c_{2}, …, 2c_{m}, 1).

Proof. Let (V, B) be the m-bicolorable STS(v). We form an STS(2v + 1) on (V × {0, 1}) ∪ {∞} as follows. Whenever {x, y, z} ∈ B, form the blocks {x_{i}, y_{j}, z_{k}} for (i, j, k) = (0,0,0), (0,1,1), (1,0,1), and (1,1,0). Then form the blocks {∞, x_{0}, x_{1}} for x ∈ X. Color x_{i} for i ∈ {0, 1} using the same color as was assigned to x in the STS(v). Then assign ∞ a new color.

That there exist m-bicolorable STSs with arbitrarily large m is now immediate. However, in this section we restrict our attention to the case of 4- and 5-bicolorings as these display some marked contrasts to the case of 3-bicolorings. For example, while Theorem ?? ensures that there exist infinitely many admissible orders v for which no 3-bicolorable STS can exist, this does not appear to be so in the case of 4- or 5-bicolorings.

Another somewhat less obvious recursion is proved:

Theorem 3.3 If there exists a m-bicolorable STS(v) with m-split (c_{1}, …, c_{m}), then there exists a (m + 2)-bicolorable STS(5v + 4) with (m + 2)-split (2v + 2, 2v + 2, c_{1}, …, c_{m}).

Proof. Let V = {a_{j} : j = 1, …, v}, and suppose (V, B) is the m-colorable STS(v). We construct a (m + 2)-bicolorable STS(5v + 4) on the (5v + 4)-set W = Z_{2v+2} × {1, 2} ∪ V as follows.

Consider the graph G with the vertex-set Z_{2v+2} and the edge-set {{x, y} : |x − y| ∈ {(v + 3)/2, (v + 5)/2, …, v + 1}; G is regular of degree v, and thus, by the Stern-Lenz Lemma (cf. [?], Chapter 1), G has a 1-factorization, say {F_{1}, …, F_{v}}. Let further S = {(a_{r}, b_{r}) : r = 1, 2, …, (v + 1)/2}, b_{r} − a_{r} = r be a Skolem sequence of order (v + 1)/2 if (v + 1)/2 ≡ 0, 1 (mod 4), or a hooked Skolem sequence of order (v + 1)/2 if (v + 1)/2 ≡ 2, 3 (mod 4) (cf. [?], Chapter 2).

Define now the following sets of triples (for the sake of brevity we write x_{i} for (x, i) etc.).

P = {a_{j}, x, y} : {x, y} ∈ F_{j}^{i}, i = 1, 2, j = 1, 2, …, v},

Q = {{i_{2}, (i + r − 1)_{1}, (i + a_{r} − 1)_{1}} : r = 1, …, (v + 1)/2, i ∈ Z_{2v+2}}, R = {{i_{1}, (i + 2v + 1 − r)_{2}, (i + 2v + 1 − a_{r})_{2}} : r = 1, …, (v + 1)/2, i ∈

Z_{2v+2}}.

Then (W, B ∪ P ∪ Q ∪ R) is an STS(5v + 4). Moreover, this STS is (m + 2)-bicolorable with color classes Z_{2v+2} × {1}, Z_{2v+2} × {2}, and the m color classes of the original m-bicoloring of (V, B).

A specific recursion for special 4-splits can also be established:

Theorem 3.4 Suppose that there exists a 4-bicolorable STS(v) with 4-split (x, y, z, 1) and a 4-bicolorable STS(u) with 4-split (a, b, c, 1), so that c = max(a, b, c) and c ≤ a + b. Then there exists a 4-bicolorable STS(\frac{1}{2}(u − 1)(v −1)+1) with 4-split (\frac{1}{2}(ax+by +cz), \frac{1}{2}(ay +bz +cx), \frac{1}{2}(az +bx+cy), 1).

Proof. Define sets V_{ij} of elements with 0 ≤ i < \frac{v−1}{2} and j ∈ \{0, 1, 2\}, so that V_{ij} has a, b, c elements for j = 0, 1, 2 respectively, when 0 ≤ i < \frac{x}{2}; b, c, a elements for j = 0, 1, 2 respectively, when \frac{x}{2} ≤ i < \frac{x+y}{2}; and c, a, b elements for j = 0, 1, 2 respectively, when \frac{x+y}{2} ≤ i < \frac{v−1}{2}. The union of V_{ij} for 0 ≤ i < \frac{v−1}{2} then has \frac{1}{2}(ax + by + cz), \frac{1}{2}(ay + bz + cx), \frac{1}{2}(az + bx + cy) elements for j = 0, 1, 2, respectively. Add a new point ∞.

For i = 0, …, \frac{v−1}{2} − 1, place on the union of V_{ij} for j = 0, 1, 2 together with ∞, an (a, b, c, 1)−bicolored STS(u) in which the color classes are V_{i0}, V_{i1}, V_{i2}, and \{∞\}. Next consider the 4-bicolored STS(v) with color classes \{i, \overline{i} : 0 ≤ i < \frac{x}{2}\}, \{i, \overline{i} : \frac{x}{2} ≤ i < \frac{x+y}{2}\}, \{i, \overline{i} : \frac{x+y}{2} ≤ i < \frac{v−2}{2}\}, and \{∞\}. Call the colors in this coloring 0, 1, 2, and 3, where ∞ gets color 3. Partition each set V_{ij} into two sets X_{ij} and \overline{X}_{ij} of equal size, for each 0 ≤ i < \frac{v−1}{2} and j ∈ {0, 1, 2}. Consider a block of the STS(v) not containing ∞, say \{f, g, h\}. For each element t ∈ \{f, g, h\}, choose one of X_{ij} or \overline{X}_{ij} depending upon whether t is of the form i or \overline{i}. On the three corresponding sets, latin squares of side \frac{u−1}{2} are used to form triples as in Theorem ??.

Table ?? lists all possible 4-splits for v ≤ 99, and Table ?? all possible 5splits for v ≤ 87 meeting the divisibility conditions. The entry ‘yes’ indicates that the corresponding STS has been found by hill climbing or by the constructions given in this paper. The entries ‘dupl’, ‘odd’, and ‘den’ indicate that the parameters fail the duplicity, oddity, or density condition, respectively. As in the case of 3-bicoloring, we have actually generated all possible 4-splits satisfying the divisibility and duplicity conditions for all v ≤ 157, and all possible 5-splits satisfying the divisibility, duplicity, oddity, and density conditions for v ≤ 105. We then used the hill-climbing algorithm to verify that in each case there exists a bicolorable STS with the corresponding split.

In view of the above, the following conjectures appear reasonable.

Conjecture 3.5 A 4-bicolorable STS(v) exists if and only if v ≡ 1, 3 (mod 6) , v ≥ 15, v ≠ 21, 31.

Conjecture 3.6 A 5-bicolorable STS(v) exists if and only if v ≡ 1, 3 (mod 6), v ≥ 31, v ≠ 33, 37, 43, 45, 61.

4 Conclusion

If an STS(v) is m-bicolorable then m ≤ ⌈log_{2}(v + 1)⌉ [?, ?]. Moreover, for all v = 2^{n} − 1 there exists an STS(v) for which this bound is attained. The corresponding STS is the projective STS(v) (see, e.g., [?]).

If we define the spectrum C(v) for bicolorings by C(v) = {m: there exists an m-bicolorable STS(v) } then we have C(7) = C(9) = C(13) = {3}, C(15) = {4}, C(19) = {3, 4}, C(21) = {3}, C(25) = C(27) = {3, 4}, C(31) = {3, 5}, C(33) = {4}.

Thus C(v) is not necessarily an interval. Can one characterize those orders v for which C(v) is an interval? It is conceivable that 31 is the only admissible order v for which C(v) is not an interval.

Acknowledgments

We thank Vitali Voloshin for suggesting the problem, and Dave Dummit for assistance with the proof of Lemma ??. Research of the authors is supported by ARO grant DAAG55-98-1-0272 (Colbourn), and NSERC Canada grant OGP007268 (Rosa).

v a b c d ∃? v a b c d ∃? v a b c d ∃?
15 8 4 2 1 yes 19 10 5 2 2 dupl 19 10 4 4 1 yes
19 8 8 2 1 yes 21 none 25 12 8 4 1 yes
27 14 6 5 2 yes 27 12 10 4 1 yes 31  none
33 16 10 5 2 yes 33 16 8 8 1 yes 33 14 13 4 2 yes
37 16 14 5 2 yes 39 20 9 6 4 yes 39 18 13 6 2 yes
39 18 12 8 1 yes 43 22 10 6 5 yes 43 22 9 8 4 yes
43 21 10 10 2 yes 43 20 12 10 1 yes 43 18 17 4 4 yes
43 18 16 8 1 yes 45 22 13 6 4 yes 45 21 14 8 2 yes
49 24 14 6 5 yes 49 21 18 8 2 yes 51 26 10 10 5 yes
51 25 14 8 4 yes 51 20 20 10 1 yes 55 28 12 9 6 yes
55 26 17 8 4 yes 55 24 18 12 1 yes 57 24 22 6 5 yes
57 24 21 10 2 yes 57 24 20 12 1 yes 61 30 16 10 5 yes
61 30 14 13 4 yes 61 29 18 10 4 yes 61 28 20 9 4 yes
61 28 18 13 2 yes 61 25 24 8 4 yes 63 32 14 9 8 yes
63 29 18 14 2 yes 63 28 22 9 4 yes 63 28 18 16 1 yes
67 33 18 8 8 yes 67 32 20 9 6 yes 67 30 21 14 2 yes
69 34 16 14 5 yes 69 32 22 10 5 yes 69 29 26 10 4 yes
69 28 26 13 2 yes 73 36 18 13 6 yes 73 34 22 13 4 yes
73 33 24 12 4 yes 73 32 26 10 5 yes 73 32 20 20 1 yes
73 29 28 14 2 yes 73 28 28 16 1 yes 75 38 16 12 9 yes
75 37 18 14 6 yes 75 36 22 9 8 yes 75 36 18 17 4 yes
75 34 21 18 2 yes 75 33 26 12 4 yes 75 33 24 16 2 yes
75 32 28 9 6 yes 75 32 24 18 1 yes 75 30 30 10 5 yes
79 40 17 12 10 yes 79 40 16 14 9 yes 79 38 22 13 6 yes
79 36 25 14 4 yes 79 34 29 10 6 yes 79 34 24 20 1 yes
79 33 28 16 2 yes 79 32 28 18 1 yes 81 40 21 10 10 yes
81 38 24 14 5 yes 81 34 30 13 4 yes 81 33 32 8 8 yes
85 42 21 14 8 yes 85 41 24 12 8 yes 85 38 29 12 6 yes
85 38 24 21 2 yes 85 36 32 9 8 yes 85 36 29 18 2 yes
87 44 17 16 10 yes 87 41 22 20 4 yes 87 40 26 17 4 yes
87 34 32 20 1 yes 91 44 25 14 8 yes 91 38 34 14 5 yes
93 46 21 18 8 yes 93 45 26 12 10 yes 93 45 22 20 6 yes
93 44 28 12 9 yes 93 42 30 16 5 yes 93 42 29 18 4 yes
93 40 30 21 2 yes 93 38 36 13 6 yes 97 46 29 12 10 yes
97 46 24 22 5 yes 97 45 26 22 4 yes 97 42 34 16 5 yes
97 40 37 14 6 yes 97 40 36 17 4 yes 97 40 34 21 2 yes
97 40 32 24 1 yes 99 50 21 14 14 yes 99 50 20 17 12 yes
99 49 24 16 10 yes 99 48 26 17 8 yes 99 46 25 24 4 yes
99 42 37 10 10 yes 99 42 28 28 1 yes 99 41 38 12 8 yes
99 40 34 24 1 yes 99 38 38 21 2 yes

v a b c d e ∃? v a b c d e ∃? v a b c d e ∃?
31 16 8 4 2 1 yes 33 none 37 none
39 20 10 5 2 2 dupl 39 20 10 4 4 1 yes 39 20 8 8 2 1 yes
39 19 11 7 1 1 odd 39 17 15 3 3 1 odd 39 16 16 4 2 1 yes
43 21 13 5 3 1 odd 43 21 11 9 1 1 odd 45  none
49 20 20 5 2 2 dupl 49 20 20 4 4 1 yes 51 26 13 6 4 2 den
51 26 12 8 4 1 yes 51 25 15 5 5 1 odd 51 24 17 4 4 2 den
51 24 16 8 2 1 yes 51 23 17 9 1 1 odd 55 28 14 6 5 2 yes
55 28 12 10 4 1 yes 55 27 15 9 3 1 odd 55 26 18 5 4 2 den
55 25 19 7 3 1 odd 55 24 20 8 2 1 yes 57 28 17 4 4 4 den
57 28 16 8 4 1 yes 57 26 20 5 4 2 den 61 30 18 5 4 4 den
61 28 21 6 4 2 den 63 31 15 13 3 1 odd 63 30 20 6 5 2 yes
67 34 17 8 4 4 den 67 34 16 10 5 2 yes 67 34 16 8 8 1 yes
67 34 14 13 4 2 yes 67 32 21 6 6 2 den 67 32 20 10 4 1 yes
67 32 16 16 2 1 yes 67 31 17 17 1 1 odd 67 30 24 6 5 2 yes
67 29 25 7 5 1 odd 67 29 23 13 1 1 odd 67 28 26 8 4 1 yes
69 34 20 6 5 4 den 69 30 26 5 4 4 den 69 30 25 10 2 2 dupl
69 28 28 6 5 2 yes 73 36 21 6 6 4 den 73 36 20 10 5 2 yes
73 36 20 8 8 1 yes 73 36 16 16 4 1 yes 73 34 24 8 5 2 yes
73 30 29 8 4 2 yes 75 38 16 14 5 2 yes 75 37 21 9 5 3 odd
75 37 19 13 5 1 odd 75 35 25 5 5 5 odd 75 34 26 8 5 2 yes
75 33 27 9 5 1 odd 75 32 28 10 4 1 yes 79 40 20 9 6 4 yes
79 40 18 13 6 2 yes 79 40 18 12 8 1 yes 79 39 21 11 7 1 odd
79 39 19 15 5 1 odd 79 38 24 9 4 4 yes 79 37 26 6 6 4 den
79 37 25 11 3 3 odd 79 37 23 15 3 1 odd 79 36 26 12 4 1 yes
79 36 24 16 2 1 yes 79 35 27 13 3 1 odd 79 34 30 6 5 4 den
79 33 31 7 5 3 odd 81 38 26 9 6 2 yes 81 37 28 6 6 4 den
81 36 29 8 6 2 den 81 36 28 12 4 1 yes 85 42 24 8 6 5 den
85 41 26 6 6 6 den 85 40 26 13 4 2 yes 85 38 30 9 6 2 yes
87 44 22 10 6 5 yes 87 44 22 9 8 4 yes 87 44 21 10 10 2 yes
87 44 20 12 10 1 yes 87 44 18 17 4 4 yes 87 44 18 16 8 1 yes
87 43 23 13 5 3 odd 87 43 23 11 9 1 odd 87 42 26 10 5 4 yes
87 42 20 20 4 1 yes 87 41 28 8 6 4 den 87 41 27 11 7 1 odd
87 41 23 19 3 1 odd 87 40 29 10 6 2 yes 87 40 24 20 2 1 yes
87 39 31 7 5 5 odd 87 39 23 23 1 1 odd 87 38 32 9 4 4 yes
87 36 34 10 5 2 yes 87 36 34 8 8 1 yes 87 36 32 16 2 1 yes
87 35 35 9 7 1 odd

References

[1] M. de Brandes, K.T. Phelps, V. Rödl, Coloring Steiner triple systems, SIAM J. Alg. Disc. Meth. 3 (1982), 241-249.

[2] C. J. Colbourn and J. H. Dinitz, eds. The CRC Handbook of Combinatorial Designs, CRC Press, Inc., 1996.

[3] C.J. Colbourn, A. Rosa, Triple Systems, Clarendon Press, Oxford, 1999.

[4] L. Haddad, On the chromatic numbers of Steiner triple systems, J. Combinat. Designs 7 (1999), 1–10.

[5] L. Milazzo, Zs. Tuza, Upper chromatic number of Steiner triple and quadruple systems, Discrete Math. 174 (1997), 247-259.

[6] L. Milazzo, Zs. Tuza, Strict colourings for classes of Steiner triple systems, Discrete Math. 182 (1998), 233-243.

[7] A. Rosa, On the chromatic number of Steiner triple systems, in: Combinat. Structures and their Applications, Proc. Conf. Calgary 1969, Gordon & Breach 1970, pp. 369-371.

[8] A. Rosa, Steiner triple systems and their chromatic number, Acta Fac. Rer. Nat. Univer. Comen. Math. 24 (1970), 159-174.

[9] A. Rosa and C. J. Colbourn, Colorings of block designs. In Contemporary Design Theory: A Collection of Surveys, J. H. Dinitz and D. R. Stinson, eds., John Wiley & Sons, 1992, pp. 401-430.

[10] H.J. Ryser, A combinatorial theorem with an application to Latin rectangles, Proc. Amer. Math. Soc. 2 (1951), 550-552.

[11] D.R. Stinson, Hill-climbing algorithms for the construction of combinatorial designs, Ann. Discrete Math. 26 (1985), 321-334.

[12] V.I. Voloshin, On the upper chromatic number of a hypergraph, Australas. J. Combin. 11 (1995), 25-45.

[13] D. de Werra, Equitable colorations of graphs, Rev. Francaise Automat. Informat. Rech. Oper. Ser. Rouge 3 (1971), 3-8.