Inducibility in the hypercube

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 g e q d

be an integer, let

H

be a configuration in

Q_{d}

and let

S

be a configuration in

Q_{n}

. We let

l a m b d a (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 c a p R

is an exact copy of

H

, and we define the

d

-cube density

l a m b d a (H, d)

of

H

to be the limit as

n

goes to infinity of

l a m b d a (H, d, n)

. We determine

l a m b d a (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.

Cites Work

This page was built for publication: Inducibility in the hypercube