OFFSET
0,4
COMMENTS
The independence number alpha(G) of a graph is the cardinality of the largest independent vertex set. The n-hypercube has alpha(G) = 1 for n = 0 and alpha(G) = 2^(n-1) for n >= 1. The independence polynomial for the n-hypercube is given by Sum_{k=0..alpha(G)} T(n,k)*t^k.
Since 0 <= k <= alpha(G), row n has length 2^(n-1) + 1 except for n = 0 which has length 2.
Jenssen, Perkins and Potukuchi proved asymptotics for independent sets of given size.
LINKS
Christopher Flippen, Table of n, a(n) for n = 0..71
M. Jenssen, W. Perkins and A. Potukuchi, Independent sets of a given size and structure in the hypercube, Combinatorics, Probability and Computing, 2022, 1-19; see also arXiv:2106.09709 [math.CO], 2021-2022.
Eric Weisstein's World of Mathematics, Hypercube graph
Eric Weisstein's World of Mathematics, Independence polynomial
EXAMPLE
Triangle begins:
n=0: 1, 1
n=1: 1, 2
n=2: 1, 4, 2
n=3: 1, 8, 16, 8, 2
n=4: 1, 16, 88, 208, 228, 128, 56, 16, 2
The 3-hypercube graph has independence polynomial 1 + 8*t + 16*t^2 + 8*t^3 + 2*t^4.
PROG
(Sage) from sage.graphs.independent_sets import IndependentSets
def row(n):
if n == 0:
g = graphs.CompleteGraph(1)
setCounts = [0, 0]
else:
g = graphs.CubeGraph(n)
setCounts = [0] * (pow(2, n - 1) + 1)
for Iset in IndependentSets(g):
setCounts[len(Iset)] += 1
return setCounts
# Christopher Flippen and Scott Taylor, Jun 2022
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Christopher Flippen, Jun 06 2022
STATUS
approved