# On the characterization of chordal graphs using Horn hypergeometric series

Dipnit Biswas  Department of Mathematics, Indian Institute of Science,
Bangalore 560012, India<EMAIL_ADDRESS>,  Irfan Habib  Department of
Mathematics, Indian Institute of Science, Bangalore 560012, India
<EMAIL_ADDRESS>and  R. Venkatesh  Department of Mathematics, Indian
Institute of Science, Bangalore 560012, India  Visiting Faculty, Department of
Mathematics, Indian Institute of Technology Madras, Chennai 600036, India
<EMAIL_ADDRESS>
###### Abstract.

In [6], Radchenko and Villegas characterized the chordal graphs by their
inverse of the independence polynomials being Horn hypergeometric series. In
this paper, we reprove their result using some elementary combinatorial
methods and also generalize it to $PEO-$graphs that could have a countable
number of vertices. Our proof is different from the proof of [6], and it is
based on the connection between the inverse of the multi-variate independence
polynomials and the multi-colored chromatic polynomials of graphs, established
in [1].

I.H. was partially supported by DST/INSPIRE/03/2019/000172.

##  1\. Introduction

We only consider simple graphs in this paper; that means our graphs have no
multiple edges and loops. Let $\mathcal{G}$ be a simple graph with a countable
number of vertices $I$, i.e., we allow $\mathcal{G}$ to have a possibly
countably infinite number of vertices. A subset of $I$ is said to be stable or
independent if the subgraph spanned by that subset has no edges. Let
$\mathbb{F}$ be a field of characteristic $0$ and let
$R=\mathbb{F}[[x_{i}:i\in I]]$ be the ring of formal power series generated by
the commuting variables $x_{i},i\in I$ over $\mathbb{F}$. The multi-variate
independence polynomial of $\mathcal{G}$ over $\mathbb{F}$ is defined to be
the formal power series

$I(\mathcal{G},\mathbf{x})=\sum\limits_{S\in\mathcal{I}(\mathcal{G})}\left(\prod_{i\in
S}x_{i}\right)\in R,$

where $\mathcal{I}(\mathcal{G})$ is the set of all finite independent subsets
of $\mathcal{G}$. Note that $\emptyset$ and
$\\{i\\}\in\mathcal{I}(\mathcal{G})$ for all $i\in I.$ Since the power series
$I(\mathcal{G},\mathbf{x})$ has constant term $1$, we have
$I(\mathcal{G},\mathbf{x})^{-q}\in R.$ Recall that a power series
$F(\mathbf{x})=\sum_{\mathbf{m}\geq 0}c_{\mathbf{m}}\mathbf{x}^{\mathbf{m}}\in
R$ is called Horn hypergeometric if

  1. (1)

$c_{\mathbf{m}}\neq 0$ for all $\mathbf{m}\geq 0$ with
$|\mathrm{supp}(\mathbf{m})|<\infty$ and

  2. (2)

$\frac{c_{\mathbf{m}+\mathbf{e}_{i}}}{c_{\mathbf{m}}}$ is a rational function
of $\\{m_{j}:j\in\mathrm{supp}(\mathbf{m})\\}$ for each
$i\in\mathrm{supp}(\mathbf{m})$, where $\mathbf{e}_{i}:=(\delta_{ji}:j\in I)$
for $i\in I$.

We urge interesting readers to refer to [6] for more details and motivation to
study the Horn hypergeometric series, this will not be discussed in this
paper.

An ordering on the vertices of $\mathcal{G}$ is called a perfect elimination
ordering if it is a well-ordering and for each $k\in I$ the subgraph
$\mathcal{G}_{k}$ of $\mathcal{G}$ induced by the set of vertices from
$\\{i\in I:i<k\\}$ that are adjacent with $k$ is a (finite) complete subgraph.
We call a graph $\mathcal{G}$ a $PEO-$graph if it has an ordering of its
vertices that is a perfect elimination ordering. Now, we state the main result
of this paper.

######  Theorem 1.

Let $\mathcal{G}$ be a simple graph with a countable vertex set $I.$ Then the
following are equivalent.

  1. (1)

The graph $\mathcal{G}$ is a $PEO-$graph.

  2. (2)

The power series $I(\mathcal{G},\mathbf{x})^{-q}$ is Horn hypergeometric for
all $q\not\in-\mathbb{Z}_{+}$.

  3. (3)

The power series $I(\mathcal{G},\mathbf{x})^{-1}$ is Horn hypergeometric.

