OFFSET
0,1
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
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.
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
EXAMPLE
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
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 *)
CROSSREFS
KEYWORD
nonn,nice,hard,more
AUTHOR
EXTENSIONS
Correction of a(0) by Eric W. Weisstein, Jan 04 2014, re-established by M. F. Hasler, Feb 09 2015
STATUS
approved