Structural Reductions for Monochromatic Matchings and Ramsey Tilings

Abstract

The Alon--Frankl--Lovász theorem determines the chromatic number of Kneser hypergraphs; equivalently, it gives the sharp minimum size of a monochromatic matching in every edge-colouring of a complete uniform hypergraph. Its known general proofs are topological. We introduce a topology-free structural framework. It reduces every colouring of a pseudorandom $t$-graph, with only $o(n)$ loss in the largest monochromatic matching, to a colouring of $K_n^{(t)}$ whose vertex set has at most $r$ parts and whose edge colours depend only on intersection profiles. Together with a stability analysis at the critical scale, we prove an exact robust form: there exists $c=c(r,t)>0$ such that, if a $t$-graph satisfies $\delta (\mathcal{G})\ge (1-c)\left(\genfrac{}{}{0ex}{}{n-1}{t-1}\right)$, then every $r$-colouring of $\mathcal{G}$ contains a monochromatic matching of the exact optimal size for all sufficiently large $n$. This gives a topology-free proof of the Alon--Frankl--Lovász theorem for large $n$, a sparse random transference theorem, and the exact value predicted by Meunier's stable Kneser conjecture throughout the range covered by our robust AFL theorem. We further develop the framework for Ramsey graph tilings. For a graph $H$, let $R{t}_r(H;K_n)$ be the minimum, over all $r$-edge-colourings of $K_n$, of the largest monochromatic $H$-tiling. We prove $$R{t}_r(H;K_n)=({\beta }_{r,H}+o(1))n,$$ where ${\beta }_{r,H}$ is effectively computable from finitely many rational linear programs depending only on $H$ and $r$. An additional multipartite Ramsey argument is needed to reconstruct a consistent coloured template. This gives an effective asymptotic solution to the multicolour Ramsey-tiling problem, extending the classical two-colour theorem of Burr, Erdős and Spencer. We also determine explicit constants for several natural families.

43 pages, 5 figures. Added an exact robust version of the Alon-Frankl-Lovász theorem