Polynomial graph invariants and the KP hierarchy
Sergei Chmutov Maxim Kazarian Sergey Lando

Generating Talking Face Landmarks from Speech
    Sefik Emre Eskimez
Ross K Maddox Chenliang Xu Zhiyao Duan This is a pre-print of an article whose final form will appear in LVA ICA 2018. This work is supported by the University of Rochester Pilot Award Program in AR/VR and the National Science Foundation grant No. 1741471.
    
=======================================================================================================================================================================================================================================================================================




We prove that the generating function for the symmetric chromatic polynomial of all connected graphs
satisfies (after appropriate scaling change of variables) the Kadomtsev–Petviashvili
integrable hierarchy of mathematical physics. Moreover, we describe a large family of
polynomial graph invariants giving the same solution of the KP.
In particular, we introduce the Abel polynomial for graphs and show this for its generating function.
The key point here is a Hopf algebra structure on the space spanned by graphs and the behavior of the invariants on its primitive space.




§ INTRODUCTION

The Kadomtsev–Petviashvili (KP) hierarchy is an infinite system of nonlinear partial differential equations for a function F(p_1,p_2,…) of infinitely many variables, see Sec. <ref> for details. The equations are indexed by partitions
of integers n, n≥4, into two parts none of which is 1.
The first two equations, those corresponding to partitions of 4 and 5, are

    ^̣2F/p̣_2^2 = ^̣2F/p̣_1p̣_3-
          1/2(^̣2F/p̣_1^2)^2 - 1/12^̣4F/p̣_1^4


    ^̣2F/p̣_2p̣_3 = ^̣2F/p̣_1p̣_4-
          ^̣2F/p̣_1^2·^̣2F/p̣_1p̣_2
    			- 1/6^̣4F/p̣_1^3p̣_2

The left hand side of the equations correspond to partitions into two parts none of which is 1,
while the terms on the right hand sides correspond to partitions of the same number n involving 1.
For n=6, there are two equations, which correspond to the partitions 2+4=6 and
3+3=6, and so on.

It is well known now <cit.> that the generating function for simple connected Hurwitz numbers
is a solution to the Kadomtsev–Petviashvili hierarchy.
Simple connected Hurwitz numbers enumerate certain connected embedded graphs, and
similar statements are known to be true for generating
functions enumerating  other kinds of embedded graphs as well.
In the present paper, we derive a similar statement for the generating functions for
Stanley's symmetric chromatic polynomial of graphs,
the Abel polynomials enumerating rooted forests in graphs,
and for a more general family of polynomial graph invariants.
As far as we know, this is the first appearance of KP solutions coming from graph polynomials.


The symmetric chromatic polynomial.
In 1995, Richard Stanley <cit.> introduced the symmetric chromatic polynomial
X_G(x_1,x_2,…) of a finite graph G with the vertex set V(G)
as the sum over all proper colorings κ:V(G)→ that color the endpoints of each edge into distinct colors:

    X_G(x_1,x_2,...) = ∑_κ∏_v∈ V(G) x_κ(v).

Being a symmetric function in the variables x_1,x_2,…,
the function X_G can be expressed through a basis of symmetric functions.

In fact, a polynomial W_G(q_1,q_2,…), equivalent to the expression of X_G(p_1,p_2,...) in terms of the power-sum functions
p_m := ∑_i=1^∞ x_i^m, was introduced in 1994 in <cit.>, motivated by some problems in knot theory.
The equivalence was noted in <cit.>: 
    (-1)^|V(G)|W_G(q_j=-p_j)=X_G(p_1,p_2,...).


Following <cit.>, we call W_G(q_1,q_2,…) the weighted chromatic polynomial.

There are two advantages of using the <cit.> approach as opposed to the <cit.> one.
Firstly, W_G(q_1,q_2,…) satisfies a contraction-deletion relation, which is understood properly
in terms of graphs with weighted vertices. Secondly, W_G(q_1,q_2,…) encodes the graph G as an element of an appropriate Hopf algebra in terms of its primitive elements. We give the precise definitions and review the relevant results in Sec.<ref>.

The main result of this paper is that after an appropriate rescaling of the variables,  the function

    (q_1,q_2,…):=
    ∑_G connectedW_G(q_1,q_2,…)/|(G)|

becomes a solution to the KP hierarchy. Here and below |(G)| denotes the order of the automorphism group of the graph G.
Note that we do not include the empty graph in the set of connected graphs.

The Abel polynomial.
The classical sequence of Abel polynomials is defined as x(x-an)^n-1.
We consider its specialization with the parameter a=-1, A_n(x):=x(x+n)^n-1.
This is a sequence of polynomials of degree n= A_n, n=0,1,2,…,
with leading coefficient 1 and zero free term (for n>0).
It possesses the following remarkable properties:


  * d/dx e^-d/dx (A_n(x)) = nA_n-1(x), see <cit.>;

  * it is of binomial type <cit.>, A_n(x+y)=∑_k=0^nn kA_k(x)A_n-k(y);

  * its coefficient of x^k is equal to the number of rooted spanning forests
 consisting of k trees (each of which has a root) in the complete graph K_n. For instance, the coefficient of x equals n^n-1, the number of rooted spanning trees of K_n, according to the famous Cayley formula.


The last property allows us to define the Abel polynomial of an arbitrary graph
and make it into a polynomial of several variables q_1,q_2,…. Namely, with
each spanning forest of a graph G, we associate a monomial equal to the product of
(i· q_i) over the trees of the forest, where i stands for the number of vertices of the tree, and the multiplication by i corresponds to the different choices of the root of the tree. The Abel polynomial A_G(q_1,q_2,…) of G
 is equal to the sum of these monomials over all (non-rooted) spanning forests of G.

 In particular, for a graph G with n vertices, the coefficient of q_n in A_G is equal to the number of rooted spanning trees of G. For a complete graph K_n, after the substitution