Our main motivation for this work comes from a result of Radchenko and
Villegas [6], in which they characterize the finite $PEO-$graphs by
$I(\mathcal{G},\mathbf{x})^{-q}$ (for $q\not\in-\mathbb{Z}_{+}$) being Horn
hypergeometric. Note that a finite simple graph is $PEO-$graph if and only if
it is chordal, i.e., it has no induced subgraph isomorphic to the cycle graph
$C_{n}$ with $n\geq 4$. We reprove their result using elementary combinatorial
methods and generalize it to $PEO-$graphs that could have a countably infinite
number of vertices. Our proof is motivated by the connection between the
multi-colored chromatic polynomials of $\mathcal{G}$ and the $q$–th power of
independence polynomial of $\mathcal{G}.$ This result was established in [1,
Propostion 3.7], see also [2, Remark 3.4].

######  Theorem 2.

Let $\mathcal{G}$ be a simple graph with the vertex set $I$. For
$q\in\mathbb{Z}$, we have

$I(\mathcal{G},\mathbf{x})^{q}=\sum\limits_{\mathbf{m}}(-1)^{|\mathbf{m}|}\pi_{\mathcal{G}}^{\mathbf{m}}(q)\mathbf{x}^{\mathbf{m}}$

where the sum runs over all $\mathbf{m}\geq 0$ such that
$|\mathrm{supp}(\mathbf{m})|<\infty.$

On the other hand, we have the multi-colored chromatic polynomials of
$\mathcal{G}$, which is easy to compute for $PEO-$graphs. For $PEO-$graphs, we
have

######  Theorem 3.

Let $\mathcal{G}$ be a $PEO-$graph with the vertex set $I$. For
$\mathbf{m}\geq 0$ with $\mathrm{supp}(\mathbf{m})=\\{i_{1}<\cdots<i_{N}\\}$
(induced from the $PEO-$ ordering of $I$) and for $q\notin-\mathbb{Z}_{+}$, we
have

$\pi_{\mathcal{G}}^{\mathbf{m}}(-q)=\prod\limits_{r=1}^{N}\binom{q-1+a_{r}(\mathbf{m})}{m_{i_{r}}}$

where $a_{r}(\mathbf{m})=m_{i_{r}}+\sum\limits_{\begin{subarray}{c}1\leq
s<r\\\ s\sim i_{r}\end{subarray}}m_{i_{s}}$ for $1\leq r\leq N$ (here $a\sim
b$ means the vertices $a$ and $b$ are connected by an edge in $\mathcal{G}$).

Note that we recover one of the main results of [6] (namely Corollary 3.2)
from Theorem 2 and 3, which was proved in [6] by entirely different
techniques. Since the Theorem 2 holds for any simple graph $\mathcal{G}$, we
can compute the multi-colored chromatic polynomials for any cycle graphs
$C_{n}$, and this is done in Read’s paper [7]. It is important to note that
the authors computed only for $I(C_{n},\mathbf{x})^{-1},n\geq 4$ in [6] using
their techniques, but the general formula for $I(C_{n},\mathbf{x})^{-q}$ for
$n\geq 4$ can be written down easily using our method and a result of Read. We
can use this information to prove our main theorem without any difficulties,
as in [6].

_Acknowledgment. We thank Bernd Sing from the Department of Mathematics,
University of the West Indies, Cave Hill, Barbados for providing a copy of
Ronald C. Read’s article._

##  2\. Characterization of $PEO-$graphs using Horn hypergeometic series

###  2.1. Preliminaries

We denote by $\mathbb{N}$, $\mathbb{Z}_{+}$, and $\mathbb{Z}$ the set of
positive integers, non-negative integers, and integers, respectively. The ring
of formal series in one variable $t$ over a field $\mathbb{F}$ is denoted as
$\mathbb{F}[[t]].$ For a set $S$, denote by $|S|$ the cardinality of $S$ and
by $P(S)$ the power set of $S.$ Denote by $\mathbb{Z}_{+}^{I}$ the set of
$I$–tuple of non-negative integers. For a given $\mathbf{m}:=(m_{i}:i\in
I)\in\mathbb{Z}_{+}^{I}$, the support of $\mathbf{m}$ is denoted by
$\mathrm{supp}(\mathbf{m})=\\{i\in I:m_{i}\neq 0\\}$. Given
$\mathbf{m}=(m_{i}:i\in I)\in\mathbb{Z}_{+}^{I}$ with finite support, i.e.,
$|\mathrm{supp}(\mathbf{m})|<\infty$, we define $|\mathbf{m}|=\sum_{i\in
I}m_{i}.$

### 2.2.

Let $\mathcal{G}$ be a simple graph with a countable vertex set $I$ and an
edge set $E$.

######  Definition 1.

The induced subgraph defined by a subset $S$ of vertices of $\mathcal{G}$ is
denoted as $\mathcal{G}(S)$ and is obtained by deleting from $\mathcal{G}$ the
vertices not in $S$ and all their attached edges.

