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 G1□⋯□Gm of arbitrary connected graphs. Namely, we show that (∣E(G)|/∣V(G)∣)≤⌈2max{dens(G1),...,dens(Gm)}⌉log∣V(G)∣, where dens(H) is the maximum ratio ∣E(H′)∣/∣V(H′)∣ taken over all subgraphs H′ of H. We introduce the notions of VC‐dimension VC‐dim⁡(G) and VC‐density VC‐dens(G) of a subgraph G of a Cartesian product G1□⋯□Gm, generalizing the classical Vapnik‐Chervonenkis dimension of set‐families (viewed as subgraphs of hypercubes). We prove that if G1,...,Gm belong to the class G(H) of all finite connected graphs not containing a given graph H as a minor, then for any subgraph G of G1□⋯□Gm the sharper inequality (∣E(G)∣/∣V(G)∣)≤μ(H)⋅VC‐dim⁡*(G) holds, where μ(H) is the supremum of the densities of the graphs from G(H). We refine and sharpen these 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. [ABSTRACT FROM AUTHOR]