q_i=x for all i, the polynomial becomes the Abel polynomial A_n(x), A_K_n(x,x,…)=A_n(x).
This polynomial is related to the spectrum of the combinatorial Laplace operator via the matrix-forest theorem <cit.>.














An analog of the second property of the Abel polynomial relates it to the Hopf algebra structure on graphs.
We discuss it in detail in Sec.<ref>. As a consequence, we get one more
result: after an appropriate rescaling of the variables,  the function

    (q_1,q_2,…):=∑_G connectedA_G(q_1,q_2,…)/|(G)|

becomes a solution to the KP hierarchy.

The work on this paper started during the second author's visit to the Ohio State University,
to which he expresses his gratitude.
The second and the third authors appreciate the support of RSF grant, project
16-11-10316 dated 11.05.2016.



§ MAIN RESULTS


The weighted chromatic polynomial.

Necessary definitions will be given in Sec. <ref>.
Besides the function (q_1,q_2,…), we introduce the function

    ^∘(q_1,q_2,…):=exp()=∑_GW_G(q_1,q_2,…)/|(G)|

represented by the sum over all (not necessarily connected, possibly empty) simple graphs.

For rescaling the variables we need the sequence <cit.>

    c_1=1;    
    c_n=(-1)^n+1[1+ ∑_k=1^n-1 (-1)^k 2^k(n-k)n-1 k-1 c_k] .

In particular,
c_1=1,   c_2=1,   c_3=5,   c_4=79,   c_5=3377,….


After the substitution q_n=2^n(n-1)/2(n-1)!/c_n· p_n,
the generating function  becomes a solution to the KP hierarchy of partial differential equations and ^∘ becomes a τ-function of the KP hierarchy.


The Abel polynomial.

Similarly, we introduce the function

    ^∘(q_1,q_2,…):=exp()=∑_GA_G(q_1,q_2,…)/|(G)|,

and the constants a_n:=2^(n-1)(n-2)/2n^n-1 for n=1,2,…, so that a_1=1, a_2=2, a_3=18, a_4=512.


After  the substitution q_n=2^n(n-1)/2(n-1)!/a_n· p_n, the generating function  becomes the solution to the KP hierarchy from Theorem <ref>. So ^∘ becomes the τ-function of the KP hierarchy from the same theorem.


Theorems <ref> and <ref> are corollaries of the following more general statement
concerning umbral graph polynomial invariants as defined in Sec. <ref>.
Both the weighted chromatic polynomial and the Abel polynomial are examples of umbral graph invariants.



Let I be an umbral graph polynomial invariant with values in the polynomial ring in infinitely many variables q_1,q_2,….
Define two generating functions by

    ^∘(q_1,q_2,…)   =   ∑_GI_G(q_1,q_2,…)/|(G)|
    (q_1,q_2,…)   =   ∑_G connectedI_G(q_1,q_2,…)/|(G)|

where the first summation is carried over all graphs, while the second one over
all connected graphs and |(G)| denotes the order of the automorphism group
of the graph G.

Then after an appropriate rescaling of the variables q_n=2^n(n-1)/2(n-1)!/i_n· p_n, where i_n, n=1,2,…, are some constants,
the generating function  becomes a solution to the KP hierarchy of partial differential equations.
After the same rescaling of the variables the generating function ^∘ becomes a
τ-function of the KP hierarchy.

The rescaling constants i_n are given by the sum

    i_n=n!∑_G connected[q_n]I_G(q_1,q_2,…)/|(G)|

of the coefficients of q_n.


We would like to stress that, after the rescaling in the theorem, any umbral graph invariant I leads
to one and the same generating function.

In the last formula the summation can well be carried over all graphs rather than only connected ones,
since the coefficient of q_n in the value I_G(q_1,q_2,…)
on any disconnected graph G with n vertices is 0.
Note also that the value of an umbral graph invariant I_G on any graph with n vertices is
a weighted homogeneous polynomial of weight n, with weights of the variable q_i
taken to be i, for i=1,2,….


The previous theorem can be made more precise.









After the rescaling of the variables described in Theorem <ref>, the generating function ^∘
becomes the following linear combination of one-part Schur polynomials:

    (p_1,p_2,…)=
    1+2^0s_1(p_1)+2^1s_2(p_1,p_2)+…+2^n(n-1)/2s_n(p_1,p_2,…,p_n)+….



For the discussion of Schur polynomials, see Sec. <ref> below.




§ THE HOPF ALGEBRA OF GRAPHS AND UMBRAL GRAPH INVARIANTS


In this section we describe the Hopf algebra structure on the space spanned by graphs.
The study of Hopf algebras in combinatorics was initiated in <cit.>. It was then developed in <cit.>.
Later it led to the concept of combinatorial Hopf algebra (see <cit.> and <cit.>) suitable for quasisymmetric functions.
Independently the Hopf algebra of graphs was introduced in <cit.>.

Let  denote the vector space over  spanned by simple graphs. This vector space is graded,

    =_0⊕_1⊕_2⊕…,

where _n denotes the finite dimensional vector space spanned by all graphs with n vertices.
The product of two graphs is just their disjoint union, while the value of the coproduct Δ:→
on a graph G is obtained as the sum of all terms G(V_1) G(V_2) where G(V_1) and G(V_2) are two induced subgraphs of G whose vertex sets V_1 and V_2 constitute
an ordered partition of the vertex set of G, V(G)=V_1⊔ V_2.
Clearly, both the product and the coproduct respect the grading.
These operations make the vector space spanned by graphs into a graded bialgebra.
This bialgebra is commutative, cocommutative, with a unit given by the empty graph.
According to the classical Milnor–Moore theorem it is isomorphic to the algebra of polynomials over its primitive vector space,
which is the space of elements x on which the comultiplication Δ acts as Δ(x)=x1+1 x.
Any such bialgebra can be thought of as a Hopf algebra with the antipode acting by multiplication by -1 on the primitive space and counit taking value 1 on the empty graph and 0 on all other graphs.

