Inducibility in the hypercube

John Goldwasser; Ryan Hansen

paper

Inducibility in the hypercube

arXiv:2209.04740

Abstract

Let $Q_{d}$ be the hypercube of dimension $d$ and let $H$ and $K$ be subsets of the vertex set $V (Q_{d})$ , called configurations in $Q_{d}$ . We say that $K$ is an \emph{exact copy} of $H$ if there is an automorphism of $Q_{d}$ which sends $H$ onto $K$ . Let $n \geq d$ be an integer, let $H$ be a configuration in $Q_{d}$ and let $S$ be a configuration in $Q_{n}$ . We let $λ (H, d, n)$ be the maximum, over all configurations $S$ in $Q_{n}$ , of the fraction of sub- $d$ -cubes $R$ of $Q_{n}$ in which $S \cap R$ is an exact copy of $H$ , and we define the $d$ -cube density $λ (H, d)$ of $H$ to be the limit as $n$ goes to infinity of $λ (H, d, n)$ . We determine $λ (H, d)$ for several configurations in $Q_{3}$ and $Q_{4}$ as well as for an infinite family of configurations. There are strong connections with the inducibility of graphs.