We have that the induced subgraph $\mathcal{G}(S)$ spanned by a finite subset
$S$ of $I$ is finite, i.e., it has only finitely many edges and vertices. For
$i,j\in I$, the edge between $i$ and $j$ is denoted as $e(i,j).$ Note that
$e(i,j)=e(j,i)$ for all $i,j\in I.$

######  Definition 2.

A subset $S\subseteq I$ is said to be independent or stable if $e(i,j)\notin
E$ for all $i,j\in S.$ Denote $\mathcal{I}(\mathcal{G})$ by the set of all
finite independent subsets of $\mathcal{G}$.

######  Definition 3.

  1. (1)

The multi-variate independence polynomial of $\mathcal{G}$ over $\mathbb{F}$
is defined to be the formal power series

$I(\mathcal{G},\mathbf{x})=\sum\limits_{S\in\mathcal{I}(\mathcal{G})}\left(\prod_{i\in
S}x_{i}\right)\in R.$

  2. (2)

Let $a_{k}$ denote the number of independent subsets of $\mathcal{G}$ of
cardinality $k$. Note that $a_{k}$ need not be generally finite for a given
$k\geq 0$. Suppose $a_{k}$’s are finite for all $k\geq 0$, then we define the
one-variable independence polynomial of $\mathcal{G}$ over $\mathbb{F}$ to be
the formal power series

$I(\mathcal{G},t)=\sum\limits_{S\in\mathcal{I}(\mathcal{G})}t^{|S|}=\sum\limits_{k\geq
0}a_{k}t^{k}\in\mathbb{F}[[t]].$

Note that the one-variable independence polynomial $I(\mathcal{G},t)$ is
obtained from $I(\mathcal{G},\mathbf{x})$ by setting the variables $x_{i}=t$
for all $i\in I$ (whenever it makes sense and in particular $I(\mathcal{G},t)$
is well-defined for a finite graph $\mathcal{G}$).

######  Example 1.

Let us consider the path graph $P_{n}$ for $n\in\mathbb{N}\cup\\{\infty\\}$.
The first few multi-variate independence polynomials of these graphs are
$I(P_{1},x_{1})=1+x_{1},I(P_{2},x_{1},x_{2})=1+x_{1}+x_{2},I(P_{3},x_{1},x_{2},x_{3})=1+x_{1}+x_{2}+x_{3}+x_{1}x_{3}.$
It is easy to see that $I(P_{n},t)$ satisfies the following recursion

$I(P_{n},t)=I(P_{n-1},t)+tI(P_{n-2},t),\,\,n\geq 2$

with $I(P_{2},t)=1+2t$ and $I(P_{1},t)=1+t.$

######  Example 2.

Let $n$ be a positive number such that $n\geq 3.$ The cycle graph $C_{n}$
consists of vertices $\\{1,2,\ldots,n\\}$ with edges joining $i$ with $i+1$
for all $1\leq i<n$ and $n$ with $1.$ Then, the first few multi-variate
independence polynomials of these graphs are:
$I(C_{3},x_{1},x_{2},x_{3})=1+x_{1}+x_{2}+x_{3},I(C_{4},x_{1},x_{2},x_{3},x_{4})=1+x_{1}+x_{2}+x_{3}+x_{4}+x_{1}x_{3}+x_{2}x_{4}.$
Again in this case, we have

$I(C_{n},t)=I(C_{n-1},t)+tI(C_{n-2},t),n\geq 5$

with $I(C_{3},t)=1+3t$ and $I(C_{4},t)=1+4t+2t^{2}.$

###  2.3. Generalized Chromatic Polynomials

Let $\mathbf{m}=(m_{i}:i\in I)$ be a tuple of non-negative integers with
finite support, i.e., $|\mathrm{supp}(\mathbf{m})|<\infty$.

######  Definition 4.

We need the following definitions.

  1. (1)

We call a map $\tau^{\mathbf{m}}_{\mathcal{G}}:I\to
P\left(\\{1,\ldots,q\\}\right)$ a proper vertex multi-coloring of
$\mathcal{G}$ associated to $\mathbf{m}$ using at most $q$-colors if the
following conditions are satisfied:

    1. (a)

for all $i\in I$, we have $|\tau^{\mathbf{m}}_{\mathcal{G}}(i)|=m_{i}$;

    2. (b)

for all $i,j\in I$ such that $e(i,j)\in E$, we have
$\tau^{\mathbf{m}}_{\mathcal{G}}(i)\cap\tau^{\mathbf{m}}_{\mathcal{G}}(j)=\emptyset$.

  2. (2)