In the case of , the reference to the Milnor–Moore theorem can be eliminated by the following observation.
Each homogeneous subspace _n⊂ admits a representation as a direct sum _n=P(_n)⊕ D(_n)
of the subspace P(_n) of primitive elements and the subspace D(_n) of decomposable elements, which is spanned
by products of elements having grading smaller than n.

Now, the projection π:_n→ P(_n) to the primitive space along the space of decomposable
elements is given by

    π(G)=∑_V(G)=_β∈ B V_β(-1)^|B|-1(|B|-1)!∏_β∈ B G(V_β),

where the summation is carried over all unordered partitions B of the set V(G) of vertices of G into disjoint
unions of nonempty subsets, |B| is the number of parts, and
G(V_β) denotes the subgraph of G induced by the subset V_β⊂ V(G) (see <cit.>, <cit.>). Note that the product ∏_β∈ B G(V_β) is represented by the graph obtained from G by removing all edges connecting vertices belonging to different parts of the partition.

W. Schmitt's interpretation <cit.> of the projection to the subspace of primitive elements
as the logarithm of the identity mapping allows one to invert Eq. (<ref>)
and express any graph as a polynomial in the primitive elements of the form π(G):

    G=∑_V(G)=_β∈ B V_β ∏_β∈ Bπ(G(V_β)).



The algebra of polynomials [q_1,q_2,…] is another commutative and cocommutative Hopf algebra.
The multiplicaton acts as the usual multiplication of polynomials and the
comultiplication Δ acts on variables q_n as on primitive elements,
Δ(q_n)=q_n1+1 q_n. It becomes graded if we set the degree of q_n to be n.
Thus it has precisely one-dimensional primitive space spanned by q_n in each degree n.


An umbral graph polynomial invariant is an arbitrary homomorphism F:→[q_1,q_2,…]
of graded Hopf algebras.


The term `umbral' is justified by the interpretation of the classical umbral calculus
as the study of the Hopf algebra of polynomials given in <cit.>.
Below, the adjective `polynomial' will be often omitted since we consider no
other kinds of graph invariants.
Umbral invariants participate in Theorem <ref>.

Equivalently, umbral invariants can be defined as multiplicative invariants taking primitive elements
of  to linear polynomials (the latter are the primitive elements in the
Hopf algebra of polynomials).
The condition of respecting comultiplication by F can be reformulated in terms of the binomial property, saying that for any  graph G,

    F_G(x_1+y_1,x_2+y_2,x_3+y_3,…)=∑_V(G)=V_1⊔ V_2
    F_G(V_1)(x_1,x_2,…)F_G(V_2)(y_1,y_2,…),

where the summation on the right runs over all partitions of the set of vertices V(G)
into an ordered disjoint union of two subsets.
So any umbral graph invariant is uniquely determined by a set of constants b_G, one for each graph G, such that F_π(G)=b_G q_|V(G)|.


The weighted chromatic polynomial.

The weighted chromatic polynomial is defined in terms of one more graded Hopf algebra, introduced in <cit.>, namely,
the Hopf algebra of weighted graphs  (it was denoted  in <cit.>, but in the present paper we reserve
the notation  for the generating function) together with a graded homomorphism →. Also it was proved there that
 is isomorphic to [q_1,q_2,…]. Hence we get an umbral graph invariant which makes Theorem <ref> about the generating function for weighted chromatic polynomials a corollary of the general Theorem <ref>.

The algebra  is the quotient of the space spanned by weighted graphs modulo the
weighted chromatic relation.

 A weighted graph is a graph G without loops and multiple edges given together with
a weight w:V(G)→ that assigns a positive integer to each vertex of the graph.

Ordinary simple graphs can be treated as
weighted graphs with the weights of all vertices equal to 1.

 The weighted chromatic relation is
the set of relations G = G'_e + G”_e, one for each graph G and an edge e in it,
where the graph G'_e is obtained from G by removing the edge e; and G”_e is obtained from G by a contraction of e such that
if a multiple edge arises, it is reduced to a single edge and the weight w(v) of the new vertex v is set up to be equal to the sum of the weights of the two ends of the edge e; weights of the other vertices remaining unchanged.


The quotient space of the space spanned by all weighted graphs modulo these relations inherits
the multiplication (disjoint union) and the comultiplication (splitting the vertex set into two subsets) and therefore becomes a Hopf algebra. This is . It is graded by the total weight of a graph, w(G)=∑_v∈ V(G)w(v), so that

    =_0⊕_1⊕_2⊕…,

where the vector space _n is spanned by all weighted graphs of total weight n modulo weighted chromatic relations.

It was proved in <cit.> that the Hopf algebra  has a one-dimensional primitive space in each grading and thus is isomorphic to [q_1,q_2,…]. Iterating the weighted chromatic relation we can reduce any
graph to a linear combination of (disconnected) graphs without edges. In degree n, the primitive space
P(_n) is spanned by the graph which is a single vertex of weight n. If we send it to
q_n, then the image of an ordinary graph G (considered as a weighted graph with weights of all vertices equal to 1) in  can be represented by a polynomial in the variables q_n. This is exactly the weighted chromatic polynomial W_G(q_1,q_2,…) from the Introduction (p. pW_G).

