%I #110 Nov 05 2023 10:26:02
%S 2,3,7,35,743,254475,19768832143
%N Number of independent vertex sets in the n-hypercube graph Q_n.
%C Also the number of vertex covers of Q_n. - _Eric W. Weisstein_, Jan 04 2014
%C A. Sapozhenko proved that a(n) ~ 2 * sqrt(e) * 2^(2^(n-1)). See link (Galvin, 2006). - _Daniel Forgues_, Feb 11 2015
%C 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
%C 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
%C 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
%D David Galvin, Independent sets in the discrete hypercube, arXiv preprint arXiv:1901.0199, January 2019 [_N. J. A. Sloane_, Apr 29 2019]
%D Ilinca, Liviu, and Jeff Kahn. "Counting maximal antichains and independent sets." Order 30.2 (2013): 427-435.
%H David Galvin, <a href="https://www3.nd.edu/~dgalvin1/pdf/countingindsetsinQd.pdf">Independent sets in the discrete hypercube</a>, 2006.
%H Quora, <a href="https://www.quora.com/What-does-the-sequence-A027624-for-Number-of-independent-vertex-sets-in-the-n-hypercube-graph-Q_n-mean">What does the sequence A027624 for "Number of independent vertex sets in the n-hypercube graph Q_n" mean?</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HypercubeGraph.html">Hypercube Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/IndependentVertexSet.html">Independent Vertex Set</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/VertexCover.html">Vertex Cover</a>
%e a(0) = 2 since {} and {0} are independent vertex sets of Q_0, which is the graph consisting of a single vertex labeled 0.
%e a(1) = 3 since Q_1 = 0---1 has independent vertex sets {}, {0}, {1}.
%e From _Daniel Forgues_, Feb 11-12 2015, Feb 17 2015: (Start)
%e 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.
%e 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.
%e a(2) = 7 since Q_2 is
%e 00---01
%e | |
%e 10---11
%e with vertex adjacency submatrix M_2 =
%e M_1
%e I_2 M_1
%e for 0 <= i <= 3 and 0 <= j < i
%e 00 01 10 11
%e ___________
%e 00 |
%e 01 | 1
%e 10 | 1 0
%e 11 | 0 1 1
%e yielding the 1 + 4 trivial: { } and {00}, {01}, {10}, {11};
%e the 2 (= 0 + (4 - 2) + 0) pairs with adjacency 0: {10, 01}, {11, 00};
%e for a total of 7 = 1 + 2^2 + 2 independent vertex sets.
%e a(3) = 35 since Q_3 is
%e 000---------001
%e | \ / |
%e | 100---101 |
%e | | | |
%e | 110---111 |
%e | / \ |
%e 010---------011
%e with vertex adjacency submatrix M_3 =
%e M_2
%e I_4 M_2
%e for 0 <= i <= 7 and 0 <= j < i
%e 000 001 010 011 100 101 110 111
%e ________________________________
%e 000 |
%e 001 | 1
%e 010 | 1 0
%e 011 | 0 1 1
%e 100 | 1 0 0 0
%e 101 | 0 1 0 0 1
%e 110 | 0 0 1 0 1 0
%e 111 | 0 0 0 1 0 1 1
%e yielding the 1 + 8 trivial: { } and
%e {000}, {001}, {010}, {011}, {100}, {101}, {110}, {111};
%e the 16 (= 2 + (16 - 4) + 2) pairs with adjacency 0:
%e {010, 001}, {011, 000}, {100, 001}, {100, 010},
%e {100, 011}, {101, 000}, {101, 010}, {101, 011},
%e {110, 000}, {110, 001}, {110, 011}, {110, 101},
%e {111, 000}, {111, 001}, {111, 010}, {111, 100};
%e the 8 triples whose subset pairs are all among the above 16 pairs:
%e {100, 010, 001}, {101, 011, 000}, {110, 011, 000}, {110, 101, 000},
%e {110, 101, 011}, {111, 010, 001}, {111, 100, 001}, {111, 100, 010};
%e the 2 quadruples whose subset triples are all among the above 8 triples:
%e {10, 01} & 1 union {11, 00} & 0 =
%e {110, 101, 011, 000} and
%e {10, 01} & 0 union {11, 00} & 1 =
%e {111, 100, 010, 001};
%e for a total of 35 = 1 + 2^3 + 16 + 8 + 2 independent vertex sets. (End)
%e The above 2 quadruples represent a vertex 2-coloring of Q_3. - _Daniel Forgues_, Feb 17 2015
%e a(4) = 743 since Q_4 is (...) with vertex adjacency submatrix M_4 =
%e M_3
%e I_8 M_3
%e for 0 <= i <= 15 and 0 <= j < i (...) yielding the 1 + 16 trivial: (...);
%e the 88 (= 16 + (64 - 8) + 16) pairs with adjacency 0: (...);
%e the 208 triples: (...); the 228 quadruples: (...);
%e the 128 quintuples: (...); the 56 sextuples: (...);
%e the 16 (= 2 * (8 choose 7)) septuples: (...);
%e and the 2 octuples (representing a vertex 2-coloring of Q_4):
%e {110, 101, 011, 000} & 1 union {111, 100, 010, 001} & 0 =
%e {1101, 1011, 0111, 0001, 1110, 1000, 0100, 0010} and
%e {110, 101, 011, 000} & 0 union {111, 100, 010, 001} & 1 =
%e {1100, 1010, 0110, 0000, 1111, 1001, 0101, 0011}.
%e - _Daniel Forgues_, Feb 17-18 2015
%p Nbh:= proc(x)
%p local i,n;
%p n:= nops(x);
%p {seq(subsop(i=1-x[i], x), i=1..n)};
%p end proc:
%p F:= proc(S) option remember;
%p local s, Sp;
%p if nops(S) = 0 then return 1 fi;
%p s:= S[1];
%p Sp:= S[2..-1];
%p F(Sp) + F(Sp minus Nbh(s))
%p end proc:
%p G[0]:= {[]}:
%p a[0]:= F(G[0]):
%p for d from 1 to 6 do
%p G[d]:= map(t -> ([0,op(t)],[1,op(t)]),G[d-1]);
%p a[d]:= F(G[d]);
%p od:
%p seq(a[d],d=0..6); # _Robert Israel_, Feb 18 2015
%t 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]]]];
%t Table[Length[stableSets[Subsets[Range[n]], And[Length[#1] + 1 === Length[#2], Complement[#1, #2] === {}] &]], {n, 0, 5}] (* _Gus Wiseman_, Mar 24 2016 *)
%t Table[Length[Union @@ (Subsets /@ FindIndependentVertexSet[HypercubeGraph[n], Infinity, All])], {n, 0, 5}] (* _Eric W. Weisstein_, Sep 21 2017 *)
%Y Cf. A354802 (by set size), A354082 (alternating sum), A284707 (maximal), A366425 (maximal non-isomorphic).
%Y A000431(n+1), n >= 1. (Number of independent vertex pairs of Q_n.)
%K nonn,nice,hard,more
%O 0,1
%A _R. H. Hardin_
%E Correction of a(0) by _Eric W. Weisstein_, Jan 04 2014, re-established by _M. F. Hasler_, Feb 09 2015