Track new results across pure and applied mathematics.
Search papers, labs, and topics across Lattice.
This paper determines the exact number of cells to remove from an $n \times n$ board to eliminate all cycles, denoted $\nabla(n)$. The authors prove $\nabla(n) = \lceil((n-1)^2+1)/3\rceil$ for $n \equiv 3, 5 \pmod 6$ via explicit constructions and establish $\nabla(n) = \lceil((n-1)^2+1)/3\rceil + 1$ for $n \equiv 0, 2 \pmod 6$ using a geometric obstruction. These results fully characterize $\nabla(n)$ for all $n$, resolving a long-standing problem in combinatorial design.
Cycles are eliminated from $n \times n$ boards with precisely $\lceil (n^2 - n/2 + 4/3) \rceil - \lceil n/2 \rceil$ removed cells, a result that is $\lceil((n-1)^2+1)/3\rceil$ or one greater depending on $n \pmod 6$.
Define $\nabla(n)$ as the least possible number of cells that must be removed from the $n\times n$ square board in order to leave no cycles. Put $L_n=\left\lceil\left((n-1)^2+1\right)/3\right\rceil$. The results of Luccio, Madelaine-Stewart, and Lien-Fu-Shih imply that $\nabla(n)=L_n$ in case $n\equiv 1\pmod 6$ and $n\equiv 4\pmod 6$, while for the remaining $4$ residue classes $\nabla(n)=L_n$ or $\nabla(n)=L_n+1$. In this paper, we provide optimal constructions in the odd residue classes $n\equiv3,5\pmod6$, (proving $\nabla(n)=L_n$) and a geometric obstruction showing that equality in lower bound is impossible when $n\equiv0,2\pmod6$ (yielding $\nabla(n)=L_n+1$). Starting with $n=3$, the resulting sequence is thus given by \[ \nabla(n)=\bigg{\lceil}\frac{n^2}{3}-\frac{n}{6}+\frac{4}{3}\bigg{\rceil}-\bigg{\lceil}\frac{n}{2}\bigg{\rceil}. \]