An exact small-$n$ computation of the minimum 2-coloring discrepancy of $K_n^{(3)}$

Abstract

For an integer $r\ge 2$ and an order $n\equiv 1,3(\mathrm{mod}6)$, write ${\delta }_r(n)$ for the minimum, over all $r$-colourings $\chi :\left(\genfrac{}{}{0ex}{}{[n]}{3}\right)\to [r]$, of ${\max }_{\mathcal{S}}\mathrm{disc}(\mathcal{S},\chi )$, where the maximum is over labelled Steiner triple systems $\mathcal{S}$ of order $n$ and $\mathrm{disc}(\mathcal{S},\chi )={\max }_c|\#\{T\in \mathcal{S}:\chi (T)=c\}-|\mathcal{S}|/r|$. Following Gishboliner, Glock, and Sgueglia \cite{GishbolinerGlockSgueglia2025}, the bulk of the recent work on this quantity has been on lower bounds for $r\ge 3$ (proving ${\delta }_r(n)=\Omega (n^2)$) and on structural characterisation of the low-discrepancy 2-colourings. We give three small computational contributions in the small-$n$ regime $n\in \{7,9,13,15,19,21\}$: An exact value of ${\delta }_2(n)$ for each such $n$, matching the formula ${\delta }_2(n)={\min }_{x\in [0,n]\cap \mathbb{Z}}|x(n-x)/2-n(n-1)/12|$ obtained by optimising the GGS Example 1.1 family. Rigorous for $n\in \{7,9\}$ via exhaustive search over labelled STSs ($30$ resp. $840$ systems) and over all $2$-colourings; computational for $n\in \{13,15,19,21\}$ by simulated-annealing search; A wide near-optimal basin: at $n=9$, every two-colour-flip neighbour of the optimal Example~1.1 colouring that maintains discrepancy $1.0$ exists; about $34\%$ of two-flip perturbations preserve optimality; Random-colouring statistics for $r\in \{2,3,4\}$: $⟨{\max }_{\mathcal{S}}\mathrm{disc}⟩$ grows linearly in $n$, in agreement with a heuristic Gaussian estimate $n/\sqrt{6r}\cdot \sqrt{2\log K}$ over $K$ sampled labellings; the typical-case discrepancy is far below the GGS worst-case $\Omega (n^2)$. We additionally state a conjectural exact formula for ${\delta }_2(n)$ that holds for every $n\equiv 1,3(\mathrm{mod}6)$.

Theorem 1 is false. Pernegger and Hametner found a 2-colouring of the triples of [9] with discrepancy 0 on every Steiner triple system of order 9 (X={1,2}; a triple is blue iff it meets both X and its complement and avoids {1,3}), so delta_2(9)=0, not 1. The same construction also refutes n=13,19,21 and the conjecture; the true value is the parity floor. With thanks to the authors