Colour Critical Hypergraphs With Many Edges

NEW

Problem: The intended conjecture is: for fixed $k\ge3$ and $r>l\ge2$, if $T(k,r,l,n)$ denotes the number of non-isomorphic $k$-critical $(r,l)$-systems on $n$ vertices, then

The lower bound is Theorem 6.1 of Rödl--Siggers; the conjectural content is the upper bound $T(k,r,l,n)\le C^{n^l}$. This is the only nontrivial reading, since a mere lower bound is already proved in the paper.

Result: The conjecture is false. It already fails for $(k,r,l)=(4,3,2)$.

We prove that for infinitely many $n$,

so no bound $C^{n^2}$ is possible.

Use Toft’s theorem: there is $a>0$ and, for all large $N$, a $4$-critical graph $G_N$ on $N$ vertices with $m\ge aN^2$ edges.

Let $t=4N$. The number of proper edge-colourings

is at least $(2N)^m$, since when greedily colouring an edge, at most $2N-4$ colours are forbidden.

For each such $\alpha$, build a linear triple system $J_\alpha$ as follows. Take three copies $v^1,v^2,v^3$ of each vertex $v\in V(G_N)$, and vertices $w_1,\dots,w_t$. For every edge $uv\in E(G_N)$ and $i=1,2,3$, add the triple

Because $\alpha$ is a proper edge-colouring, these triples form a $(3,2)$-system. Add the standard Rödl--Siggers gadgets $S(3,3)$ forcing $w_1=\cdots=w_t$ in every proper $3$-colouring, and gadgets $D(3,3)$ forcing $v^1,v^2,v^3$ to receive three distinct colours.

Then $J_\alpha$ is not $3$-colourable: if all $w_j$ have colour $1$, then each original vertex $v$ has a unique copy $v^i$ of colour $1$. Mapping $v\mapsto i$ gives a proper $3$-colouring of $G_N$, contradiction.

Moreover, any non-$3$-colourable subhypergraph $K\subseteq J_\alpha$ must contain at least one of the three triples over every edge $uv\in E(G_N)$. Otherwise, since $G_N-uv$ is $3$-colourable, one extends such a colouring to the three copies and the gadgets, making $K$ $3$-colourable.

Choose an inclusion-minimal non-$3$-colourable subhypergraph $K_\alpha\subseteq J_\alpha$. Then $K_\alpha$ is $4$-critical. Distinct $\alpha$’s give distinct labelled $K_\alpha$’s, because $K_\alpha$ contains a lifted triple using $w_{\alpha(uv)}$ for every $uv$.

The ambient vertex set has size $O(N)$. Dividing by all possible labellings loses only $\exp(O(N\log N))$, while the number of choices of $\alpha$ is at least

By pigeonholing over the $O(N)$ possible vertex counts, for infinitely many $n=\Theta(N)$,

Thus $T(4,3,2,n)$ is not $\exp(\Theta(n^2))$. The conjectured upper bound is false.

Citation: The dense $4$-critical graphs are due to Toft, Studia Sci. Math. Hung. 5 (1970), 461--470. The forcing gadgets $S(k,r)$, $D(k,r)$ are from Rödl--Siggers, “Colour Critical Hypergraphs With Many Edges,” Construction 3.1. The superexponential-in-$n^l$ counterexample above is not cited there.