A027624 Number of independent vertex sets in the n-hypercube graph Q_n.

2, 3, 7, 35, 743, 254475, 19768832143

Offset: 0

Author

R. H. Hardin

Keywords

• nonn
• nice
• hard
• more

Comments

Also the number of vertex covers of Q_n. - Eric W. Weisstein, Jan 04 2014

A. Sapozhenko proved that a(n) ~ 2 * sqrt(e) * 2^(2^(n-1)). See link (Galvin, 2006). - Daniel Forgues, Feb 11 2015

The cardinality of the largest independent vertex set (the vertex independence number) of the n-hypercube graph Q_n is 1 for n = 0, 2^(n-1) for n >= 1. Except for n = 0, there are two such sets (whose elements have binary labels which are bitwise complement of each other) that represent a vertex coloring, with chromatic number 2, of Q_n. - Daniel Forgues, Feb 11 2015, Feb 16-17 2015

Number of independent vertex pairs for Q_n, n >= 1: 2^(n-1) * (2^n - (n+1)) = T_(2^n - 1) - n * 2^(n-1) = L_n - E_n = A006516(n) - A001787(n), where L_n is the number of vertex pairs and E_n is the number of vertex pairs yielding edges. The g.f. is 2 x^2 / ((1-2x)^2 (1-4x)). (A000431(n+1), n >= 1.) - Daniel Forgues, Feb 17 2015

Number of independent vertex sets with 2^(n-1) - 1 items for Q_n: 2^n = 2 * (2^(n-1) choose 2^(n-1) - 1). - Daniel Forgues, Feb 18 2015

Examples

			a(0) = 2 since {} and {0} are independent vertex sets of Q_0, which is the graph consisting of a single vertex labeled 0.
a(1) = 3 since Q_1 = 0---1 has independent vertex sets {}, {0}, {1}.
From _Daniel Forgues_, Feb 11-12 2015, Feb 17 2015: (Start)
Independent vertex set (resp. vertex cover) of graph G: vertex subset of G such that at most (resp. at least) one vertex represent an edge of G.
Vertices of Q_n are adjacent if and only if a single digit differs in the binary representation of their labels, ranging from 0 to 2^n - 1.
a(2) = 7 since Q_2 is
  00---01
  |     |
  10---11
with vertex adjacency submatrix M_2 =
  M_1
  I_2 M_1
for 0 <= i <= 3 and 0 <= j < i
    00 01 10 11
    ___________
00 |
01 | 1
10 | 1  0
11 | 0  1  1
yielding the 1 + 4 trivial: { } and {00}, {01}, {10}, {11};
the 2 (= 0 + (4 - 2) + 0) pairs with adjacency 0: {10, 01}, {11, 00};
for a total of 7 = 1 + 2^2 + 2 independent vertex sets.
a(3) = 35 since Q_3 is
  000---------001
  | \         / |
  |  100---101  |
  |  |       |  |
  |  110---111  |
  | /         \ |
  010---------011
with vertex adjacency submatrix M_3 =
  M_2
  I_4 M_2
for 0 <= i <= 7 and 0 <= j < i
     000 001 010 011 100 101 110 111
     ________________________________
000 |
001 |  1
010 |  1   0
011 |  0   1   1
100 |  1   0   0   0
101 |  0   1   0   0   1
110 |  0   0   1   0   1   0
111 |  0   0   0   1   0   1   1
yielding the 1 + 8 trivial: { } and
  {000}, {001}, {010}, {011}, {100}, {101}, {110}, {111};
the 16 (= 2 + (16 - 4) + 2) pairs with adjacency 0:
  {010, 001}, {011, 000}, {100, 001}, {100, 010},
  {100, 011}, {101, 000}, {101, 010}, {101, 011},
  {110, 000}, {110, 001}, {110, 011}, {110, 101},
  {111, 000}, {111, 001}, {111, 010}, {111, 100};
the 8 triples whose subset pairs are all among the above 16 pairs:
  {100, 010, 001}, {101, 011, 000}, {110, 011, 000}, {110, 101, 000},
  {110, 101, 011}, {111, 010, 001}, {111, 100, 001}, {111, 100, 010};
