\section{New recurrence relations}
\label{sec:new_rec_rel}

There are two other recurrence relations for the independence polynomial of a simple graph $G$ with an edge $e = \{u, v\}$ that appear to be unknown:
\begin{align}
I(G, x) &= I(G_{\vdel u}, x) + I(G_{\vdel v}, x) - I(G_{\vdel e}, x), \\
&= I(G_{-e}, x) - x \cdot I(G_{/e}, x) + x \cdot I(G_{\vsdel e}, x).
\end{align}

We derive generalizations of both equation for hypergraphs from a graph polynomial in four variables, the so-called generalized subgraph counting polynomial, which counts subgraphs with respect to some invariants.

\begin{defi}[Definition 5.1 in \cite{trinks2012c}]
\label{defi:gscp}
Let $G = (V, E)$ be a hypergraph. The \emph{generalized subgraph counting polynomial} $F(G, v, x, y, z)$ is defined as
\begin{align}
F(G, v, x, y, z) = \sumsr{H = (W, F) \subseteq G}{v^{\abs{W}} \, x^{k(H)} \, y^{\abs{F}} \, z^{\abs{E(\vig{G}{W})}}}.
\end{align}
\end{defi}

This graph polynomial generalizes several well-known graph polynomials, among others, the matching polynomial, the Potts model, the edge elimination polynomial and the subgraph component polynomial \cite[Section 5.2]{trinks2012c}. Furthermore, it satisfies a recurrence relation with respect to an edge deletion.

\begin{theo}[Theorem 5.2 in \cite{trinks2012c}]
\label{theo:gscp_rec_rel}
Let $G = (V, E)$ be a hypergraph with an edge $e \in E$. The generalized subgraph counting polynomial $F(G) = F(G, v, x, y, z)$ satisfies
\begin{align}
& F(G) = z \cdot F(G_{-e}) + v^{\abs{e}-1} \, y \, z \cdot F(G_{/e}) - v^{\abs{e}-1} \, y \, z \cdot F(G_{\vsdel e}) \notag \\
& \phantom{F(G)} \eqspace + (z-1) \cdot \sumsr{\emptyset \subset B \subseteq e}{(-1)^{\abs{B}} \cdot F(G_{\vsdel B})}, \\
& F(E_n) = (1 + v \, x)^n.
\end{align}
\end{theo}

The independence polynomial can be derived from the generalized subgraph counting polynomial through two different techniques. From these, two different recurrence relations follow, although both derivations are based on the fact that in hypergraphs a vertex subset $W$ is independent if the subgraph of $G$ induced by $W$ is edgeless.

\begin{theo} \label{theo:rel_gscp_i_1}
Let $G = (V, E)$ be a hypergraph. The independence polynomial is encoded in the generalized subgraph counting polynomial:
\begin{align}
I(G, x) = H(G, 1, x, 1, 0).
\end{align}
\end{theo}

\begin{proof}
The statement follows directly from the definition of both polynomials:
\begin{align*}
H(G, 1, x, 1, 0)
&= \sumsr{H = (W, F) \subseteq G}{1^{\abs{W}} \, x^{k(H)} \,  1^{\abs{F}} \, 0^{\abs{E(\vig{G}{W})}}} 
= \sumsr{\substack{H = (W, F) \subseteq G \\ \abs{E(\vig{G}{W})} = 0}}{x^{k(H)}} \\
&= \sumsr{\substack{W \subseteq V \\ W \text{ is independent in } G}}{x^{\abs{W}}} 
= I(G, x). \qedhere
\end{align*}
\end{proof}

\begin{coro} \label{coro:rec_rel_hg_e_1}
Let $G = (V, E)$ be a hypergraph with an edge $e \in E$. The independence polynomial satisfies
\begin{align}
I(G, x) = \sumsr{\emptyset \subset W \subseteq e}{(-1)^{\abs{W}+1} \cdot I(G_{\vsdel W}, x)}.
\end{align}
\end{coro}

We give another combinatorial proof via an inclusion-exclusion argument.
\begin{proof}
The independent sets of $G$ are the independent sets of $G_{\edel e}$ not including all vertices of $e$, or, equivalently, missing at least one vertex of $e$. The independent sets of $G_{\edel e}$ missing at least the non-empty vertex set  $W \subseteq e$ are enumerated by $G_{-e \vsdel W} = G_{\vsdel W}$. Consequently, via the principle of inclusion-exclusion the statement follows.
\end{proof}

