Title: On density of subgraphs of Cartesian products,
Abstract: 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$ of arbitrary connected graphs. Namely, we show that
$\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)$ is the maximum ratio $\frac{|E(H')|}{|V(H')|}$ over all
subgraphs $H'$ 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,\ldots,G_m$ belong to the class ${\mathcal
G}(H)$ of all finite connected graphs not containing a given graph $H$ as a
minor, then for any subgraph $G$ of $G_1\times\cdots\times G_m$ a sharper
inequality $\frac{|E(G)|}{|V(G)|}\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.