Large Cross-free sets in Steiner triple systems

Abstract

A {\em cross-free} set of size $m$ in a Steiner triple system $(V,\mathcal{B})$ is three pairwise disjoint $m$-element subsets $X_1,X_2,X_3\subset V$ such that no $B\in \mathcal{B}$ intersects all the three $X_i$-s. We conjecture that for every admissible $n$ there is an STS$(n)$ with a cross-free set of size $\lfloor \frac{n-3}{3}\rfloor$ 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 $\lceil \frac{2n}{3}\rceil +1$ (we conjecture that equality holds for every admissible $n$). The analogue problem can be asked for $r$-colorings as well, if $r-1 \equiv 1,3 \mbox{ (mod 6)}$ 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 $\frac{n}{r-1}$ points, and this is sharp for infinitely many $n$.

Journal of Combinatorial Designs, 2014

Cited by in corpus (1)

• Large monochromatic components in expansive hypergraphs