PreprintarXiv licencearXiv
Maximal subsets of n× n board without cycles
Abstract
Define ∇(n) as the least possible number of cells that must be removed from the n× n square board in order to leave no cycles. Put Ln=⌈((n−1)2+1)/3⌉. The results of Luccio, Madelaine-Stewart, and Lien-Fu-Shih imply that ∇(n)=Ln in case n≡ 1pmod 6 and n≡ 4pmod 6, while for the remaining $4$ residue classes ∇(n)=Ln or ∇(n)=Ln+1. In this paper, we provide optimal constructions in the odd residue classes n≡3,5pmod6, (proving ∇(n)=Ln) and a geometric obstruction showing that equality in lower bound is impossible when n≡0,2pmod6 (yielding ∇(n)=Ln+1). Starting with n=3, the resulting sequence is thus given by ∇(n)=⌈n2/3−n/6+4/3⌉−⌈n/2⌉.
Related
- Extremal graphs without cycles of length 0 modulo 4
- Extremal hypergraphs without generalized 4-cycles
- On graphs without cycles of length $0$ modulo $3$ or $4$ modulo $6$
- Total-coloring of planar graphs with maximum degree 6 and without prescribed 4-cycles
- Spectral extremal hypergraphs without long Berge cycles
BibTeX
@misc{alkauskas2026maximal,
title = {{Maximal subsets of $n\times n$ board without cycles}},
author = {Giedrius Alkauskas},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.20034},
eprint = {2610.20034},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.20034},
}
RIS
TY - UNPB
TI - Maximal subsets of n× n board without cycles
AU - Giedrius Alkauskas
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2610.20034
UR - https://arxiv.org/abs/2610.20034
AB - Define ∇(n) as the least possible number of cells that must be removed from the n× n square board in order to leave no cycles. Put L_n=⌈((n−1)^2+1)/3⌉. The results of Luccio, Madelaine-Stewart, and Lien-Fu-Shih imply that ∇(n)=L_n in case n≡ 1pmod 6 and n≡ 4pmod 6, while for the remaining $4$ residue classes ∇(n)=L_n or ∇(n)=L_n+1. In this paper, we provide optimal constructions in the odd residue classes n≡3,5pmod6, (proving ∇(n)=L_n) and a geometric obstruction showing that equality in lower bound is impossible when n≡0,2pmod6 (yielding ∇(n)=L_n+1). Starting with n=3, the resulting sequence is thus given by ∇(n)=⌈n^2/3−n/6+4/3⌉−⌈n/2⌉.
ER -