2020/09/18 by John Goldwasser, Goldwasser, John, Ryan N. Hansen +1
Computer Science · Engineering · Mathematics · #05D05 (Primary) 05D10 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2009.09037
openalex publication_date 2020/09/18 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
Let H and K be subsets of the vertex set V(Qd) of the d-cube Qd\n(we call H and K configurations in Qd). We say K is an \exact\ncopy of H if there is an automorphism of Qd which sends H to K. If\nd is a positive integer and H is a configuration in Qd, we define\n\π(H,d) to be the limit as n goes to infinity of the maximum fraction,\nover all subsets S of V(Qn), of sub-d-cubes of Qn whose intersection\nwith S is an exact copy of H. We determine \π(C8,4) and \π(P4,3)\nwhere C8 is a "perfect" 8-cycle in Q4 and P4 is a "perfect" path with\n4 vertices in Q3, and make conjectures about \π(C2d,d) and\n\π(Pd+1,d) for larger values of d. In our proofs there are connections\nwith counting the number of sequences with certain properties and with the\ninducibility of certain small graphs. In particular, we needed to determine the\ninducibility of two vertex disjoint edges in the family of bipartite graphs.\n