Large Cross-Free Sets in Steiner Triple Systems

Gyárfás, András (2015) Large Cross-Free Sets in Steiner Triple Systems. Journal of Combinatorial Designs, 23 (8). pp. 321-327. ISSN 1063-8539

Preview

Text 1509.05527v1.pdf Download (108kB) | Preview

Abstract

A cross-free set of size m in a Steiner triple system (V,B) is three pairwise disjoint m-element subsets X1,X2,X3⊂V such that no B∈B intersects all the three Xi-s. We conjecture that for every admissible n there is an STS(n) with a cross-free set of size ⌊n-33⌋ which if true, is best possible. We prove this conjecture for the case n=18k+3, constructing an STS(18k+3) containing a cross-free set of size 6k. We note that some of the 3-bichromatic STSs, constructed by Colbourn, Dinitz, and Rosa, have cross-free sets of size close to 6k (but cannot have size exactly 6k). The constructed STS(18k+3) shows that equality is possible for n=18k+3 in the following result: in every 3-coloring of the blocks of any Steiner triple system STS(n) there is a monochromatic connected component of size at least ⌈2n3⌉+1 (we conjecture that equality holds for every admissible n). The analog problem can be asked for r-colorings as well, if r-1≡1,3(mod6) and r-1 is a prime power, we show that the answer is the same as in case of complete graphs: in every r-coloring of the blocks of any STS(n), there is a monochromatic connected component with at least nr-1 points, and this is sharp for infinitely many n. © 2014 Wiley Periodicals, Inc.

Actions (login required)

Edit Item