A354082 - OEIS

%I #37 Jul 18 2022 06:07:19

%S 0,-1,-1,3,7,11,143,7715

%N The independence polynomial of the n-hypercube graph evaluated at -1.

%C 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)} A354802(n,k)*t^k, meaning that a(n) is the alternating sum of row n of A354802.

%C Jenssen, Perkins and Potukuchi proved asymptotics for independent sets of given size.

%C It appears that this sequence remains positive for n > 3.

%H M. Jenssen, W. Perkins and A. Potukuchi, <a href="https://doi.org/10.1017/S0963548321000559">Independent sets of a given size and structure in the hypercube</a>, Combinatorics, Probability and Computing, 2022, 1-19; see also <a href="https://arxiv.org/abs/2106.09709">arXiv:2106.09709</a> [math.CO], 2021-2022.

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/HypercubeGraph.html">Hypercube graph</a>

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/IndependencePolynomial.html">Independence polynomial</a>

%e Row 3 of A354802 is 1, 8, 16, 8, 2. This means the 3-hypercube cube graph has independence polynomial 1 + 8*t + 16*t^2 + 8*t^3 + 2*t^4. Taking the alternating row sum of row 3, or evaluating the polynomial at -1, gives us 1 - 8 + 16 - 8 + 2 = 3 = a(3).

%o (Sage) from sage.graphs.connectivity import connected_components

%o def recurse(g):

%o     if g.order() == 0:

%o             return 1

%o     comp = g.connected_components()

%o     if len(comp[-1]) == 1:

%o         return 0

%o     elif len(comp) > 1:

%o         prod = 1

%o         for c in comp:

%o             if prod == 0:

%o                 return 0

%o             else:

%o                 prod = prod*recurse(g.subgraph(vertices=c))

%o         return prod

%o     min_degree_vertex = g.vertices()[0]

%o     for v in g.vertices():

%o         if g.degree(v) < g.degree(min_degree_vertex):

%o             min_degree_vertex = v

%o     to_remove_edge =  g.edges_incident(min_degree_vertex)[0]

%o     to_remove_vertices = [to_remove_edge[0], to_remove_edge[1]]

%o     to_remove_vertices.extend(g.neighbors(to_remove_edge[0]))

%o     to_remove_vertices.extend(g.neighbors(to_remove_edge[1]))

%o     to_remove_vertices = list(set(to_remove_vertices))

%o     without_neighborhoods = copy(g)

%o     without_edge = copy(g)

%o     without_neighborhoods.delete_vertices(to_remove_vertices)

%o     without_edge.delete_edge(to_remove_edge)

%o     return recurse(without_edge) - recurse(without_neighborhoods)

%o def a(n):

%o     if n == 0:

%o         return recurse(graphs.CompleteGraph(1))

%o     else:

%o         return recurse(graphs.CubeGraph(n))

%o # _Christopher Flippen_ and Scott Taylor, Jun 2022

%Y Cf. A027624, A354802.

%K sign,more

%O 0,4

%A _Christopher Flippen_, Jun 05 2022