cp's OEIS Frontend

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

%I A284707 #38 Feb 16 2025 08:33:43
%S A284707 1,2,2,6,42,1670,1281402
%N A284707 Number of maximal independent vertex sets in the n-hypercube graph Q_n.
%H A284707 Dwight Duffus, Peter Frankl, and Vojtěch Rödl, <a href="https://doi.org/10.1016/j.ejc.2010.08.004">Maximal independent sets in bipartite graphs obtained from Boolean lattices</a>, European Journal of Combinatorics 32.1 (2011): 1-9.
%H A284707 Dwight Duffus, Peter Frankl, and Vojtěch Rödl, <a href="https://doi.org/10.1016/j.dam.2010.09.003">Maximal independent sets in the covering graph of the cube</a>, Discrete Applied Mathematics 161.9 (2013): 1203-1208.
%H A284707 Dmitry I. Ignatov, <a href="https://doi.org/10.1007/978-3-031-35949-1_11">On the Maximal Independence Polynomial of the Covering Graph of the Hypercube up to n = 6</a>, Int'l Conf. Formal Concept Analysis, 2023.
%H A284707 Liviu Ilinca and Jeff Kahn, <a href="https://arxiv.org/abs/1202.4427">Counting maximal antichains and independent sets</a>, arXiv:1202.4427 [math.CO], Feb 2012; Order 30.2 (2013): 427-435.
%H A284707 Jeff Kahn and Jinyoung Park, <a href="https://arxiv.org/abs/1909.04283">The number of maximal independent sets in the Hamming cube</a>, arXiv:1909.04283 [math.CO], 2019.
%H A284707 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/HypercubeGraph.html">Hypercube Graph</a>
%H A284707 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/IndependentVertexSet.html">Independent Vertex Set</a>
%H A284707 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/MaximalIndependentVertexSet.html">Maximal Independent Vertex Set</a>
%F A284707 a(n) ~ 2*n*2^(N/4) where N = 2^n [Kahn and Park]. - _N. J. A. Sloane_, Sep 11 2019
%t A284707 Table[Length @ FindIndependentVertexSet[HypercubeGraph[n], Infinity, All], {n, 0, 6}] (* _Eric W. Weisstein_, Jan 01 2024 *)
%o A284707 (Python)
%o A284707 from networkx import empty_graph, find_cliques
%o A284707 def A284707(n):
%o A284707     k = 1<<n
%o A284707     G = empty_graph(list(range(k)))
%o A284707     G.add_edges_from((a,b) for a in range(k) for b in range(a) if (lambda m: (m&-m)^m if m else 1)(a^b))
%o A284707     return sum(1 for c in find_cliques(G)) # _Chai Wah Wu_, Jan 11 2024
%Y A284707 Cf. A027624 (not necessarily maximal), A366425 (non-isomorphic).
%K A284707 nonn,more
%O A284707 0,2
%A A284707 _Eric W. Weisstein_, Apr 01 2017