A354082 -id:A354082 - cp's OEIS frontend

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

2, 3, 7, 35, 743, 254475, 19768832143

Offset: 0

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

			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

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.

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

Cf. A354802 (by set size), A354082 (alternating sum), A284707 (maximal), A366425 (maximal non-isomorphic).

A000431(n+1), n >= 1. (Number of independent vertex pairs of Q_n.)

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

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 *)

Correction of a(0) by Eric W. Weisstein, Jan 04 2014, re-established by M. F. Hasler, Feb 09 2015

A354802 Irregular triangle read by rows where T(n,k) is the number of independent sets of size k in the n-hypercube graph.

Original entry on oeis.org

1, 1, 1, 2, 1, 4, 2, 1, 8, 16, 8, 2, 1, 16, 88, 208, 228, 128, 56, 16, 2, 1, 32, 416, 2880, 11760, 29856, 48960, 54304, 44240, 29920, 17952, 9088, 3672, 1120, 240, 32, 2, 1, 64, 1824, 30720, 342400, 2682432, 15328064, 65515840, 213464240, 538811200, 1070860384, 1708551424, 2245780976, 2517976640, 2509047680

Offset: 0

Christopher Flippen, Jun 06 2022

The independence number alpha(G) of a graph is the cardinality of the largest independent vertex set. The n-hypercube has alpha(G) = 1 for n = 0 and alpha(G) = 2^(n-1) for n >= 1. The independence polynomial for the n-hypercube is given by Sum_{k=0..alpha(G)} T(n,k)*t^k.
Since 0 <= k <= alpha(G), row n has length 2^(n-1) + 1 except for n = 0 which has length 2.
Jenssen, Perkins and Potukuchi proved asymptotics for independent sets of given size.

			Triangle begins:
  n=0: 1, 1
  n=1: 1, 2
  n=2: 1, 4, 2
  n=3: 1, 8, 16, 8, 2
  n=4: 1, 16, 88, 208, 228, 128, 56, 16, 2
The 3-hypercube graph has independence polynomial 1 + 8*t + 16*t^2 + 8*t^3 + 2*t^4.

Christopher Flippen, Table of n, a(n) for n = 0..71
M. Jenssen, W. Perkins and A. Potukuchi, Independent sets of a given size and structure in the hypercube, Combinatorics, Probability and Computing, 2022, 1-19; see also arXiv:2106.09709 [math.CO], 2021-2022.
Eric Weisstein's World of Mathematics, Hypercube graph
Eric Weisstein's World of Mathematics, Independence polynomial

Cf. A027624 (row sums), A354082 (alternating sums).

from sage.graphs.independent_sets import IndependentSets
def row(n):
    if n == 0:
        g = graphs.CompleteGraph(1)
        setCounts = [0, 0]
    else:
        g = graphs.CubeGraph(n)
        setCounts = [0] * (pow(2,n - 1) + 1)
    for Iset in IndependentSets(g):
        setCounts[len(Iset)] += 1
    return setCounts
# Christopher Flippen and Scott Taylor, Jun 06 2022

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Extensions