Abstract:The avoidance of induced forests, or induced acyclic subgraphs, in $d$-dimensional grid graphs, or lattice graphs, has been studied in Alon et al. and later in Caragiannis et al., finding upper and lower bounds with respect to the number of vertices in a single dimension $n$ and the dimension $d$. In this work, we study the avoidance of induced $C_4$-free subgraphs, a superset of induced forests, of $2$-dimensional grid graphs $G$ and characterize the maximal sets $S \subseteq V$ such that the induced subgraph $G_S$ of $G$ with vertex set $S$ is $C_4$-free. Additionally, we will give upper and lower bounds on the number of $C_4$-free induced subgraphs with slightly fewer vertices than contained in the maximum.
| Comments: | A few small corrections were made to previous draft. Taiki was an undergrad student; this is sort of like an REU paper |
| Subjects: | Combinatorics (math.CO) |
| MSC classes: | 05D99 |
| Cite as: | arXiv:2604.08397 [math.CO] |
| (or arXiv:2604.08397v2 [math.CO] for this version) | |
| https://doi.org/10.48550/arXiv.2604.08397 arXiv-issued DOI via DataCite |
From: Ernie Croot [view email]
[v1]
Thu, 9 Apr 2026 15:57:53 UTC (9 KB)
[v2]
Mon, 25 May 2026 20:19:48 UTC (9 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。