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

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

Offset: 0

Author

Christopher Flippen, Jun 05 2022

Keywords

• sign
• more

Comments

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.

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

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

Examples

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

Links

• 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

Crossrefs

Cf. A027624, A354802.

Programs

Sage

from sage.graphs.connectivity import connected_components
def recurse(g):
    if g.order() == 0:
            return 1
    comp = g.connected_components()
    if len(comp[-1]) == 1:
        return 0
    elif len(comp) > 1:
        prod = 1
        for c in comp:
            if prod == 0:
                return 0
            else:
                prod = prod*recurse(g.subgraph(vertices=c))
        return prod
    min_degree_vertex = g.vertices()[0]
    for v in g.vertices():
        if g.degree(v) < g.degree(min_degree_vertex):
            min_degree_vertex = v
    to_remove_edge =  g.edges_incident(min_degree_vertex)[0]
    to_remove_vertices = [to_remove_edge[0], to_remove_edge[1]]
    to_remove_vertices.extend(g.neighbors(to_remove_edge[0]))
    to_remove_vertices.extend(g.neighbors(to_remove_edge[1]))
    to_remove_vertices = list(set(to_remove_vertices))
    without_neighborhoods = copy(g)
    without_edge = copy(g)
    without_neighborhoods.delete_vertices(to_remove_vertices)
    without_edge.delete_edge(to_remove_edge)
    return recurse(without_edge) - recurse(without_neighborhoods)
def a(n):
    if n == 0:
        return recurse(graphs.CompleteGraph(1))
    else:
        return recurse(graphs.CubeGraph(n))
# Christopher Flippen and Scott Taylor, Jun 05 2022