# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/

Search: id:a027624
Showing 1-1 of 1

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

# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE