login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A027624 Number of independent vertex sets in the n-hypercube graph Q_n. 3
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

Ilinca, Liviu, and Jeff Kahn. "Counting maximal antichains and independent sets." Order 30.2 (2013): 427-435.

LINKS

Table of n, a(n) for n=0..6.

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

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 A304524 A034900

Adjacent sequences:  A027621 A027622 A027623 * A027625 A027626 A027627

KEYWORD

nonn,nice,hard,more

AUTHOR

R. H. Hardin

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 18 13:22 EST 2018. Contains 317306 sequences. (Running on oeis4.)