the 2 quadruples whose subset triples are all among the above 8 triples:
  {10, 01} & 1 union {11, 00} & 0 =
    {110, 101, 011, 000} and
  {10, 01} & 0 union {11, 00} & 1 =
    {111, 100, 010, 001};
for a total of 35 = 1 + 2^3 + 16 + 8 + 2 independent vertex sets. (End)
The above 2 quadruples represent a vertex 2-coloring of Q_3. - _Daniel Forgues_, Feb 17 2015
a(4) = 743 since Q_4 is (...) with vertex adjacency submatrix M_4 =
  M_3
  I_8 M_3
for 0 <= i <= 15 and 0 <= j < i (...) yielding the 1 + 16 trivial: (...);
the 88 (= 16 + (64 - 8) + 16) pairs with adjacency 0: (...);
the 208 triples: (...); the 228 quadruples: (...);
the 128 quintuples: (...); the 56 sextuples: (...);
the 16 (= 2 * (8 choose 7)) septuples: (...);
and the 2 octuples (representing a vertex 2-coloring of Q_4):
  {110, 101, 011, 000} & 1 union {111, 100, 010, 001} & 0 =
    {1101, 1011, 0111, 0001, 1110, 1000, 0100, 0010} and
  {110, 101, 011, 000} & 0 union {111, 100, 010, 001} & 1 =
    {1100, 1010, 0110, 0000, 1111, 1001, 0101, 0011}.
- _Daniel Forgues_, Feb 17-18 2015
		

References

• David Galvin, Independent sets in the discrete hypercube, arXiv preprint arXiv:1901.0199, January 2019 [N. J. A. Sloane, Apr 29 2019]
• Ilinca, Liviu, and Jeff Kahn. "Counting maximal antichains and independent sets." Order 30.2 (2013): 427-435.

Links

• David Galvin, Independent sets in the discrete hypercube, 2006.
• Quora, What does the sequence A027624 for "Number of independent vertex sets in the n-hypercube graph Q_n" mean?
• Eric Weisstein's World of Mathematics, Hypercube Graph
• Eric Weisstein's World of Mathematics, Independent Vertex Set
• Eric Weisstein's World of Mathematics, Vertex Cover

Crossrefs

Cf. A354802 (by set size), A354082 (alternating sum), A284707 (maximal), A366425 (maximal non-isomorphic).

A000431(n+1), n >= 1. (Number of independent vertex pairs of Q_n.)

Programs

Maple

Nbh:= proc(x)
local i,n;
n:= nops(x);
{seq(subsop(i=1-x[i], x), i=1..n)};
end proc:
F:= proc(S) option remember;
   local s, Sp;
   if nops(S) = 0 then return 1 fi;
   s:= S[1];
   Sp:= S[2..-1];
   F(Sp) + F(Sp minus Nbh(s))
end proc:
G[0]:= {[]}:
a[0]:= F(G[0]):
for d from 1 to 6 do
  G[d]:= map(t -> ([0,op(t)],[1,op(t)]),G[d-1]);
  a[d]:= F(G[d]);
od:
seq(a[d],d=0..6); # Robert Israel, Feb 18 2015

Mathematica

stableSets[u_, Q_] := If[Length[u] === 0, {{}}, With[{w = First[u]}, Join[stableSets[DeleteCases[u, w], Q], Prepend[#, w] & /@ stableSets[DeleteCases[u, r_ /; r === w || Q[r, w] || Q[w, r]], Q]]]];
Table[Length[stableSets[Subsets[Range[n]], And[Length[#1] + 1 === Length[#2], Complement[#1, #2] === {}] &]], {n, 0, 5}] (* Gus Wiseman, Mar 24 2016 *)
Table[Length[Union @@ (Subsets /@ FindIndependentVertexSet[HypercubeGraph[n], Infinity, All])], {n, 0, 5}] (* Eric W. Weisstein, Sep 21 2017 *)

Extensions

Correction of a(0) by Eric W. Weisstein, Jan 04 2014, re-established by M. F. Hasler, Feb 09 2015