\begin{theo} \label{theo:rel_gscp_i_2}
Let $G = (V, E)$ be a hypergraph. The independence polynomial is encoded in the generalized subgraph counting polynomial:
\begin{align}
I(G, x) = H(G, x, 1, -1, 1).
\end{align}
\end{theo}

\begin{proof}
The statement follows directly from the definition of both polynomials:
\begin{align*}
H(G, x, 1, -1, 1)
&= \sumsr{H = (W, F) \subseteq G}{x^{\abs{W}} \, 1^{k(H)} \, (-1)^{\abs{F}} \, 1^{\abs{E(\vig{G}{W})}}} \\
&= \sumsr{H = (W, F) \subseteq G}{x^{\abs{W}} \, (-1)^{\abs{F}}} 
= \sumsr{W \subseteq V}{x^{\abs{W}} \sumsr{F \subseteq E(\vig{G}{W})}{(-1)^{\abs{F}}}} \\
&= \sumsr{W \subseteq V}{x^{\abs{W}} \, 0^{\abs{E(\vig{G}{W})}}} 
= \sumsr{\substack{W \subseteq V \\ W \text{ is independent in } G}}{x^{\abs{W}}} 
= I(G, x). \qedhere
\end{align*}
\end{proof}

\begin{coro} \label{coro:rec_rel_hg_e_2}
Let $G = (V, E)$ be a hypergraph with an edge $e \in E$. The independence polynomial satisfies
\begin{align}
I(G, x) = I(G_{-e}, x) - x^{\abs{e}-1} \cdot I(G_{/e}, x) + x^{\abs{e}-1} \cdot I(G_{\vsdel e}, x).
\end{align}
\end{coro}

Here, we present another combinatorial argument to support this statement.

\begin{proof}
By the independence polynomial of $G_{-e}$, $I(G_{-e}, x)$, all independent sets of $G$ are enumerated. However, there are some independent sets of $G_{-e}$ including all the vertices of $e$, which are not independent in $G$. To counterbalance this, we subtract $x^{\abs{e}-1} \cdot I(G_{/e}, x)$,
where the vertices incident $e$ are contracted to the vertex $w$. The independent sets counted by this term including $w$ correspond to the independent sets of $G_{-e}$ including all the vertices of $e$ and thus compensate the independent sets additionally counted by $I(G_{-e}, x)$. But at the same time, we also subtract the terms corresponding to independent sets of $G_{/e}$ not including $w$. But these sets are enumerated by $I(G_{/e -w}, x)$, which is equivalent to $I(G_{\vsdel e}, x)$. Thus, the subtracted excess terms are compensated by $x^{\abs{e}-1} \cdot I(G_{\vsdel e}, x)$.
\end{proof}

The subdivision of an edge is a well-known graph operation. It has been used by \textcite[pp.\ 222]{merrifield1989} in a recurrence relation for the number of independent sets $\sigma(G) = I(G, 1)$: For a simple graph $G = (V, E)$ with an edge $e$ it is true that
\begin{align}
\sigma(G) = \sigma(G_{\times e}) - \sigma(G_{/e}).
\end{align}

This result can be generalized simultaneously to the independence polynomial and to hypergraphs.

\begin{theo}
Let $G = (V, E)$ be a hypergraph with an edge $e \in E$. The independence polynomial $I(G, x)$ satisfies 
\begin{align}
I(G, x) = I(G_{\esub e}, x) - x^{\abs{e}-1} \cdot I(G_{/e}, x) + (x^{\abs{e}-1} - x) \cdot I(G_{\vsdel e}, x).
\end{align}
\end{theo}

\begin{proof}
The independent sets of $G_{\esub e}$ can be divided into two sets, those that include the newly inserted vertex $d$ and those that do not. The independent sets of the first kind (including $d$) cannot also include any of the vertices of $e$, as those vertices are linked by an edge with $d$. Therefore, $I_{d \in e}(G_{\esub e}) = x \cdot I(G_{\vsdel e})$.
The independent sets of the second kind (not including $d$) are the independent sets of $G_{\esub e - d} = G_{-e}$. Thus, we have
\[ I(G_{\esub e}) = x \cdot I(G_{\vsdel e}) + I(G_{-e}). \]
Substituting $I(G_{-e})$ in Corollary \ref{coro:rec_rel_hg_e_2}, the result follows from the equation above.
\end{proof}
{"config": "arxiv", "file": "1406.2990/new_recurrence_relations.tex"}