Sign up or sign in
logo

Contributed Papers

Icon: calendar Contributed Papers Session #1.5

Subevent of Contributed Papers Session #1 (Geometry & Topology)

Stevens Hall 400

2026 Mar 27 from 03:20PM to 03:35PM (Central Time (US & Canada))

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. (2001) and later in Caragiannis et al. (2002), 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.