We say that two given ${}_{1}\tau^{\mathbf{m}}_{\mathcal{G}}$ and
${}_{2}\tau^{\mathbf{m}}_{\mathcal{G}}$ proper vertex multi-coloring of
$\mathcal{G}$ associated to $\mathbf{m}$ using at most $q$-colors distinct if
${}_{1}\tau^{\mathbf{m}}_{\mathcal{G}}(i)\neq{}_{2}\tau^{\mathbf{m}}_{\mathcal{G}}(i)$
for some $i\in I.$

  3. (3)

For a given $q\in\mathbb{N}$, the number of proper vertex multi-coloring of
$\mathcal{G}$ associated to $\mathbf{m}$ using at most $q$ colors is a
polynomial in $q$, called the generalized chromatic polynomial of
$\mathcal{G}$ associated to $\mathbf{m}$, and it is denoted as
$\pi_{\mathcal{G}}^{\mathbf{m}}(q)$.

### 2.4.

The generalized chromatic polynomial has the following well-known description.
As before, we take $\mathbf{m}=(m_{i}:i\in I)$ as a tuple of non-negative
integers with finite support. We denote by $P_{k}(\mathbf{m},\mathcal{G})$ the
set of all ordered $k$-tuples $(P_{1},\ldots,P_{k})$ such that:

  1. (1)

each $P_{i}$ is a non-empty independent subset of $I$, i.e., no two vertices
have an edge between them; and

  2. (2)

the disjoint union of $P_{1},\ldots,P_{k}$ is equal to the multiset
$\\{i,\ldots,i:i\in\mathrm{supp}(\mathbf{m})\\}$, where $i$ appears exactly
$m_{i}$ number of times for each $i\in\mathrm{supp}(\mathbf{m})$.

The following is well-known; see [1].

######  Proposition 1.

For each $q\in\mathbb{N}$, we have

$\pi_{\mathcal{G}}^{\mathbf{m}}(q)=\sum_{k\geq
0}|P_{k}(\mathbf{m},\mathcal{G})|\binom{q}{k}.$

In particular $\pi_{\mathcal{G}}^{\mathbf{m}}(q)$ is a polynomial in $q.$ ∎

### 2.5.

We have a close relationship between ordinary chromatic polynomials and multi-
colored chromatic polynomials. To see this connection, we need the following
definition of join of $\mathcal{G}$. Let $\mathbf{m}=(m_{i}:i\in
I)\in\mathbb{Z}_{+}^{I}$ with $|\mathrm{supp}(\mathbf{m})|<\infty.$ The graph
$\mathcal{G}(\mathbf{m})-$the join of $\mathcal{G}$ with respect to
$\mathbf{m}$ is defined as follows: the vertices of $\mathcal{G}(\mathbf{m})$
are the disjoint union of $\\{i^{1},\ldots,i^{m_{i}}\\}$,
$i\in\mathrm{supp}(\mathbf{m})$ and the edges of $\mathcal{G}(\mathbf{m})$ are
$e(i^{r},i^{s})$ for all $1\leq r\neq s\leq m_{i}$ and $e(i^{r},j^{s})$ for
$e(i,j)\in E(\mathcal{G})$ and $1\leq r\leq m_{i}$, $1\leq s\leq m_{j}$. That
is, for each vertex $i\in\mathrm{supp}(\mathbf{m})$, we take a clique of size
$m_{i}$ and join the all the vertices of $i$th clique and $j$th clique if
there is an edge between the vertices $i$ and $j$ in the original graph
$\mathcal{G}.$ The following is well-known (see for example [1, Remark 3.3])

######  Proposition 2.

Let $\mathbf{m}=(m_{i}:i\in I)\in\mathbb{Z}_{+}^{I}$ with
$|\mathrm{supp}(\mathbf{m})|<\infty.$ We have

$\pi_{\mathcal{G}}^{\mathbf{m}}(q)=\frac{\pi_{\mathcal{G}(\mathbf{m})}(q)}{\prod_{i}m_{i}!},$

where $\pi_{\mathcal{G}(\mathbf{m})}(q)$ is the ordinary chromatic polynomial
of $\mathcal{G}(\mathbf{m}).$∎

### 2.6.

Using the first counting principles, we can efficiently compute the
generalized chromatic polynomials for many exciting families of graphs. We
have listed some examples below.

$1$$2$$n-1$$n$… (a) Path $P_{n}$

$1$$2$$3$… (b) Path $P_{\infty}$

Figure 1. Path graphs

$n-2$$4$$n-1$$3$$2$$1$$n$… (a) Star graph $S_{n}$

$n-2$$4$$n-1$$3$$2$$1$$n$…… (b) Star graph $S_{\infty}$

