Large cross-free sets in Steiner triple systems

DOI10.1002/JCD.21395zbMATH Open1322.05027arXiv1509.05527OpenAlexW2951666996MaRDI QIDQ2950652FDOQ2950652

András Gyárfás

Publication date: 9 October 2015

Published in: Journal of Combinatorial Designs (Search for Journal in Brave)

Abstract: A {em cross-free} set of size $m$ in a Steiner triple system $(V,calB)$ is three pairwise disjoint $m$-element subsets $X_1,X_2,X_{3}subsetV$ such that no $BincalB$ 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 $lfloorn-3over3floor$ 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 $lceil2nover3ceil+1$ (we conjecture that equality holds for every admissible $n$). The analogue problem can be asked for $r$-colorings as well, if $r-1equiv1,3mbox(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 $noverr-1$ points, and this is sharp for infinitely many $n$.

Full work available at URL: https://arxiv.org/abs/1509.05527

Recommendations

• scientific article; zbMATH DE number 2192115
• Steiner triple systems with high chromatic index
• On colourings of Steiner triple systems
• scientific article; zbMATH DE number 3874089
• Unbalanced Steiner triple systems

zbMATH Keywords

Steiner triple systemsedge coloring of hypergraphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65) Triple systems (05B07)

Cites Work

• Bicoloring Steiner triple systems
• On the Independence Number of Steiner Systems

Cited In (7)

• Large monochromatic components in 3‐edge‐colored Steiner triple systems
• Large girth approximate Steiner triple systems
• Generalizations and strengthenings of Ryser's conjecture
• Finding large 3-free sets. I. The small \(n\) case
• Large monochromatic components in expansive hypergraphs
• Existence of good large sets of Steiner triple systems
• Title not available (Why is that?)

This page was built for publication: Large cross-free sets in Steiner triple systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2950652)