高失衡的Steiner三元系统

Steiner triple systems with high discrepancy

摘要 Abstract

本文首次研究了组合设计的失衡问题。具体而言,我们证明了对于每个固定的$r\geq 3$以及$n\equiv 1,3 \pmod{6}$的情况,任何对$[n]$上的三元组进行$r$-染色都存在一个阶数为$n$且失衡量为$\Omega(n^2)$的Steiner三元系统。但当$r=2$时,这一结论不成立;我们能够渐近刻画所有不含高失衡量的Steiner三元系统的二染色情况。在我们的证明过程中,关键步骤是对避免某种自然诱导子图的3-均匀超图进行特征化,这为超图的结构理论做出了贡献。

In this paper, we initiate the study of discrepancy questions for combinatorial designs. Specifically, we show that, for every fixed $r\ge 3$ and $n\equiv 1,3 \pmod{6}$, any $r$-colouring of the triples on $[n]$ admits a Steiner triple system of order $n$ with discrepancy $\Omega(n^2)$. This is not true for $r=2$, but we are able to asymptotically characterise all $2$-colourings which do not contain a Steiner triple system with high discrepancy. The key step in our proofs is a characterization of 3-uniform hypergraphs avoiding a certain natural type of induced subgraphs, contributing to the structural theory of hypergraphs.

高失衡的Steiner三元系统 - arXiv