Figure 2. Star graphs $n-1$$3$$n$$2$$1$… Figure 3. Cycle $C_{n}$

######  Example 3.

  1. (1)

For the path $P_{n}$, we have

$\pi_{P_{n}}^{\mathbf{m}}(q)=\binom{q}{m_{1}}\binom{q-m_{1}}{m_{2}}\cdots\binom{q-m_{n-1}}{m_{n}}$

  2. (2)

For the infinite path graph $P_{\infty}$, we have

$\pi_{P_{\infty}}^{\mathbf{m}}(q)=\binom{q}{m_{1}}\binom{q-m_{1}}{m_{2}}\cdots\binom{q-m_{N-1}}{m_{N}}$

where $N=|\mathrm{supp}(\mathbf{m})|.$

  3. (3)

For the star graph $S_{n}$, we have

$\pi_{S_{n}}^{\mathbf{m}}(q)=\binom{q}{m_{1}}\binom{q-m_{1}}{m_{2}}\cdots\binom{q-m_{1}}{m_{n}}$

  4. (4)

For the infinite star graph $S_{\infty}$, we have

$\pi_{S_{\infty}}^{\mathbf{m}}(q)=\binom{q}{m_{1}}\binom{q-m_{1}}{m_{2}}\cdots\binom{q-m_{1}}{m_{N}}$

where $N=|\mathrm{supp}(\mathbf{m})|.$

  5. (5)

For the complete graph $K_{n}$, we have

$\pi_{K_{n}}^{\mathbf{m}}(q)=\binom{q}{m_{1}}\binom{q-m_{1}}{m_{2}}\binom{q-m_{1}-m_{2}}{m_{3}}\cdots\binom{q-m_{1}-\cdots-
m_{n-1}}{m_{n}}$

  6. (6)

For the cycle graph $C_{n}$, we have the following formula by Read (see [7])

$\pi_{C_{n}}^{\mathbf{m}}(q)=\left(\prod_{r=1}^{n}(q)_{(m_{r}+m_{r+1})}\right)\times\left(\sum\limits_{k=0}^{n}\Big{(}(-1)^{kn}v_{k}(q)\prod_{i=1}^{n}\frac{(m_{i})^{k}}{(q)^{m_{i}+k}}\Big{)}\right)$

where $m_{n+1}=m_{1}$ and $v_{k}(q)=\binom{q}{k}-\binom{q}{k-1}$ and
$(q)_{k}=q(q-1)(q-2)\cdots(q-k+1)$.

###  2.7. Perfect Elimination Ordering and Chordal graphs

A graph $\mathcal{G}$ is called chordal if it has no induced subgraph
isomorphic to the cycle graph $C_{n}$ with $n\geq 4$. For example, the cycle
graph $C_{n}$ for $n\geq 4$ is not a chordal graph, and all other families
listed earlier $P_{n},P_{\infty}$, $S_{n},S_{\infty}$ are chordal graphs. It
is easy to compute the chromatic polynomials for finite chordal graphs (see,
for example, [4]) as they have perfect elimination ordering. We now recall the
definition of perfect elimination ordering of vertices. First, denote
$N_{\mathcal{G}}(k)$ by the set of all neighbors of $k$ in $\mathcal{G}$
excluding $k$, i.e.,

$N_{\mathcal{G}}(k)=\\{r\in I\backslash\\{k\\}:e(r,k)\in E\\}.$

######  Definition 5 (PEO–Graphs).

  1. (1)

The ordering of the vertices of $\mathcal{G}$ is called a perfect elimination
ordering of $I$ if it is a well-ordering of $I$ and for each $k\in I$ the
subgraph $\mathcal{G}_{k}$ of $\mathcal{G}$ induced by the set of vertices
$N_{\mathcal{G}}(k)\cap\\{r\in I:r<k\\}$ is a finite clique (i.e., a finite
complete subgraph).

  2. (2)

A graph $\mathcal{G}$ is said to be PEO–graph if it has an ordering of its
vertices that is a perfect elimination ordering.

We identify $I$ with $\\{1,\ldots,n\\}$ if its cardinality is $n$. We assume
that this ordering of the vertices is a perfect elimination ordering if
$\mathcal{G}$ is a $PEO-$graph. The following result is well-known for finite
simple graphs [5, Theorem 4.1], see also [3].

######  Proposition 3.

A finite simple graph $\mathcal{G}$ is chordal if and only if it has a perfect
elimination ordering. ∎

### 2.8.

We have explicit formulas for the generalized chromatic polynomials of graphs
that have perfect elimination ordering.

######  Theorem 4.

