Inducibility in the hypercube

2022/09/10 by John Goldwasser, Goldwasser, John, Ryan N. Hansen +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Interconnection Networks and Systems

paper · pdf · doi:10.48550/arxiv.2209.04740

openalex publication_date 2022/09/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 exact copy of H if there is an automorphism of Q_d which sends H onto K. Let n≥ 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∩ 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₃ and Q₄ as well as for an infinite family of configurations. There are strong connections with the inducibility of graphs.

Related

• Maximum density of vertex-induced perfect cycles and paths in the\n hypercube
• Some exact values of the inducibility and statistics constants for hypercubes
• Almost partitioning the hypercube into copies of a graph
• An extremal theorem in the hypercube
• Decomposing the vertex set of a hypercube into isomorphic subgraphs