4-cycle-free induced subgraphs of grid graphs

Abstract

In this paper we consider sets $S$ of vertices of the $n\times n$ grid graph $G_n$ where the induced subgraph $G_S$ having vertex set $S$ contains no $4$-cycles. We first quickly establish the maximum size of any such induced subgraph. Then, for even $n$ we estimate the number of $4$-cycle-free induced subgraphs of maximum and near-maximum size. If ${\mathcal{F}}_{\epsilon }$ denotes the family of $4$-cycle-free induced subgraphs with at least $(3/4-\epsilon )n^2$ vertices, then we show $$\log |{\mathcal{F}}_0|=(1+o(1))n\log n.$$ Then, we also establish exponential upper and lower bounds for $|{\mathcal{F}}_{\epsilon }|$. This estimate is proved using a local letter-pattern encoding of the unique missing vertex in a set of $2\times 2$ blocks that tile the grid; the upper bound for $|{\mathcal{F}}_{\epsilon }|$ uses a coarser block tiling (using larger blocks). We discuss the problem of closing the gap between our upper and lower bounds for $|{\mathcal{F}}_{\epsilon }|$, and a possible defect-container approach.

A few small corrections were made to previous draft. Taiki was an undergrad student; this is sort of like an REU paper