Let $\mathcal{G}$ be a $PEO-$graph with a countable vertex set $I$. For
$\mathbf{m}\geq 0$ with $\mathrm{supp}(\mathbf{m})=\\{i_{1}<\cdots<i_{N}\\}$,
induced from the $PEO-$ ordering of $I$, and $q\notin-\mathbb{Z}_{+}$, we have

$\pi_{\mathcal{G}}^{\mathbf{m}}(-q)=\prod\limits_{r=1}^{N}\binom{q-1+a_{r}(\mathbf{m})}{m_{i_{r}}}$

where $a_{r}(\mathbf{m})=m_{i_{r}}+\sum\limits_{\begin{subarray}{c}1\leq
s<r\\\ s\in N_{\mathcal{G}}(i_{r})\end{subarray}}m_{i_{s}}$ for $1\leq r\leq
N$.

###### Proof.

Since $N=|\mathrm{supp}(\mathbf{m})|<\infty$, we can restrict our attention to
the induced subgraph $\mathcal{G}(I_{N})$, where
$I_{N}=\mathrm{supp}(\mathbf{m})$ relabelled as $\\{1,\ldots,N\\}$. Note that
the induced ordering is also a perfect elimination ordering for
$\mathcal{G}(I_{N})$. If we start coloring the vertices of
$\mathcal{G}(I_{N})$, the first vertex $1$ has no restrictions, so we can
choose $m_{i_{1}}$ colors from the given $q$ colors and color it. By
induction, we colored the first $k-1$ vertices, $k\geq 2$. For $2\leq k<N$,
the subgraph spanned by $N_{\mathcal{G}(I_{N})}(k)\cap\\{1,\dots,k-1\\}$ is a
clique. So, the only restriction that we have to color the vertex $k$ is that
the colors that are used to color the vertices
$N_{\mathcal{G}(I_{N})}(k)\cap\\{1,\dots,k-1\\}$ can not be used to color the
vertex $k$. With this restriction, we can choose any $m_{i_{r}}$ colors from
the remaining $q-a_{r}(\mathbf{m})+m_{i_{r}}$ colors and color the vertex $r.$
Thus, for any $q\in\mathbb{N}$, we have

$\pi_{\mathcal{G}}^{\mathbf{m}}(q)=\prod\limits_{r=1}^{N}\binom{q-a_{r}(\mathbf{m})+m_{i_{r}}}{m_{i_{r}}}$

Now using ${-q\choose k}=(-1)^{k}{q+k-1\choose k}$, we get the desired result.
∎

### 2.9.

Now we record the following significant result from [1] that connects the
$q$–th power of the multi-variate independence polynomial of $\mathcal{G}$ and
the generalized chromatic polynomials of $\mathcal{G}.$ We give proof of this
fact here for the reader’s convenience. For an indeterminate $q$, we define

${q\choose k}=\frac{q(q-1)\cdots(q-(k-1)))}{k!}.$

Note that we have

${-q\choose k}=(-1)^{k}{q+k-1\choose k}.$

