A Combinatorial Proof of Hilton's Conjecture and Beyond

Thomas Lesgourgues; Luke Postle

En palabras de los autores

Using refined absorption, we prove that for every integer $g \geq 1$ and real $γ > 0$ , and for sufficiently large $n$ , there exists an $n^{- 1 + γ}$ -spread distribution on Latin squares of order $n$ and girth at least $g$ that have no proper subsquares. This implies a combinatorial proof of Hilton's conjecture from the 1970s (recently proved algebraically by Allsop and Wanless) that for all sufficiently large $n$ , there exists a subsquare-free Latin square of order $n$ ; indeed, it implies there exist at least $n^{(1 - o (1)) n^{2}}$ subsquare-free squares. Simultaneously it also implies the existence of high girth Latin squares (recently proved by Kwan, Sah, Sawhney and Simkin) and even an $n^{- 1 + γ}$ -spread distribution on high girth Latin squares.

Resultado principalEl resumen no menciona limitaciones.

A Combinatorial Proof of Hilton's Conjecture and Beyond

En palabras de los autores

Más de Combinatoria y matemática discreta ese día

Thinning and sprinkling: from robust sampling to almost Hamiltonicity

Boolean threshold functions, neuron capacity, and memory retrieval

The Marcus-Minc Transform Inequality

The coarse Erd\H{o}s-P\'{o}sa theorem

Antichain polynomials of products of chains and minuscule posets