On density of subgraphs of Cartesian products

In this paper, we extend two classical results about the density of subgraphs of hypercubes to subgraphs $G$ of Cartesian products $G_1\times\cdots\times G_m$ofarbitraryconnectedgraphs\mathrm{.}Namely,weshowthat$\frac{|E(G)|}{|V(G)|}\le \lceil 2\max{ $\text{dens}$(G_1),\ldots,$\text{dens}$(G_m)} \rceil\log|V(G)|$,where$$\text{dens}$(H)$isthemaximumratio$\frac{|E(H’)|}{|V(H’)|}$ over all subgraphs $H^{\mathrm{\prime }}$ of $H$. We introduce the notions of VC-dimension $\text{VC-dim}(G)$ and VC-density $\text{VC-dens}(G)$ of a subgraph $G$ of a Cartesian product $G_1\times \cdots \times G_m$, generalizing the classical Vapnik-Chervonenkis dimension of set-families (viewed as subgraphs of hypercubes). We prove that if $G_1,\dots ,G_m$ belong to the class ${\mathcal G}(H)$ofallfiniteconnectedgraphsnotcontainingagivengraph$H$ as a minor, then for any subgraph $G$ of $G_1\times \cdots \times G_m$ a sharper inequality $\frac{\mathrm{\mid }E(G)\mathrm{\mid }}{\mathrm{\mid }V(G)\mathrm{\mid }}\le \text{VC-dim}(G)\alpha (H)$ holds, where $\alpha (H)$ is the density of the graphs from $\mathcal{G}(H)$. We refine and sharpen those two results to several specific graph classes. We also derive upper bounds (some of them polylogarithmic) for the size of adjacency labeling schemes of subgraphs of Cartesian products.