Sign up or sign in

Contributed Papers

Contributed Papers Session #1.5

Subevent of Contributed Papers Session #1

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

4-cycle-free induced subgraphs of grid graphs

Taiki Aiba <taiba3@gatech.edu>, Georgia Institute of Technology

Coauthors: Ernest Croot

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 provide an upper bound on the size of maximal sets $S \subseteq V$ such that the induced subgraph $H_{S}$ of $G$ with vertex set $S$ is $C_4$-free. Additionally, we will show that the number of maximal $C_4$-free induced subgraphs with number of vertices slightly smaller than this upper bound is sufficiently small.

Back to events