turkmath.org

The n-cube Qn is the graph whose vertex set is the set of all binary n-tuples, with two vertices adjacent if and only if they differ in precisely one coordinate. Let G be an induced subgraph of the d-cube Qd. We define f(d,G), the d-cube density of G, to be the limit -as n goes to infinity- of the maximum fraction, over all subsets J of the vertex set of the n-cube Qn, of sub-d-cubes of Qn whose intersection with J induces an exact copy of G (isomorphic to G, with the same embedding in Qd).
In general, it is difficult to determine f(d,G). We show that if C is a “perfect” 8-cycle (4 pairs of vertices at distance 4) then f(4,C) = 3/32. Surprisingly, to establish the upper bound we needed to determine the Turán density of {P4, P5}, where P4 = {abcd, abce, abde} and P5 = {abcd, abce, adef} and where the only 4-graphs (hypergraph where all the edges have 4 elements) allowed are those where there is a bipartition of the vertex set such that each edge has two vertices in each part. (This is the limit, as n goes to infinity, of the maximum fraction of 4-subsets one can choose from an n-set, so that there is no copy of P4 or P5.) We note that the link graphs of the vertex a in P4 and P5 are the 3-graphs known as K4- and F5, the forbidden 3-graphs in Bollobás’ well-known theorem on the maximum number of edges in a 3-graph where no edge contains the symmetric difference of two others.