A closed formula for W_G(q_1,q_2,…) is found in <cit.>,

    W_G(q_1,q_2,…)=∑_E'⊆ E(G) q_v_1… q_v_k (-1)^|E'|-|V(G)|+k(E') ,

where the sum runs over all subsets E' of the edge set E(G), which we may consider as
spanning subgraphs of G, k(E') is the number of connected components of this spanning subgraph,
v_1,…, v_k denoting the numbers of vertices in the connected components.




𝐧=1. There is only one graph with one vertex, G=∙. It is primitive of degree 1 as a weighted graph,
whence W_∙(q_1,q_2,…)=q_1.

𝐧=2. There is only one connected (simple) graph with two vertices,
G=1gr_A22000. The order of its automorphism group is 2. According to the
weighted chromatic relation, it can be represented (as a weighted graph) as
G=1gr_A22000=(∙ ∙) +
[ ∙; 2 ],
where the weight of a vertex is written underneath, weights 1 being omitted.
The first graph is disconnected, whence taken to q_1^2 in [q_1,q_2,…]. The second graph is sent to q_2. Therefore,
W_-3gr_A22000(q_1,q_2,…)=q_1^2+q_2.

𝐧=3. There are two connected simple graphs with three vertices, namely,
0gr_A33500 and -5gr_tr20150. They have automorphism groups of orders 2 and 6, respectively. As weighted graphs, modulo the weighted chromatic relation, they can be reduced as follows:

    [                                                                                                 0gr_A33500                                                                                                          = (0gr_A3-e3500) +
    			[ 1gr_A22000;          2 ] =
    	    (0gr_A3-ee3500) +
    			2([ ∙ ∙;   2 ])+
          [ ∙; 3 ];                                                                                               -5gr_tr20150                                                                                                          = -5gr_tr-e20150+
    			[ 1gr_A22000;          2 ] =
    		(-5gr_tr-eee20150) +
    			3([ ∙ ∙;   2 ])+
          2[ ∙; 3 ] ]

The corresponding weighted chromatic polynomials are therefore

    W_-3gr_A33500(q_1,q_2,…)=q_1^3+2q_1q_2+q_3,     
    W_-12gr_tr2000(q_1,q_2,…)=q_1^3+3q_1q_2+2q_3.




𝐧=4. There are six connected simple graphs with four vertices. We arrange the results in the following table.

    [                                   G              (0,15)  W_G(q_1,q_2,…)                               |(G)|;                        0gr_A4551310   q_1^4+3q_1^2q_2+q_2^2+2q_1q_3+q_4                                   2;                       -9gr_D4351614         q_1^4+3q_1^2q_2+3q_1q_3+q_4                                   6;                     -9gr_D4+e351614  q_1^4+4q_1^2q_2+q_2^2+4q_1q_3+2q_4                                   2;                       -8gr_sq222020 q_1^4+4q_1^2q_2+2q_2^2+4q_1q_3+3q_4                                   8;                     -8gr_sq+d222020 q_1^4+5q_1^2q_2+2q_2^2+6q_1q_3+4q_4                                   4;                       -8gr_K4222020 q_1^4+6q_1^2q_2+3q_2^2+8q_1q_3+6q_4                                  24;                                     ]

Consequently, the generating function

    (q_1,q_2,…)=
    ∑_G connected   non-emptyW_G(q_1,q_2,…)/|(G)|

starts with

    (q_1,q_2,…)   =   1/1!q_1+1/2!(q_1^2+q_2)+1/3!(4q_1^3+9q_1q_2+5q_3)
          +1/4!(38q_1^4+144q_1^2q_2+45q_2^2+140q_1q_3+79q_4)+…,


The beginning of its exponent looks like

    ^∘(q_1,q_2,…)   =   exp()=∑_GW_G(q_1,q_2,…)/|(G)|
       =   1+1/1!q_1+1/2!(2q_1^2+q_2)+1/3!(8q_1^3+12q_1q_2+5q_3)
          +1/4!(64q_1^4+192q_1^2q_2+48q_2^2+160q_1q_3+79q_4)+…


The rescaling of variables in Theorem <ref> gives

    q_1=p_1,   q_2=2p_2,   q_3=2^3·2!/5p_3,   q_4=2^6·3!/79p_4,  …

After this substitution we get the function

    F(p_1,p_2,…)   =   (p_1,2p_2,16/5p_3,384/79p_4,…)
       =   
    p_1+1/2(p_1^2+2p_2)+1/6(4p_1^3+18p_1p_2+16p_3)
          +1/24(38p_1^4+288p_1^2p_2+180p_2^2+448p_1p_3+384p_4)+…,

which coincides with the logarithm of the function  from Theorem <ref>.

One may easily check that ^̣2F/p̣_2^2 = 15 +…,    while

    ^̣2F/p̣_1p̣_3-
          1/2(^̣2F/p̣_1^2)^2 - 1/12^̣4F/p̣_1^4
    =56/3-1/2-19/6+ …=15+ …

giving thus an evidence that we get a solution of the first KP equation.


The Abel polynomial.


 This example is similar to <ref>. We will follow it case by case.

𝐧=1. For G=∙, we have A_∙(q_1,q_2,…)=q_1.

𝐧=2. For G=1gr_A22000, there are two spanning forests, (∙ ∙) and the graph itself 1gr_A22000. Therefore,
A_-3gr_A22000(q_1,q_2,…)=q_1^2+2q_2.

𝐧=3. There are two connected simple graphs with three vertices,
0gr_A33500 and -5gr_tr201512 ,with automorphism groups of order 2 and 6, respectively. For the first one, 0gr_A33500, there are four spanning forests

    (0gr_A3-ee3500),     (0gr_A3-e3500),    
    (0gr_A3-e-op3500),    0gr_A33500

which contribute the following monomials to the Abel polynomial:

    q_1^3,     2q_1q_2,     2q_1q_2,     3q_3.

Thus A_-3gr_A33500(q_1,q_2,…)=q_1^3+4q_1q_2+3q_3.

For the triangle, -5gr_tr2000, there are seven spanning forests

    (-5gr_tr-eee2000),  (-5gr_tr-ee2000),  (-5gr_tr-ee-op2000),  (-5gr_tr-ee-t2000),  -5gr_tr-e2000,  -5gr_tr-e-op2000,  -5gr_tr-e-t2000.

Each of the last three spanning trees contributes 3q_3. The previous three spanning forests contribute
2q_1q_2 each. Hence the Abel polynomial of the triangle is
A_-12gr_tr2000(q_1,q_2,…)=q_1^3+6q_1q_2+9q_3.


𝐧=4. For the six connected simple graphs with four vertices, we collect the results in the following table.

    [                                       G                  (0,15)  A_G(q_1,q_2,…)                                   |(G)|;                            0gr_A4551310     q_1^4+6q_1^2q_2+4q_2^2+6q_1q_3+4q_4                                       2;                           -9gr_D4351614            q_1^4+6q_1^2q_2+9q_1q_3+4q_4                                       6;                         -9gr_D4+e351614   q_1^4+8q_1^2q_2+4q_2^2+15q_1q_3+12q_4                                       2;                           -8gr_sq222020   q_1^4+8q_1^2q_2+8q_2^2+12q_1q_3+16q_4                                       8;                         -8gr_sq+d222020  q_1^4+10q_1^2q_2+8q_2^2+24q_1q_3+32q_4                                       4;                           -8gr_K4222020 q_1^4+12q_1^2q_2+12q_2^2+36q_1q_3+64q_4                                      24;                                         ]

Thus the generating function

    (q_1,q_2,…)=
    ∑_G connected   non-emptyA_G(q_1,q_2,…)/|(G)|

starts with

    (q_1,q_2,…)   =   1/1!q_1+1/2!(q_1^2+2q_2)+1/3!(4q_1^3+18q_1q_2+18q_3)
          +1/4!(38q_1^4+288q_1^2q_2+180q_2^2+504q_1q_3+512q_4)+… .


The rescaling of variables in Theorem <ref> has the form

    q_1=p_1,   q_2=p_2,   q_3=8/9 p_3,   q_4=3/4 p_4,  …

After the substitution we come to the same series

    F(p_1,p_2,…)   =   (p_1,p_2,8/9 p_3,3/4 p_4,…)
       =   
    p_1+1/2(p_1^2+2p_2)+1/6(4p_1^3+18p_1p_2+16p_3)
          +1/24(38p_1^4+288p_1^2p_2+180p_2^2+448p_1p_3+384p_4)+…,

as before.
It is interesting to note that for an individual graph G, the rescalings of the
variables under consideration give different polynomials W_G(p_1,2p_2,16/5p_3,384/79p_4,…) and
A_G(p_1,p_2,8/9 p_3,3/4 p_4,…). For example, for the six graphs with four vertices from our tables, the coefficients of p_4 in W_G will be 384/79, 384/79,
768/79, 1152/79, 1536/79, 2304/79, while in A_G they will be
3, 3, 9, 12, 24, 48. However, after division by |(G)| and summation to the generating functions they become equal:

    1/24·12·384+4·384+12·768+3·1152+6·1536+2304/79 =
    384/24   =    16 
    1/24· (12·3+4·3+12·9+3·12+6·24+48)   =   16 .




The Abel polynomial A:→[q_1,q_2,…] is an umbral graph invariant.


It is clear that the Abel polynomial is homogeneous and multiplicative.
In order to prove that the mapping A:→[q_1,q_2,…] respects comultiplication,
it suffices to show that the Abel polynomial possesses the binomial property, that is, that it satisfies
the relation

    A_G(x_1+y_1,x_2+y_2,
    …)=∑_V(G)=V_1⊔ V_2A_G(V_1)(x_1,x_2,…)A_G(V_2)(y_1,y_2,…),

where the summation on the right runs over all partitions of the set of vertices V(G)
into an ordered disjoint union of two subsets.

The binomial property is satisfied because of the following argument. Consider a spanning forest
in the graph G. The contribution of this spanning forest to the expression on the left is

    ∏_i=1^∞ (i(x_i+y_i))^k_i,

where k_i is the number of trees with i vertices in the forest, k_i=0 for i large enough.
These k_i trees can be distributed between the two subsets V', V” of the partition
of the set of vertices V(G). There are k_iℓ_i ways to choose ℓ_i
trees for the first part thus leaving  k_i-ℓ_i trees for the second part, for ℓ_i=0,1,2,…,k_i.
Hence the binomial property for the Abel polynomial follows from the usual binomial identity

    (x_i+y_i)^k_i=∑k_iℓ_i x_i^ℓ_iy_i^k_i-ℓ_i.



Suppose we have a multiplicative polynomial graph invariant taking values in the ring
[x] of polynomials in a single variable x. Suppose also that the value of this invariant on
any primitive element in the Hopf algebra of graphs is a linear polynomial,
that is, x with some coefficient.
Then such a graph invariant admits a canonical umbralization.
Namely, we can associate to this graph invariant a homomorphism from the Hopf algebra
of graphs to the Hopf algebra [q_1,q_2,…] of polynomials in infinitely many variables,
which is determined uniquely by the requirement that its value on the projection π(G)
of an arbitrary graph G to the subspace of primitive elements is b_Gq_n, where
n=|V(G)| is the number of vertices of G, and b_G is the coefficient of x in the
value of the given invariant on G.

For example, Stanley's symmetrized chromatic polynomial is the umbralization of the ordinary
chromatic polynomial. Similarly, the Abel polynomial we introduce is the umbralization of
the one-variable polynomial graph invariant whose coefficient of x^k, for a given graph G,
is the number of rooted forests in G consistsing of k trees.




§ GENERAL INFORMATION ON THE KADOMTSEV–PETVIASHVILI INTEGRABLE HIERARCHY


In this section, we reproduce necessary information about the  Kadomtsev–Petviashvili
(KP) integrable hierarchy of partial differential equations.
A more detailed explanation, suitable for the first acquaintance, can be found, for example, in <cit.>.



 §.§ τ-functions and solutions to the KP hierarchy

The KP integrable hierarchy of partial differential equations is best described in terms of
its solutions and τ-functions. The latter are the exponents of the former.
In 1983, Sato <cit.> shown that the τ-functions of the KP-hierarchy
are in a natural one-to-one correspondence with semi-infinite planes in
an infinite dimensional vector space of Laurent polynomials.

Let V be the vector space of Laurent polynomials in the variable z.
The semi-infinite Grassmannian G(∞/2,V) (to be more precise,
an open dense cell in this Grassmannian)
consists of decomposable vectors in PΛ^∞/2V,
i.e., of vectors of the form

    β_1(z)∧β_2(z)∧β_3(z)∧…,

where β_i are Laurent series in z, and we have

    β_i(z)=z^-i+c_i1z^-i+1+c_i2z^-i+2+….


The semi-infinite wedge product
Λ^∞/2V of the vector space V is, by definition, the vector space spanned by the vectors

    v_μ=z^m_1∧ z^m_2∧ z^m_3∧…,    
    m_1>m_2>m_3>…,     m_i=μ_i-i,

where μ is a partition, μ=(μ_1,μ_2,μ_3,…),
μ_1≥μ_2≥μ_3≥…,
having all but finitely many parts equal to 0.
In particular, m_i=-i for all i large enough.

The empty partition corresponds to the vacuum vector

    v_∅=z^-1∧ z^-2∧ z^-3∧….

Similarly,

    v_1^1=z^0∧ z^-2∧ z^-3∧…,  
    v_2^1=z^1∧ z^-2∧ z^-3∧…,
    
    
       v_1^2=z^0∧ z^-1∧ z^-3∧…,

and so on.

Numbering of the basic vectors in the semi-infinite wedge product
Λ^∞/2V (the space of fermions) by partitions of
nonnegative integers establishes its natural vector space isomorphism with the space of bosons,
that is, power series in infinitely many variables  p_1,p_2,….
It is called the boson-fermion isomorphism.
This isomorphism takes a basic vector v_μ
to the Schur polynomial s_μ=s_μ(p_1,p_2,…). The latter is a quaihomogeneous polynomial
of degree |μ| in the variables p_i
(by definition, the degree of p_i is i).
Schur polynomials form an additive basis of the vector space of power series in the variables p_i.

The Hirota equations are the Plücker equations of the embedding
of the semi-infinite Grassmannian into the projectivized semi-infinite wedge product
PΛ^∞/2V. Solutions of the Hirota equations (that is,
semi-infinite planes) are called τ-functions of the KP hierarchy.



Let us represent a power series in p_1,p_2,… as a linear combination

    ∑_ν c_ν s_ν(p_1,p_2,…)

of Schur polynomials.
The Hirota equations are quadratic in the coefficients c_ν of these linear combinations.

The form the Hirota equations take for the logarithm of a τ-function
are called the Kadomtsev–Petviashvili hierarchy equations.


In other words, each τ-function of the KP hierarchy can be obtained as the result of the following
procedure:


  * take a semi-infinite plane β_1(z)∧β_2(z)∧… in V;
 
  * using the Laurent expansion of β_i
 represent the corresponding point in the semi-infinite Grassmannian as a linear combination
 of the basic vectors v_κ and multiply by a constant in order to make 1 the coefficient
 of the vacuum-vector v_∅;
 
  * replace each vector v_κ in the resulting linear combination
 with the corresponding Schur polynomial s_κ(p_1,p_2,…);
 this series in p_1,p_2,… is the desired τ-function.


Logarithms of τ-functions are solutions to the KP hierarchy.




 §.§ Schur polynomials and constructions of combinatorial τ-functions


For λ being partitions of a given non negative integer n, the Schur polynomials s_λ
form an additive basis in the vector space of symmetric
polynomials in infinitely many variables x_1,x_2,….
In particular, the one-part Schur polynomial s_n^1=s_n is defined as the complete homogeneous symmetric polynomial, which is the sum of all monomials of homogeneous degree n
in variables x_1,x_2,….

After substituting for p_i the power sum functions

    p_i=x_1^i+x_2^i+…,     i=1,2,…,

the Schur polynomials turn into an additive basis in the vector space of quasi-homogeneous polynomials
in p_1,…,p_n, with the weight of p_i taken to be i, for i=1,2,….

The expression of the one-part Schur polynomial s_n in variables p_1,p_2,… can be found from
the generating function

    ∑_n=0^∞ s_n   =   e^∑_k=1^∞p_k/k
       =   1+p_1+1/2!(p_1^2+p_2)+1/3!(p_1^3+3p_1p_2+2p_3)+… .

For arbitrary partition λ=(λ_1,λ_2,…,λ_l), λ_1≥λ_2≥…≥λ_l,
the Schur polynomial s_λ can be given by
the Jacobi–Trudi formula

    s_λ=([     s_λ_1   s_λ_1+1   s_λ_1+2         … s_λ_1+l-1;   s_λ_2-1     s_λ_2   s_λ_1+1         … s_λ_2+l-2;         …         …         …         …         …; s_λ_l-l+1 s_λ_l-l+2 s_λ_l-l+3         …     s_λ_l ]).


The Schur polynomials constitute a convenient language for describing formal τ-functions
as well as solutions to the KP hierarchy. In particular, the following statement is true.


Any linear combination

    1+c_1s_1+c_2s_2+…

of one-part Schur polynomials with constant coefficients c_n is a τ-function for the KP hierarchy.


Indeed, consider the semi-infinite plane β_1(z)∧ z^-2∧ z^-3∧…, where
β_1(z)=z^-1+c_1 z^0+c_2z^1+c_3z^2+…. Since

    β_1(z)∧ z^-2∧ z^-3∧…=v_∅+c_1v_1^1+c_2v_2^1+…,

this plane is taken, under the boson-fermion correspondence, to the power series in the Proposition.





§ PROOF OF THE MAIN THEOREMS


In this section, we give the proofs of main theorems stated in Sec. <ref>.



 §.§ Proof of Theorem <ref>


Define the universal umbral graph invariant G↦ U_G(q_1,q_2,…) as the multiplicative graph invariant
taking value b_Gq_|V(G)| on the primitive element π(G), which is the projection of a
graph G to the subspace of primitive elements along the subspace of decomposable elements in ,
for all connected graphs G. The invariant U_G takes values in the ring of polynomials in the
variables q_1,q_2,… whose coefficients are polynomials in the variables b_H, for all connected graphs H.
(Of course, for a given graph G, the coefficients
of the polynomial U_G depend only on those indeterminates b_H such that H is an induced subgraph of G).
We call the invariant U universal because the projections π(G) of connected graphs to
the subspace of primitive elements form a basis in the space of primitive elements of ,
whence any umbral graph invariant with values in the ring [q_1,q_2,…] can be induced
from U by choosing appropriate values of b_G, for all connected graphs G.

Introduce two generating functions

    ^∘(q_1,q_2,…)   =   ∑_GU_G(q_1,q_2,…)/|(G)|
    (q_1,q_2,…)   =   ∑_G connectedU_G(q_1,q_2,…)/|(G)|.


As above, we have

    =exp(^∘).


For k=0,1,2,…, denote by

    u_k=∑_G connected |V(G)|=kb_G/|(G)|

the coefficient of the monomial q_k in either  or ^∘.
As well, denote by

    ^∘_k(q_1,q_2,…)   =   ∑_G, |V(G)|=kU_G(q_1,q_2,…)/|(G)|
    _k(q_1,q_2,…)   =   ∑_G connected |V(G)|=kU_G(q_1,q_2,…)/|(G)|

the k th homogeneous parts of the generating functions ^∘ for all graphs
and  for connected graphs, respectively, so that

    ^∘(q_1,q_2,…)   =   1+^∘_1(q_1,q_2,…)+^∘_2(q_1,q_2,…)+…
    (q_1,q_2,…)   =   _1(q_1,q_2,…)+_2(q_1,q_2,…)+….


Introduce notation

    Q_k(q_1,q_2,…)=s_k(u_1/0!2^0q_1,u_2/1!2^1q_2,u_3/2!2^3q_3,…),

that is, Q_k(q_1,q_2,…) is the result of the substitution p_i=u_i/(i-1)! 2^i 2q_i
into the one-part Schur function s_k(p_1,p_2,…,p_k).


For each k=0,1,2,…, we have

    ^∘_k(q_1,q_2,…)=2^k2Q_k(q_1,q_2,…,q_k),

so that

    ^∘(q_1,q_2,…)=Q_0+2^0Q_1+2^1Q_2+2^3Q_3+2^6Q_4+….




This means that after the specified rescaling of the variables,

    q_k=2^k2(k-1)!/u_kp_k,    
    k=1,2,…,

the generating function (q_1,q_2,…) becomes a linear combination of one-part
Schur functions, namely, the function (p_1,p_2,…) from Theorem <ref>, whence, according to Proposition <ref>,
a τ-function for the KP hierarchy.

In order to prove the theorem, we will need the following statement.

Set b_G=0 for disconnected graphs G.

Now, Eq. (<ref>) shows that for any (either connected or disconnected) graph G, we have

    U_G(q_1,q_2,…)=∑_V(G)=⊔_α V_α∏_α b_G(V_α)q_|V_α|,

where the summation is carried over all unordered partitions of the set V(G) of vertices of G
into disjoint unions of subsets, and G(V_α) denotes the subgraph of G induced by the subset
V_α⊂ V(G).

In order to prove Theorem <ref>, let us replace summation over all graphs
with k vertices with summing over all spanning subgraphs of the complete graph K_k
on k vertices. Obviously, for a graph G with k vertices we have

    U_G(q_1,q_2,…)/|(G)|=1/k!∑_E⊂ E(K_k)  K_k|_E=GU_K_k|_E(q_1,q_2,…),

where the summation is carried over all spanning subgraphs K_k|_E of K_k that are isomorphic to G.
Hence,

    ^∘_k(q_1,q_2,…)=1/k!∑_E⊂ E(K_k)U_K_k|_E(q_1,q_2,…),

and we have replaced summation over isomorphism classes of graphs with k vertices with summation over subsets
in the set of edges of the complete graph with k vertices.

Making use of Eq. (<ref>) we obtain

    ^∘_k(q_1,q_2,…)=1/k!∑_V(K_k)=⊔_α V_α2^k2-
    ∑_α|V_α|2∏_α∑_E⊂ E(K_k(V_α))b_K_k(V_α)|_Eq_|V_α|.

Here k2-∑_α|V_α|2 is the number of the edges of K_k connecting
vertices belonging to distinct subsets V_α. Dividing both sides of the last equation by
2^k2 we obtain

    2^-k2^∘_k(q_1,q_2,…)   =   1/k!∑_V(K_k)=⊔_α V_α∏_α2^-
    |V_α|2 |V_α|! u_|V_α|q_|V_α|
       =   1/k!∑_V(K_k)=⊔_α V_α∏_α (|V_α|-1)! p_|V_α|.


The right-hand side of the last equation is independent of the variables
b_G and coincides with the definition of the one-part Schur function s_k=s_k(p_1,p_2,…),
which proves the theorem.



 §.§ Specialization to weighted chromatic polynomial


Theorem <ref> for the weighted chromatic polynomial W_G follows from the main theorem,
since the weighted chromatic polynomial is an example of umbral
graph invariant. For this invariant, the sequence

    1,1,5,79,3377,…

of the values c_1,c_2,c_3,… can be described as follows. The exponent of the exponential generating function
for the alternating sequence

    x-1/2!2^1x^2+5/3!2^3x^3-79/4!2^6x^4+3377/5!2^10x^5-…

is

    1+x+1/2!2^1x^2+1/3!2^3x^3+1/4!2^6x^4+1/5!2^10x^5+….

In other words, we have the recursion

    (-1)^n+1c_n=1-∑_k=1^n-1(-1)^k+12^k(n-k)n-1 k-1c_k.


In order to prove this statement, let us compute explicitly the coefficient C_k of x^k in the exponent

    exp(∑_i=1^∞(-1)^i-1c_i/i!2^i 2x^i).

This exponent is the result of substitution p_i=(-1)^i-1c_i/(i-1)! 2^i 2x^i into exp∑_i=1^∞(p_i/i), therefore, C_kx^k is the value of the Schur function s_k at the same substitution. By Theorem <ref>, we get

    C_k=2^-k 2^∘_k(q_1,q_2,…)|_q_i=(-1)^i-1,

where ^∘_k is the degree k quasihomogeneous summand of ^∘. Now, following the proof of Theorem <ref>, we get

    C_k=2^-k 21/k!∑_E⊂ E(K_k)W_K_k|_E(q_1,q_2,…)|_q_i=(-1)^i-1,

where the summation is carried over all spanning subgraphs K_k|_E of K_k. Up to this point, similar computations 
can be applied to any umbral graph invariant. Now, for the particular case of the invariant W_G, we get by (<ref>),

    C_k   =   2^-k 2/k!∑_E'⊂ E⊂ E(K_k)(-1)^|E'|
    =2^-k 2/k!∑_r=0^k 2k 2 r2^k 2-r(-1)^r.

The first factor inside the last summation is the number of ways to choose a subgraph K_k|_E' with r edges, and the second factor is the number of ways to choose a subgraph K_k|_E containing K_k|_E'. Thus, we obtain finally

    C_k
    =1/k!∑_r=0^k 2k 2 r(-2)^-r=1/k!(1-1/2)^k 2=1/k!2^k 2.

This is what we claimed.
































































 §.§ Specialization to Abel polynomial


We have proved already that the Abel polynomial possesses the binomial property and is
therefore umbral. Hence it suffices to find the sequence {a_n}
defined as

    a_n=∑_G [q_n] A_G/|  G|,

where the summation is carried over all connected graphs with n vertices.
As above, the last summation can be replaced by summation over all spanning subgraphs
of the complete graph K_n. The contribution of any spanning tree into this
sum is 2^(n-1)(n-2)/2· n, since there are n ways to choose a root in the tree,
and each tree enters exactly 2^(n-1)(n-2)/2 spanning (and necessarily connected) subgraphs of K_n
(this is the number of ways to add other edges to the tree to obtain a spanning subgraph
containing this tree). Since, by Caley's theorem, the number of spanning trees in K_n
is n^n-2, we obtain the desired equality

    a_n=2^n-12n^n-1.



99

[A134531]Sloane The On-Line Encyclopedia of Integer Sequences,

	 http://oeis.org/A134531.

[Ab826]Ab826 N. H. Abel, Beweis eines Ausdruckes, von welchem die Binomialformel
   ein einzelner Fall ist,
	Journal für die reine und angewandte Mathematik 1 159–160 (1826).

[ABS06]ABS06 M. Aguiar, N. Bergeron, F. Sottile, Combinatorial Hopf algebras
		and generalized Dehn–Sommerville relations, Compositio Math. 142 1–30 (2006).

[BM16]BM16 S. Billey, P. McNamara, The contributions of Stanley to the fabric
		of symmetric and quasisymmetric functions, in The mathematical legacy of Richard P.
		Stanley, Editors P. Herch, T. Lam, P. Pylyavskyy, V. Reiner  83–104 (2016).

[CS06]CS06 P. Chebotarev, E. Shamis, Matrix-Forest Theorems,
   arXiv:math/0602575 [math.CO].

[CDL94]CDL94 S. Chmutov, S. Duzhin, S. Lando,
Vassiliev knot invariants III. Forest algebra and weighted graphs,
Advances in Soviet Mathematics 21 135–145 (1994).

[JR79]JR79 S. Joni, G.-C. Rota, Coalgebras and bialgebras in combinatorics,
		Stud. Appl. Math. 61(2) 93–139 (1979).

[KL15]KL15 M. Kazarian, S. Lando, Combinatorial solutions to integrable hierarchies, Russ. Math. Surveys, 70(3) 453–482 (2015).

[Kn13]Kn13 O. Knill, Counting rooted forests in a network,
   arXiv:1307.3810 [math.SP].

[L97]L97      S. K. Lando,
 On primitive elements in the bialgebra of chord diagrams, in: Topics in singularity theory, 167–174,
 Amer. Math. Soc. Transl. Ser. 2, 180, Adv. Math. Sci., 34, Amer. Math. Soc., Providence, RI, 1997

[L00]L00      S. K. Lando,
    	On a Hopf algebra in graph theory,
    	J. Comb. Theory, Ser. B, vol. 80 (2000), 104–121.


[NW99]NW99 S. Noble, D. Welsh, A weighted graph polynomial
   from chromatic invariants of knots,
   Annales de l'institut Fourier 49(3) 1057–1087 (1999).

[O00]O00 A. Okounkov,
 Toda equations for Hurwitz numbers, Math. Res. Lett. 7(4) 447–453 (2000).

[RR78]RR78 S. Roman, G.-C. Rota, The Umbral Calculus, Adv. Math. 27, 95–188 (1978)

[RST97]RST G-C. Rota, J. Shen, B. Taylor, All Polynomials of Binomial Type Are
    Represented by Abel Polynomials, Annali della Scuola Normale Superiore di Pisa –
		Classe di Scienze, Série 4 25(3–4): 731–738 (1997).

[S83]S83 M. Sato and Y. Sato, Soliton equations as dynamical systems on infinite
dimensional Grassmann manifolds, in: Nonlinear partial differential equations
in applied science (Tokyo 1982), North-HollandMath. Stud., vol. 81, North-
Holland, Amsterdam 1983, pp. 259–271.

[Sch94]Sch94 W. R. Schmitt, Incidence Hopf algebras,
		Journal of Pure and Applied Algebra 96 299–330 (1994).

[Sch95]Sch95 W. R. Schmitt, Hopf algebra methods in graph theory,
		Journal of Pure and Applied Algebra 101(1) 77–90 (1995).

[St95]St95 R. Stanley, A symmetric function generalization of the chromatic
		polynomial of a graph, Advances in Math. 111(1) 166–194 (1995).