We also set $\mathbf{x}^{\mathbf{m}}=\prod\limits_{i}x_{i}^{m_{i}}$ for
$\mathbf{m}\in\mathbb{Z}^{I}_{+}$ with $|\mathrm{supp}(\mathbf{m}|<\infty$ and
$\mathbf{x}^{S}=\prod\limits_{i\in S}x_{i}$ for $S\subseteq I$ with
$|S|<\infty$. For $f\in R$, we denote $f[\mathbf{x}^{\mathbf{m}}]$ by the
coefficient of $\mathbf{x}^{\mathbf{m}}$ in $f.$

######  Theorem 5.

Let $\mathcal{G}$ be a simple graph with the vertex set $I$. For
$q\in\mathbb{Z}$, we have

$I(\mathcal{G},\mathbf{x})^{q}=\sum\limits_{\mathbf{m}}(-1)^{|\mathbf{m}|}\pi_{\mathcal{G}}^{\mathbf{m}}(q)\mathbf{x}^{\mathbf{m}}$

where the sum runs over all $\mathbf{m}\in\mathbb{Z}_{+}^{I}$ such that
$|\mathrm{supp}(\mathbf{m})|<\infty.$

###### Proof.

We expand $I(\mathcal{G},\mathbf{x})^{q}$ using the binomial expansion. For
any $f\in R$ with constant term zero, we have

$f^{q}=\sum\limits_{k\geq 0}{q\choose k}\,(f-1)^{k}.$

Take $f=I(\mathcal{G},\mathbf{x})$ and note that

$f-1=\sum_{S\in\mathcal{I}(\mathcal{G})\backslash\\{\emptyset\\}}(-1)^{|S|}\mathbf{x}^{S}.$

Let $\mathbf{m}\in\mathbb{Z}_{+}^{I}$ such that
$|\mathrm{supp}(\mathbf{m})|<\infty.$ Then the coefficient
$(f-1)^{k}[\mathbf{x}^{\mathbf{m}}]$ is given by

$\sum\limits_{(S_{1},\dots,S_{k})}(-1)^{\sum_{i=1}^{k}|S_{i}|},$

where the sum ranges over all $k$–tuples $(S_{1},\dots,S_{k})$, with some
possible repetitions, such that

  1. (1)

$S_{i}\in\mathcal{I}(\mathcal{G})\backslash\\{\emptyset\\}$ for each $1\leq
i\leq k$, and

  2. (2)

the disjoint union
$S_{1}\dot{\cup}\cdots\dot{\cup}S_{k}=\dot{\bigcup}_{i\in\mathrm{supp}(\mathbf{m})}\\{i,\ldots,i\\}$,
where $i$ appears exactly $m_{i}$ number of times for each
$i\in\mathrm{supp}(\mathbf{m})$.

It follows that $\big{(}S_{1}.\dots,S_{k})\in
P_{k}\big{(}\mathbf{m},\mathcal{G}\big{)}$ and each element is obtained in
this way. So, the sum ranges over all elements in
$P_{k}\big{(}\mathbf{m},\mathcal{G}).$ Hence we have

$(f-1)^{k}[\mathbf{x}^{\mathbf{m}}]=(-1)^{|\mathbf{m}|}|P_{k}\big{(}\mathbf{m},\mathcal{G}|.$

This implies that

$I(\mathcal{G},\mathbf{x})^{q}[\mathbf{x}^{\mathbf{m}}]=\sum\limits_{k\geq
0}{q\choose
k}\,(f-1)^{k}[\mathbf{x}^{\mathbf{m}}]=(-1)^{|\mathbf{m}|}\sum_{k\geq
0}\binom{q}{k}|P_{k}(\mathbf{m},\mathcal{G})|=(-1)^{|\mathbf{m}|}\pi_{\mathcal{G}}^{\mathbf{m}}(q).$

∎

We easily recover the results [6, Corollary 3.2 & 6.2], and they proved the
following result for chordal graphs by completely different techniques.

######  Corollary 1.

Let $\mathcal{G}$ be a $PEO-$graph with the countable vertex set $I$. For
$\mathbf{m}\geq 0$ with $\mathrm{supp}(\mathbf{m})=\\{i_{1}<\cdots<i_{N}\\}$,
induced from the $PEO$ ordering of $I$, and $q\notin-\mathbb{Z}_{+}$, we have

$I(\mathcal{G},\mathbf{x})^{-q}[\mathbf{x}^{\mathbf{m}}]=\prod\limits_{r=1}^{N}\binom{q-1+a_{r}(\mathbf{m})}{m_{i_{r}}}$

∎

######  Corollary 2.

For $n\geq 4,$ $\mathbf{m}\geq 0$, and $q\notin-\mathbb{Z}_{+}$, we have

$I(C_{n},\mathbf{x})^{-q}[\mathbf{x}^{\mathbf{m}}]=\pi_{C_{n}}^{\mathbf{m}}(-q)=\frac{1}{\prod_{i}m_{i}!}\prod_{r=1}^{n}(-q)_{(m_{r}+m_{r+1})}\left(\sum\limits_{k=0}^{n}\Big{(}(-1)^{kn}v_{k}(-q)\prod_{i=1}^{n}\frac{(m_{i})^{k}}{(-q)^{m_{i}+k}}\Big{)}\right),$

where $m_{n+1}=m_{1}$ and $v_{k}(q)=\binom{q}{k}-\binom{q}{k-1}$ and
$(q)_{k}=q(q-1)\cdots(q-k+1)$. In particular, we have the following formula
for $q=1$ and $\mathbf{a}=(a,\dots,a)$

$I(C_{n},\mathbf{x})^{-1}[\mathbf{x}^{\mathbf{a}}]=(-1)^{na}\left(\sum_{|k|\leq
a}(-1)^{k}\binom{2a}{a+k}^{n}\right).$

∎

###### Proof.

The first formula follows from the Proposition 2 and Read’s formula (see the
Example 3 (6)). It remains to consider the case $q=-1$ and
$\mathbf{a}=(a,\dots,a)$. We have

$\displaystyle(a!)^{n}I(C_{n},\mathbf{x})^{-1}[\mathbf{x}^{\mathbf{a}}]$
$\displaystyle=((-1)_{2a})^{n}\left(\sum_{k=0}^{n}v_{k}(-1)\Big{(}\frac{(a)_{k}}{(-1)_{a+k}}\Big{)}^{n}\right)$
$\displaystyle=((-1)_{2a})^{n}\left(\sum_{k=1}^{n}2\cdot(-1)^{k}\Big{(}\frac{(a)_{k}}{(-1)_{a+k}}\Big{)}^{n}\right)+((-1)_{2a})^{n}\Big{(}\frac{(a)_{0}}{(-1)_{a}}\Big{)}^{n}$
$\displaystyle=((2a)!)^{n}\left(2\left(\sum_{k=1}^{n}(-1)^{na+k}\Big{(}\frac{a!}{(a-k)!(a+k)!}\Big{)}^{n}\right)+(-1)^{na}\Big{(}\frac{1}{a!}\Big{)}^{n}\right)$
$\displaystyle=\frac{(a!)^{n}}{(-1)^{na}}\left(2\sum_{k=1}^{a}(-1)^{k}\binom{2a}{a+k}^{n}+\binom{2a}{a}^{n}\right)$

This is our required formula. ∎

###  2.10. Main Theorem

We are now ready to prove our main theorem.

######  Theorem 6.

Let $\mathcal{G}$ be a simple graph with a countable vertex set $I.$ Then the
following are equivalent.

  1. (1)

The graph $\mathcal{G}$ is a $PEO-$graph.

  2. (2)

The power series $I(\mathcal{G},\mathbf{x})^{-q}$ is Horn hypergeometric for
all $q\not\in-\mathbb{Z}_{+}$.

  3. (3)

The power series $I(\mathcal{G},\mathbf{x})^{-1}$ is Horn hypergeometric.

###### Proof.

We prove $(1)\implies(2)\implies(3)\implies(1)$. Note that $(2)\implies(3)$ is
obvious. The implication $(1)\implies(2)$ follows from Corollary 1 since
$a_{i}(\mathbf{m})\geq m_{i}$ for $i\in I.$ We will now prove
$(3)\implies(1)$. Suppose assume that the power series
$I(\mathcal{G},\mathbf{x})^{-1}$ is Horn hypergeometric, but $\mathcal{G}$ is
not a $PEO-$graph. Then it has an induced subgraph $C_{n}$ for some $\geq 4.$
This would imply that $I(C_{n},\mathbf{x})^{-1}$ is Horn hypergeometric. Hence
we get the sum of diagonal terms

$H_{n}(\mathbb{x})=\sum\limits_{\mathbf{a}=(a,\ldots,a)}c_{\mathbb{a}}\mathbb{x}^{\mathbb{a}}$

is Horn hypergeometric. But we know from Corollary 2 that,

$c_{\mathbb{a}}=(-1)^{na}\left(\sum_{|k|\leq
a}(-1)^{k}\binom{2a}{a+k}^{n}\right),$

now the proof follows the argument as it is in [6, Proposition 6.3]. ∎

######  Remark 1.

Radchenko and Villegas first gave the above characterization in [6] for
(finite) chordal graphs. Their proof uses a method motivated by the
representation theory of quantum affine algebras; they invert the Nahm system
of equations arising from the adjacency matrix of the given graph and, using
that, write down the formula for the coefficients of the inverse of the multi-
variate independence polynomial of the graph. However, they could achieve this
only for finite chordal and cycle graphs. Our method suggests that explicit
formulas can be obtained for other families and will be studied elsewhere.

## References

  * [1] G. Arunkumar, Deniz Kus, and R. Venkatesh.  Root multiplicities for Borcherds algebras and graph coloring.  J. Algebra, 499:538–569, 2018.
  * [2] Olivier Bernardi and Philippe Nadeau.  Combinatorial reciprocity for the chromatic polynomial and the chromatic symmetric function.  Discrete Math., 343(10):111989, 13, 2020.
  * [3] D. R. Fulkerson and O. A. Gross.  Incidence matrices and interval graphs.  Pacific J. Math., 15:835–855, 1965.
  * [4] Fănică Gavril.  Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph.  SIAM J. Comput., 1(2):180–187, 1972.
  * [5] Martin Charles Golumbic.  Algorithmic graph theory and perfect graphs, volume 57 of Annals of Discrete Mathematics.  Elsevier Science B.V., Amsterdam, second edition, 2004.  With a foreword by Claude Berge.
  * [6] Danylo Radchenko and Fernando Rodriguez Villegas.  Independence polynomials and hypergeometric series.  Bull. Lond. Math. Soc., 53(6):1834–1848, 2021.
  * [7] Ronald C. Read.  A large family of chromatic polynomials.  In Proceedings of the Third Caribbean Conference on Combinatorics and Computing (Bridgetown, 1981), pages 23–41. Univ. West Indies, Cave Hill, 1981.