The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A027624 Number of independent vertex sets in the n-hypercube graph Q_n. 9
 2, 3, 7, 35, 743, 254475, 19768832143 (list; graph; refs; listen; history; text; internal format)
 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 Daniel Forgues, Feb 19 2015 (with help from Robert Israel): (Start) Number of vertices: 0     1     2     3     4     5     6     7     8 a(0) =      2 = sum(1,    1) a(1) =      3 = sum(1,    2) a(2) =      7 = sum(1,    4,    2) a(3) =     35 = sum(1,    8,   16,    8,    2) a(4) =    743 = sum(1,   16,   88,  208,  228,  128,   56,   16,    2) a(5) = 254475 = sum(1, 32, 416, 2880, 11760, 29856, 48960, 54304, 44240, 29920, 17952, 9088, 3672, 1120, 240, 32, 2) (End) 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 A000431(n+1), n >= 1. (Number of independent vertex pairs of Q_n.) Sequence in context: A101484 A004026 A135907 * A165744 A330554 A304524 Adjacent sequences:  A027621 A027622 A027623 * A027625 A027626 A027627 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified November 28 06:42 EST 2021. Contains 349401 sequences. (Running on oeis4.)