login
Number of independent vertex sets in the n-hypercube graph Q_n.
13

%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