| Russian Mathematical Surveys |
|
|
|
|
|
This article is cited in 3 scientific papers (total in 3 papers) Weight systems and invariants of graphs and embedded graphs M. E. Kazarianab, S. K. Landoab a National Research University "Higher School of Economics" b Skolkovo Institute of Science and Technology
Bibliographic databases:
     IntroductionThe theory of finite-type invariants of knots and links, developed mainly in the 1990s and originating in [61], leads to a necessity to study weight systems. A weight system is a function on chord diagrams that satisfy so-called Vassiliev’s 4-term relations. One usually considers weight systems taking values in a commutative ring. In turn, a chord diagram is a combinatorial object, a graph of special kind. One can think of it as of a 3-regular graph with a distinguished Hamiltonian circuit. Two such graphs are considered as being isomorphic if there is an isomorphism taking the Hamiltonian circuit in the first graph to the one in the second graph, with orientation preserved. A 4-term relation is constructed from a chord diagram and a pair of its vertices that are neighbours along the Hamiltonian circuit; it is a linear relation on the values of a function on four chord diagrams with the same number of vertices. Since the relations are linear, all weight systems can be described as solutions of a system of linear equations. However, both the number of variables (chord diagrams) and the number of equations (4-term relations) grow very rapidly with the number of vertices (for instance, there are more than 600 000 diagrams with $2\cdot 9=18$ vertices, and the number of relations exceeds $5\cdot10^6$). In contrast, the rank of the matrix of equations, that is, the dimension of the space of chord diagrams modulo 4-term relations, grows much slower, and for 9 chords the rank is only 104. There are no universal tools to compute these dimensions, and only rough upper and lower estimates are known. The study of the spaces of all weight systems must be supplemented by constructing specific weight systems and families of such weight systems. These constructions are used, in particular, to obtain lower bounds for the dimensions. The two main sources of constructions are invariants of the intersection graphs of chord diagrams that satisfy the 4-term relations for graphs [43], and metrized Lie algebras [39], [5]. These two constructions are essentially different. Graph invariants can usually be easily computed, but their distinguishing power is rather poor. In contrast, weight systems associated with Lie algebras are powerful, but no approaches to their efficient computation was known until recently. In the present paper we describe both approaches, with a stress on recent results. The problem of computing values of weight systems associated with metrized Lie algebras at chord diagrams is complicated because computations must be done in a highly noncommutative algebra, which is the universal enveloping algebra of the Lie algebra. In the simplest non-trivial case of the Lie algebra $\mathfrak{sl}(2)$ the computations can be simplified by using the Chmutov–Varchenko recurrence relations [20], but they also often prove to be insufficient. Thus, for a long time we did not know the values of the $\mathfrak{sl}(2)$-weight system at chord diagrams any two chords in which intersect one another (that is, whose intersection graph is a complete graph). The final answer was given by Zakorko [65], who proved Lando’s conjecture of 2015 about the generating function of these values. Another recent achievement is the construction of recurrence relations for the values of the $\mathfrak{gl}(N)$-weight system [63]. These relations are based on an extension of the $\mathfrak{gl}(N)$-weight system to arbitrary permutations which was proposed by Kazarian (while chord diagrams are interpreted as permutations of special kind). One of the key problems in the study of graph invariants is that of their extension to embedded graphs. This question is considered in many recent papers. In most of them an invariant of embedded graphs is defined as an invariant of the underlying abstract graph enriched by some information about the embedding. However, we are interested first of all in extending weight systems defined by finite-type knot invariants to weight systems associated with finite-type invariants of links (in contrast to a knot, a link has several connected components). A chord diagram can be interpreted as an embedded graph with a single vertex on an orientable surface, while links correspond to generalized chord diagrams, which are embedded graphs on orientable surfaces the number of whose vertices coincides with the number of link components. In the recent papers [50] and [24] an approach to extending weight systems and graph invariants to arbitrary embedded graphs was proposed, which is based on the study of the structure of the corresponding Hopf algebras. Hopf algebras arise in a natural way in solutions of combinatorial problems of various nature (for instance, see [13]). The space of graphs, as well as the spaces of chord diagrams modulo the $4$-term relations, are endowed with the natural structure of a connected graded Hopf algebra. We do not know such a structure on the space spanned by the embedded graphs. It exists, however, on the space of binary delta-matroids [45], which are combinatorial objects that accumulate important information about graphs or chord diagrams, and also about embedded graphs. However, extending weight systems associated with metrized Lie algebras to the embedded graphs with arbitrarily many vertices remains an open problem. The paper has the following structure. In § 1 we recall the main definitions related to chord diagrams, their intersection graphs, and $4$-term relations for chord diagrams and graphs. We give several key examples of graph invariants that satisfy $4$-term relations and thus define weight systems. In § 2 the Hopf algebra structure on the space of graphs is described, as well as the behaviour of the graph invariants introduced before with respect to this structure. Here we also mention some recent results [18] relating a Hopf algebra structure to an integrability property of graph invariants. Section 3 is devoted to weight systems associated with Lie algebras. In addition to known definitions and results about the $\mathfrak{sl}(2)$-weight system, we describe the recent results due to Zinova and Kazarian about its values at chord diagrams whose intersection graphs are complete bipartite, as well as Lando’s conjecture (Zakorko’s theorem) on its values on chord diagrams with complete intersection graphs. This section also describes the extension of the $\mathfrak{gl}(N)$-weight system to arbitrary permutations and recurrence relations for its computation. Section 4 is devoted to constructing extensions of weight systems from chord diagrams to arbitrary embedded graphs. Here we introduce delta-matroids and describe the Hopf algebra structure on the space of even binary delta-matroids. All necessary definitions and classical results about weight systems can be found in [17] and [46]. We reproduce only those definitions and statements that are necessary to state recent results. Notation
1. $4$-term relationsIn 1990 Vassiliev [61] introduced the notion of a finite-type knot invariant and associated a certain function on the chord diagrams with $n$ chords with any knot invariant of order at most $n$. He showed that any such function satisfies $4$-term relations. In 1993 Kontsevich [39] proved the converse: if a function on the chord diagrams with $n$ chords which takes values in a field of characteristic zero satisfies the $4$-term relations, then it can be obtained by means of Vassiliev’s construction from some knot invariant of order at most $n$. (In Vassiliev’s theorem, as well as in Kontsevich’s theorem, the function is subject to an additional requirement; namely, it must satisfy the so-called one-term relation. However, this requirement evaporates when knots are replaced by framed knots, it does not affect the theory, and we do not mention it below.) Functions on the chord diagrams satisfying the $4$-term relations are called weight systems. The universal finite-type knot invariant constructed by Kontsevich (Kontsevich integral) enables one to recover, in principle, a finite-type invariant from the corresponding weight system. Therefore, studying weight systems plays a key role in understanding the nature of finite-type knot invariants. Note, however, that explicit computation of the Kontsevich integral of a knot is a computationally complicated problem that has not found a satisfactory solution yet. 1.1. Chord diagrams and $4$-term relationsA chord diagram of order $n$ is an oriented circle with $2n$ pairwise distinct points on it, which are split into $n$ pairs considered up to orientation-preserving diffeomorphisms of the circle. We call the circle carrying the diagram its Wilson loop. In the figures below we assume that the circle is oriented counterclockwise. The points forming a pair are connected by a line or arc segment. A $4$-term relation is defined by a chord diagram and a pair of chords with neighbouring endpoints in it. We say that a function $f$ on the chord diagrams satisfies Vassiliev’s $4$-term relations if for any chord diagram $C$ and any pair of chords $a$, $b$ with neighbouring endpoints in $C$ the equality shown in Fig. 1 holds. The equality in Fig. 1 has the following meaning. All four chord diagrams entering it can contain an additional tuple of chords whose endpoints belong to dashed arcs, which is one and the same in all four diagrams. Of the four endpoints of the two distinguished chords $a$ and $b$, both endpoints of $b$, as well as one endpoint of $a$ are fixed, while the second endpoint of $a$ takes successively all four positions close to the endpoints of $b$. The particular position of the second endpoint of $a$ determines the chord diagram in the relation. Note that it does not matter whether the two chords $a$ and $b$ intersect or not: the case of intersecting chords reduces to that of disjoint ones by multiplying the relation in Fig. 1 by $-1$. Below we write the $4$-term relation in the form
$$
\begin{equation}
f(C)-f(C'_{ab})=f(\widetilde{C}_{ab})-f(\widetilde{C}'_{ab})
\end{equation}
\tag{1}
$$
and say that the chord diagram $C'_{ab}$ is obtained from $C$ by the Vassiliev first move on the pair of chords $a$, $b$, the chord diagram $\widetilde{C}_{ab}$ is the result of the Vassiliev second move, and $\widetilde{C}'_{ab}$ is the result of the composition of the two moves; note that, when applied to the same pair of chords, the first and second move commute one with the other and the order in which they are performed is irrelevant. The definition of the $4$-term relation uses subtraction, and we are planning to multiply chord diagrams in what follows. That is why we will usually consider weight systems with values in a commutative ring, making the ring explicit in particular examples. 1.2. Intersection graphsInvariants of intersection graphs of chord diagrams serve as one of the main sources of weight systems, The intersection graph $g(C)$ of a chord diagram $C$ is the simple graph the set of whose vertices is in a one-to-one correspondence with the set of chords of $C$, and two vertices are connected by an edge if and only if the corresponding chords intersect. (Two chords in a chord diagram intersect if their endpoints on the circle follow in alternating order; the point of intersection of chords in the figures is not a vertex of the chord diagram.) Fig. 2 shows an example of a $4$-term relation for a chord diagram and its intersection graph. Only the chord diagrams and their intersection graphs are shown; no reference to the value of the function is made. Any graph with at most five vertices is the intersection graph of some chord diagram. There are two graphs with six vertices that are not intersection graphs; they are shown in Fig. 3. The fraction of intersection graphs among the simple graphs with $n$ vertices grows rapidly with $n$. A variety of complete sets of obstacles for a graph to be an intersection graph is known. On the other hand some intersection graphs can be realized as the intersection graphs of several, not pairwise isomorphic chord diagrams. For example, consider the chain on $n$ vertices (see Fig. 4). For $n=5$ there are three distinct chord diagrams with this intersection graph (see Fig. 5). 1.3. $4$-term relations for graphs$4$-term relations for graphs were introduced in [43]. We say that a graph invariant $f$ satisfies the $4$-term relation if for any graph $G$ and any pair $a$, $b$ of its vertices we have
$$
\begin{equation}
f(G)-f(G'_{ab})=f(\widetilde{G}_{ab})-f(\widetilde{G}'_{ab});
\end{equation}
\tag{2}
$$
here the graph $G'_{ab}$ is obtained from $G$ by switching adjacency between the vertices $a$ and $b$, the graph $\widetilde{G}_{ab}$ is obtained from $G$ by switching the adjacency of $a$ to all vertices in $G$ adjacent to $b$, and the graph $\widetilde{G}'_{ab}$ is the result of the composition of these two operations. Remark. The transformation $G\mapsto G'_{ab}$ is symmetric with respect to $a$ and $b$: $G'_{ab}= G'_{ba}$. On the other hand the second Vassiliev move for graphs $G\mapsto \widetilde{G}_{ab}$ is not symmetric, and the graph $\widetilde{G}_{ba}$ is not isomorphic to $\widetilde{G}_{ab}$ as a rule. Graph invariants satisfying $4$-term relations are called $4$-invariants. Similarly to the case of weight systems, we assume that $4$-invariants take values in a commutative ring. A direct study of the way the intersection graph of a chord diagram changes under Vassiliev moves proves the following statement. Theorem 1.1 (see [43]). If $f$ is a $4$-invariant of graphs, then $f\circ g$ is a weight system on the chord diagrams. An example of a $4$-term relation is given in Fig. 2. Note, however, that even if a graph $G$ is an intersection graph, this does not mean that the same is true for the other three graphs in a $4$-term relation. Thus, any $4$-invariant determines a weight system, and therefore, by Kontsevich’s theorem, a knot invariant. Below we give several examples of $4$-invariants. The following question posed by Lando has remained open for the last two decades: Is it true that, modulo the $4$-term relations for graphs, any graph is a linear combination of intersection graphs? Computer computations (Dynnikov, private communication) show that this is true for all graphs with at most eight vertices. 1.3.1. The chromatic polynomialOne of the historically first examples of 4- invariants of simple graphs is chromatic polynomials. Let $G$ be a graph, and let $V(G)$ be its vertex set. The chromatic polynomial $\chi_G(c)$ of $G$ is the number of regular colourings of $V(G)$ with $c$ colours, that is, the number of mappings $V(G)\to\{1,2,\dots,c\}$ such that at any two adjacent (connected by an edge) vertices the values of the mapping are different. It is well known that the chromatic polynomial satisfies the contraction–deletion relation: for any graph $G$ and any edge $e$ in it; here the graph $G'_e$ is obtained from $G$ by deleting the edge $e$, and $G''_e$ is the result of contracting this edge. When an edge is contracted, it is deleted, its two endpoints become a single new vertex of the graph, and any multiple edge that can appear after that is replaced by a single edge.The contraction–deletion relation can be proved easily: it corresponds to splitting the set of regular colourings of the vertices of the graph $G'_e$ with $c$ colours into two disjoint subsets, namely, of those colourings where the endpoints of $e$ are coloured differently (these are exactly the regular colourings of the vertices of $G$) and of those where these endpoints are coloured the same colour (the latter correspond one-to-one to regular colourings of the vertices of $G''_e$). Since the chromatic polynomial of a discrete (edge-free) graph on $n$ vertices is $c^n$, the contraction-deletion relation proves that, for a graph $G$ on $n$ vertices, $\chi_G(c)$ is indeed a polynomial of degree $n$ with leading coefficient $1$. Theorem 1.2 (see [16]). Chromatic polynomial is a $4$-invariant. Indeed, applying the contraction–deletion relation to a graph $G$ and an edge $e$ of $G$ with endpoints $a$ and $b$, we conclude that In turn,
$$
\begin{equation*}
\chi_{\widetilde{G}_{ab}}(c)-\chi_{\widetilde{G}'_{ab}}(c)= -\chi_{\widetilde{G}''_{ab}}(c).
\end{equation*}
\notag
$$
Verifying that the natural identification of the vertex sets of the graphs $G''_{ab}$ and $\widetilde{G}''_{ab}$ establishes their isomorphism completes the proof. 1.3.2. The weighted chromatic polynomial (Stanley’s symmetrized chromatic polynomial)The chromatic polynomial is an important graph invariant; however, it is not powerful in distinguishing. For example, the chromatic polynomial of any tree on $n$ vertices is $c(c-1)^{n-1}$, while the number of pairwise nonisomorphic trees on $n$ vertices grows very rapidly with $n$. The weighted chromatic polynomial, more widely known under the name of Stanley’s symmetrized chromatic polynomial, is a much finer graph invariant. In order to define the weighted chromatic polynomial we need the notion of a weighted graph. Definition 1.3. A weighted graph is a simple graph $G$ with a positive integer, a weight, assigned to each of its vertices. The weight of a weighted graph is the sum of the weights of its vertices. Definition 1.4 (see [16]). The weighted chromatic polynomial is the weighted graph invariant $G\mapsto W_G(q_1,q_2,\dots)$ taking values in the ring of polynomials in infinitely many variables $q_1,q_2,\dots$ and possessing the following properties: Theorem 1.5 (see [16]). There is a unique weighted graph invariant possessing the above properties. The weighted chromatic polynomial $W_G$ of a weighted graph $G$ of weight $n$ is a quasihomogeneous polynomial of degree $n$ in the variables $q_1,q_2,\dots$, where the weight of the variable $q_k$ is set equal to $k$, $k=1,2,\dots$ . A simple graph can be considered as a weighted graph such that the weight of each of its vertices is equal to $1$. Thus, any weighted graphs invariant defines a simple graphs invariant. Indeed, similarly to the proof for chromatic polynomial we observe that the natural identification of the vertex sets of the graphs $G''_{ab}$ and $\widetilde{G}''_{ab}$ establishes an isomorphism of these graphs as weighted graphs. In 1995 Stanley introduced the notion of a symmetrized chromatic polynomial. Definition 1.7 (see [60]). Let $G$ be a simple graph. A colouring of the set of vertices $V(G)$ of $G$ with an infinite set of colours is a mapping With each colouring $\beta$ one associates the monomial $x_\beta$ of degree $n=|V(G)|$ in the variables $x_1,x_2,\dots$ that is equal to the product of the values of $\beta$ at all the vertices of $G$. The symmetrized chromatic polynomial $S_G(x_1,x_2,\dots)$ of $G$ is the infinite sum where the colouring $\beta$ is said to be regular if it takes any two adjacent vertices to different elements of $X$. For obvious reasons the symmetrized chromatic polynomial is a symmetric function in the variables $X$. Stanley’s conjecture asserts that the symmetrized chromatic polynomial distinguishes between any two trees. It is confirmed for trees with up to $29$ vertices (see [32]), thus indicating that the symmetrized chromatic polynomial is a much finer graph invariant than the ordinary chromatic polynomial $\chi_G$. Being symmetric in the variables $X$, any symmetrized chromatic polynomial can be expressed as a polynomial in any basis in the space of symmetric polynomials. In particular, one can choose the power sums for this basis. Expressed in this form, the symmetrized chromatic polynomial $S_G$ becomes a finite quasihomogeneous polynomial of degree $n=|V(G)|$ in the variables $p_1,p_2,\dots$, provided that we set the degree of the variable $p_k$ to be equal to $k$, $k=1,2,\dots$. The following statement establishes a relationship between Stanley’s symemtrized chromatic polynomial and the weighted chromatic polynomial.Theorem 1.8 (see [52]). Expressed in terms of power sums, Stanley’s symmetrized chromatic polynomial becomes the weighted chromatic polynomial after the substitution $p_k=(-1)^{n-k}q_k$, $k=1,2,\dots$; here $n=|V(G)|$. As a consequence, Stanley’s symmetrized chromatic polynomial is a $4$-invariant of graphs. In turn, the ordinary chromatic polynomial is a specialization of Stanley’s symmetrized one: the latter transforms into the former after the substitution $p_i=c$, for $i=1,2,3,\dots$ . 1.3.3. The interlace polynomialOriginally, the interlace polynomial was defined as a function on the oriented graphs having two in- and two out-edges at each vertex. The definition appeared first in the paper [4], devoted to DNA sequencing. Subsequently, the definition was extended to arbitrary simple graphs. We start with defining the pivot operation. Let $G$ be a simple graph. For any pair $a$, $b$ of adjacent vertices of $G$, all other vertices of it are split into four classes, namely:
The pivot $G^{ab}$ of $G$ along the edge $ab$ is the graph obtained by switching adjacency between two arbitrary vertices in the first three classes if and only if they belong to different classes. The interlace polynomial $L_G(x)$ is defined by the following recurrence relations:
It was proved in [4] that the interlace polynomial is well defined: the result of its calculation is independent of the order in which pivots are applied. The definition immediately implies that $L_G(x)$ is indeed a polynomial in $x$ of degree $n=|V(G)|$. This theorem was proved in [51] and, in a different way, in [38]. 1.3.4. The transition polynomialFor $4$-regular graphs endowed with an oriented Eulerian circuit the transition polynomial was introduced in [34]. By contracting each chord of a chord diagram $C$ we transform it into a $4$-regular graph so that the Wilson loop of the chord diagram becomes an oriented Eulerian circuit. The transition polynomial of this graph defines, therefore, a map from the set of chord diagrams to the space of polynomials. Conversely, with a $4$-regular graph with a distinguished oriented Eulerian circuit we associate a chord diagram; the number of chords in it coincides with the number of vertices in the graph. The Eulerian circuit turns into the Wilson loop of the chord diagram, and the vertices of the graph become the chords. Here we define the transition polynomial for a chord diagram. To define it we need the notion of a transition. Let $C$ be a chord diagram. Each chord in $C$ can be replaced by a ribbon in one of the following three ways; we encode these ways by the Greek letters $\chi$, $\phi$, or $\psi$:
Choose a weight function $w\colon\{\phi,\chi,\psi\}\to K$ that associates an element of a commutative ring $K$ with each of the three Greek letters. The weighted transition polynomial of a chord diagram $C$ is the polynomial
$$
\begin{equation*}
T_C(x)=\sum_{s\colon V(C)\to\{\phi,\chi,\psi\}}\, \prod_{v\in V(C)} w(s(v))x^{c(s)-1},
\end{equation*}
\notag
$$
where summation is carried over all the states of $C$, and $c(s)$ denotes the number of connected components of the boundary of the surface obtained from $C$ by attaching a disc to the Wilson loop with chords replaced by the corresponding ribbons. Theorem 1.10 (see [25]). By setting $w(\chi)=t$, $w(\phi)=-t$, and $w(\psi)=s$ for the weight function the transition polynomial becomes a weight system taking values in the ring of polynomials $\mathbb{C}[t,s,x]$. 1.3.5. The skew characteristic polynomialLet $G$ be a simple graph with $n=|V(G)|$ vertices. We number the vertices by integers from 1 to $n$ in an arbitrary way and associate the adjacency matrix of $G$ with this numbering. The adjacency matrix $A(G)$ is an $n\times n $ matrix over the two-element field $\mathbb{F}_2$ that contains 1 in the cell $(i,j)$ if the vertices with indices $i$ and $j$ are connected by an edge, and contains 0 otherwise. In particular, the matrix $A(G)$ is symmetric and has zeros on the diagonal. The isomorphism class of $G$ is recovered uniquely from its adjacency matrix. Various characteristics of the adjacency matrix, for example, its characteristic polynomial, play a key role in the investigation of graphs. Definition 1.11. A graph $G$ is non-degenerate (degenerate) if its adjacency matrix $A(G)$ is non-singular (singular, respectively) over $\mathbb{F}_2$. The non-degeneracy of a graph is the graph invariant taking values in $\mathbb{C}$ that is equal to 1 for a non- degenerate graph and to $0$ for a degenerate one. The adjacency matrix of any graph with an odd number of vertices is degenerate since it is antisymmetric over the field $\mathbb{F}_2$, so the non-degeneracy of any graph with an odd number of vertices is 0. A graph with an even number of vertices can be either non-degenerate or degenerate. We denote the non-degeneracy of a graph $G$ by $\nu(G)$. Indeed, let $G$ be a graph, and let $a$ and $b$ be vertices on it. Choose a numbering of the vertices of $G$ so that $a$ is assigned 1 and $b$ is assigned 2. Then the adjacency matrix $A(\widetilde{G}_{ab})$ of $\widetilde{G}_{ab}$ is where $I_{12}$ is the square $|V(G)|\times |V(G)|$ matrix over $\mathbb{F}_2$ that coincides with the identity matrix everywhere with the exception of the cell $(1,2)$, which contains $1$, and $I_{12}^\top$ is its transpose matrix. The assertion of the lemma follows from the fact that both matrices $I_{12}$ and $I_{12}^\top$ are non-singular.Definition 1.13 (see [24]). The skew characteristic polynomial of a graph $G$ is the polynomial where summation is carried over all the subsets $U$ of the vertex set $V(G)$ of the graph, and $G\big|_U$ denotes the subgraph of $G$ induced by the subset $U$ of its vertices. The skew characteristic polynomial of a graph with an even number of vertices is an even function of its argument, and if the number of vertices is odd, then the skew characteristic polynomial is also odd. Lemma 1.12 implies the following. Let us explain why the skew characteristic polynomial carries this name. Let $C$ be a chord diagram, and let $g(C)$ be its intersection graph. We choose the following orientation of this graph. Taking a point $\alpha$ on the Wilson loop that is not an endpoint of a chord, cut the circle at this point and develop it into a horizontal line whose orientation inherits that of the circle. Under this transformation chords become half-circles (arcs), and two vertices in $g(C)$ are connected by an edge if and only if the corresponding arcs intersect. Orient each edge in $g(C)$ away from the vertex corresponding to the arc whose left-hand endpoint precedes the left-hand endpoint of the arc corresponding to the second vertex of the edge. If we number the vertices of the graph in the order of the left-hand endpoints of the corresponding arcs, then each edge is oriented away from the vertex with a smaller number towards the vertex with a greater one. The orientation of the intersection graph obtained in this way depends on the cut point $\alpha$ of the circle; we denote the corresponding directed graph by $\vec{g}_\alpha(C)$. The intersection matrix of a directed graph with $n$ numbered vertices is the integer-valued $ n\times n $ matrix whose $(i,j)$th entry is $0$ if the vertices $i$ and $j$ are not connected by an edge, it is $1$ if the arrow goes from $i$ to $j$, and it is $-1$ if there is an arrow from $j$ to $i$. The adjacency matrix of a directed graph is skew symmetric. Proposition 1.15 (see [24]). The characteristic polynomial of the adjacency matrix of a directed graph $\vec{g}_\alpha(C)$ is independent of the cut point $\alpha$. Theorem 1.16 (see [24]). The characteristic polynomial of the adjacency matrix of the directed intersection graph of a chord diagram $C$ coincides with the skew characteristic polynomial $Q_{g(C)}$ of its intersection graph. Thus, the skew characteristic polynomial of an intersection graph coincides with the characteristic polynomial of the oriented graph obtained by introducing an orientation on its edges that belongs to a certain class of admissible orientations. This justifies the choice of the name for the invariant. There may be no such orientation for a graph that is not an intersection graph. 2. Hopf algebra of graphsMany natural graph invariants are multiplicative. The value of such an invariant at a graph $G_1\sqcup G_2$, which is a disjoint union of the two graphs $G_1$ and $G_2$, is the product of its values at $G_1$ and $G_2$. In particular, all invariants defined in § 1.3 are multiplicative. Multiplicativity means that in order to calculate the value of the invariant at a graph it suffices to know its values at the connected components of the graph. In this section we show that the behaviour of invariants with respect to comultiplication of graphs is of no less importance. Multiplication and comultiplication of graphs together form a Hopf algebra structure on the vector space spanned by simple graphs. For the first time the importance of this structure was pointed out in [35]. This Hopf algebra is an algebra of polynomials in its primitive elements. Primitive elements are linear combinations of graphs, and for many graph invariants their values at primitive elements are much simpler than their values at graphs themselves. For instance, the value of a chromatic polynomial at any primitive element is a linear polynomial, while the chromatic polynomial of a simple graph on $n$ vertices is a polynomial of degree $n$. Following [18], we call polynomial graph invariants whose values at primitive elements are linear polynomials umbral invariants. This term is related to the fact that umbral calculus in combinatorics considers homomorphisms of the Hopf algebra of graphs to other Hopf algebras [55]. The integrability properties of umbral invariants are discussed in § 2.4. 2.1. Multiplication and comultiplication of graphsDenote by $\mathcal{G}_n$ the vector space over $\mathbb{C}$ that is freely spanned by all graphs on $n$ vertices, $n=0,1,2,\dots$, and let
$$
\begin{equation*}
\mathcal{G}=\mathcal{G}_0\oplus\mathcal{G}_1\oplus\mathcal{G}_2\oplus\cdots
\end{equation*}
\notag
$$
be the direct sum of these vector spaces. Note that the vector space $\mathcal{G}_0$ is one-dimensional; it is spanned by the empty graph. We introduce a commutative multiplication $m\colon\mathcal{G}\otimes\mathcal{G}\to\mathcal{G}$ on $\mathcal{G}$ by defining its values at the generators, and by extending this to linear combinations of graphs by linearity. Obviously, this multiplication is commutative and respects the grading:
$$
\begin{equation*}
m\colon\mathcal{G}_k\otimes \mathcal{G}_n\to \mathcal{G}_{k+n}
\end{equation*}
\notag
$$
for all $k$ and $n$. The empty graph $e\in\mathcal{G}_0$ is the unity of this multiplication. The action of comultiplication $\mu\colon\mathcal{G}\to\mathcal{G}\otimes\mathcal{G}$ on a graph $G$ has the form 1
$$
\begin{equation*}
\mu\colon G\mapsto \sum_{V(G)=U\sqcup W}G\big|_U\otimes G\big|_W,
\end{equation*}
\notag
$$
where summation on the right-hand side is carried over all the ordered partitions of the vertex set $V(G)$ of $G$ into two disjoint subsets, and $G\big|_U$ denotes the subgraph of $G$ induced by a subset $U$ of its vertices. Comultiplication is extended to linear combinations of graphs by linearity. With respect to this comultiplication the vector space $\mathcal{G}$ is a coalgebra. The linear map $\epsilon\colon\mathbb{C}\to\mathcal{G}_0$ taking $1$ to $e$ is the counit with respect to $\mu$. 2.2. Primitive elements, the Milnor–Moore theorem, and the Hopf algebra structureAn element $p$ of a coalgebra with comultiplication $\mu$ is primitive if In the coalgebra $\mathcal{G}$ the graph $K_1\in\mathcal{G}_1$ consisting of a single vertex is primitive. No other graph is primitive; however, some linear combinations of graphs in which more than one graph participate are primitive. For instance, it is easy to check that the difference $K_2-K_1^2$ is primitive. (Here and below we denote by $K_n$ the complete graph on $n$ vertices.)Any polynomial algebra $\mathbb{C}[y_1,y_2,\dots]$ in finitely or infinitely many variables is endowed with a natural coalgebra structure if we declare the variables $y_i$ primitive: $\mu(y_1)=1\otimes y_i+y_i\otimes1$. Comultiplication is extended to monomials and their linear combinations (polynomials) as a ring homomorphism, that is,
$$
\begin{equation*}
\mu\biggl(\,\prod_{k=1}^n y_{i_k}\biggr)= \prod_{k=1}^n(1\otimes y_{i_k}+y_{i_k}\otimes1).
\end{equation*}
\notag
$$
Definition 2.1. A tuple $(H,m,\mu,e,\epsilon,S)$, where is called a Hopf algebra if In a Hopf algebra the map $S$ is called the antipode. The algebra of polynomials $\mathbb{C}[y_1,y_2,\dots]$ becomes a Hopf algebra if we define the antipode $S$ as the map $S\colon y_i\mapsto-y_i$ for $i=1,2,\dots$ and extend it to the whole of $H$ as an algebra homomorphism. A Hopf algebra $H$ can be graded. In this case it is represented as a direct sum of finite-dimensional subspaces and both multiplication and comultiplication must respect the grading, that is,
$$
\begin{equation*}
m\colon H_i\otimes H_j\to H_{i+j}\quad\text{and}\quad \mu\colon H_n\to\bigoplus_{i+j=n} H_i\otimes H_j.
\end{equation*}
\notag
$$
A graded Hopf algebra is said to be connected if the vector space $H_0$ is one-dimensional. If a grading (weight) $w(y_i)\in \mathbb{N}$ of each variable $y_i$ in a polynomial Hopf algebra is fixed so that for each $n=1,2,3,\dots$ there are finitely many variables of weight at most $n$, then the polynomial Hopf algebra $\mathbb{C}[y_1,y_2,\dots]$ becomes graded. Its subspace of grading $n$ is spanned by the monomials of weight $n$, where the weight of a monomial is the sum of the weights of the variables occurring in it. The following Milnor–Moore theorem describes the structure of graded commutative cocommutative Hopf algebras. Theorem 2.2 (see [47]). Any connected graded commutative cocommutative Hopf algebra is a polynomial Hopf algebra in its primitive elements. This theorem means that if we choose a basis in each subspace of primitive elements $P(H_n)\subset H_n\subset H$ of grading $n$, then $H$ is a graded polynomial Hopf algebra in the elements of these bases, provided that we set the weight of each element to be equal to its grading. Remark. The Milnor–Moore theorem remains true if one assumes that the Hopf algebra is cococmmutative only. However, we are going to use it only in the commutative case, where the above statement is sufficient. There is a primitive element naturally associated with any polynomial in the Hopf algebra of polynomials, namely, its linear part. This map from the vector space of polynomials to the vector space of their linear parts is a projection, that is, its square coincides with itself. The Milnor–Moore theorem, Theorem 2.2, implies that the projection onto the subspace of primitive elements is naturally defined in any connected graded commutative cocommutative Hopf algebra $H$. We denote this projection by $\pi$, Each homogeneous subspace $H_n\subset H$ can be represented as the direct sum $H_n=P(H_n)\oplus D(H_n)$ of the subspace of primitive elements $P(H_n)$ and the kernel $D(H_n)$ of the projection $\pi$. The kernel $D(H_n)$ consists of the decomposable elements, that is, of the polynomials in the primitive elements with grading less than $n$. The projection $\pi$ can be described by the following formula. Let $\phi,\psi\colon H\to H$ be linear maps. Define the convolution product $\phi *\psi\colon H\to H$ as the linear map for all $a\in H$. The convolution product in graded Hopf algebras can be used to define other operations on linear maps that can be expressed in terms of power series. Thus, if $\phi\colon H\to H$ is a grading-preserving linear map of the Hopf algebra $H$ to itself such that $\phi(1)=1$, then the logarithm of $\phi$ can be defined by
$$
\begin{equation*}
\log\phi=\phi_0-\frac{1}{2}\phi_0*\phi_0+ \frac{1}{3}\phi_0*\phi_0*\phi_0-\cdots,
\end{equation*}
\notag
$$
where $\phi_0\colon H\to H$ is the linear map given by $\phi_0\colon 1\mapsto0$, and $\phi_0$ coincides with $\phi$ on all homogeneous subspaces $H_k$ of positive grading $k>0$. Theorem 2.3 (see [60]). The projection $\pi\colon H\to H$ is the logarithm of the identity map: To prove this statement it suffices to verify that for any primitive element $p$ and for any nonlinear monomial in primitive elements.In particular, in the Hopf algebra of graphs $\mathcal{G}$ the projection $\pi$ onto the subspace of primitive elements whose kernel is the subspace of decomposable elements is given by
$$
\begin{equation}
\pi(G)=G-1!\sum_{U_1\sqcup U_2=V(G)}G\big|_{U_1}G\big|_{U_2}+ 2!\sum_{U_1\sqcup U_2\sqcup U_3=V(G)} G\big|_{U_1}G\big|_{U_2}G\big|_{U_3}-\cdots
\end{equation}
\tag{6}
$$
(see [42]), where the sums are taken over all unordered partitions of the vertes set $V(G)$ of $G$ into $2,3,4,\dots$ disjoint non-empty subsets. For example, $\pi(K_3)=K_3-3K_1K_2+2K_1^3$. It is easy to check that the linear combination of graphs on the right-hand side is indeed a primitive element. The projection $\pi\colon \mathcal{G}\to\mathcal{G}$ takes disconnected graphs to $0$ since they are decomposable elements of $\mathcal{G}$. In turn, the projections of connected graphs with $n$ vertices form a basis of the space $P(\mathcal{G}_n)$ of primitive elements with grading $n$. The identity map $\mathrm{Id}\colon \mathcal{G}\to \mathcal{G}$ preserves $4$-term relations, hence the same is true for its logarithm $\log \mathrm{Id}=\pi$. As a consequence, the projection formula also works in the Hopf algebra $\mathcal{F}$. In the Hopf algebra of chord diagrams $\mathcal{C}$ the projection formula looks similarly, except that the set $V(C)$ of chords of the chord diagram $C$ replaces the vertex set $V(G)$ of $G$. Remark. There is another way to associate a primitive element of the Hopf algebra of graphs with a graph, which perhaps looks simpler (see, for instance, [3]). Namely, let us take $G$ to the sum where summation is carried over all the spanning subgraphs of $G$. However, in contrast to the projection $\pi$, this operation is specific to the Hopf algebra of graphs and cannot be extended to a projection onto the subspace of primitives by linearity. 2.3. Graph invariants and the Hopf algebra structureThe behaviour of many graph invariants, as well as that of weight systems, is closely related to the structure of the corresponding Hopf algebra. The chromatic polynomial is a typical example. Let us extend the chromatic polynomial to a mapping $\chi\colon \mathcal{G}\to\mathbb{C}[c]$ of the whole space $\mathcal{G}$ onto the space of polynomials in one variable by linearity. Theorem 2.4. The value of a chromatic polynomial at any primitive element of the Hopf algebra $\mathcal{G}$ is a linear polynomial, that is, a monomial of degree $1$. In fact, this property is just the well-known binomiality property of the chromatic polynomial, which asserts that $\chi$ is a Hopf algebra homomorphism. Theorem 2.5. The chromatic polynomial of a graph $G$ satisfies the relation where summation on the right-hand side is carried over all the ordered partitions of the vertex set $V(G)$ of $G$ into two disjoint nonempty subsets. Graded homomorphisms of the Hopf algebra of graphs $\mathcal{G}$ to the Hopf algebra of polynomials $\mathbb{C}[p_1,p_2,\dots]$ are considered in more detail below (see § 2.4). Theorem 2.4 means, in particular, that the value of the chromatic polynomial at the projection $\pi(G)$ of an arbitrary graph $G$ onto the subspace of primitives is a linear polynomial. Equality (6) and the fact that the free term of the chromatic polynomial of any (non-empty) graph is $0$ imply that for any graph $G$ the polynomial $\chi_{\pi(G)}(c)$ coincides with the linear term of $\chi_G(c)$. Some other graph invariants behave similarly. Theorem 2.6 (see [24] and [38]). At any primitive element the skew characteristic polynomial of a graph is a constant. The interlace polynomial of a primitive element of order $n$ is a polynomial of degree at most $\bigl[\frac{n}2\bigr]$. 2.4. The Hopf algebra of graphs and integrabilityIn this section we describe the relationship between graph invariants and the theory of integrable systems of mathematical physics. With a graph invariant one can associate its averaging, namely, the result of summing the values of the invariant, taken with the weight inverse to the order of the automorphism group of the graph, over all graphs. If the invariant takes values in the ring of polynomials in infinitely many variables, then the result is a formal power series in these variables. For graphs on surfaces (embedded graphs) similar constructions are well known to lead to solutions of integrable hierarchies. However, for abstract graphs a result of this type was only proved recently (see [18] and also [14]). It asserts that, after an appropriate rescaling of the variables, the averaging of an umbral graph invariant becomes a solution of the Kadomtsev–Petviashvili hierarchy. The enumerative problems leading to other solutions of this hierarchy were described in detail in [37]. 2.4.1. The KP integrable hierarchyThe Kadomtsev–Petviashvili integrable hierarchy (KP hierarchy) is an infinite system of nonlinear partial differential equations for an unknown function $F(p_1,p_2,\dots)$ depending on infinitely many variables. The equations of the hierarchy are indexed by partitions of integers $n$, $n\geqslant4$, into two parts none of which equals $1$. The first two equations, which correspond to partitions of $4$ and $5$, respectively, are
$$
\begin{equation*}
\frac{\partial^2F}{\partial p_2^2}= \frac{\partial^2F}{\partial p_1\,\partial p_3}- \frac{1}{2}\biggl(\frac{\partial^2F}{\partial p_1^2}\biggr)^2- \frac{1}{12}\,\frac{\partial^4F}{\partial p_1^4}
\end{equation*}
\notag
$$
and
$$
\begin{equation*}
\frac{\partial^2F}{\partial p_2\,\partial p_3}= \frac{\partial^2F}{\partial p_1\partial p_4}- \frac{\partial^2F}{\partial p_1^2}\, \frac{\partial^2F}{\partial p_1\,\partial p_2}- \frac{1}{6}\,\frac{\partial^4F}{\partial p_1^3\,\partial p_2}\,.
\end{equation*}
\notag
$$
The left-hand side of each equation corresponds to a partition into two parts none of which equals $1$, while the terms on the right-hand sides correspond to the partitions of the same integer $n$ that include parts equal to $1$. For $n=6$ there are two equations corresponding to the partitions $2+4=6$ and $3+3=6$, and so on. The exponents of solutions of the KP hierarchy are called $\tau$-functions of this hierarchy. 2.4.2. Umbral graph invariantsDefinition 2.7. A graph invariant with values in the ring of polynomials $\mathbb{C}[q_1,q_2,\dots]$ in infinitely many variables is called umbral if its extension to a map $\mathcal{G}\to\mathbb{C}[q_1,q_2,\dots]$ by linearity is a graded Hopf algebra homomorphism; here the grading in the ring of polynomials is defined by the weights $w(q_i)=i$ of the variables, $i=1,2,3\dots$ . This definition immediately implies that a graph invariant is umbral if and only if its value at each primitive element of order $n$ is $cq_n$ for some constant $c$. Example 2.8. Stanley’s symmetrized chromatic polynomial is an example of an umbral invariant. Indeed, by Theorem 1.5 the Hopf algebra of weighted graphs modulo contraction–deletion relation is graded isomorphic to the Hopf algebra of polynomials. Among other umbral invariants and various specializations of these obtained by assigning concrete values to the variables $q_i$ there are many well-known graph invariants. Example 2.9. In [18] the Abel polynomials of graphs were introduced. With any spanning forest in a graph $G$ we associate the monomial in the variables $q_i$ that is equal to the product of the $iq_i$ over all trees in the forest, where $i$ denotes the number of vertices in the tree. Multiplication by $i$ corresponds here to the choice of a root in the tree, that is, such a monomial encodes the number of rooted trees corresponding to the chosen spanning forest. The Abel polynomial $A_G(q_1,q_2,\dots)$ is equal to the sum of these monomials over all spanning forests in $G$. If $G$ is a graph with $n$ vertices, then $A_G$ is a quasihomogeneous polynomial of degree $n$, the coefficient of $q_n$ in it being the complexity of $G$ times $n$. (Recall that the complexity of a graph is the number of spanning trees in it.) After substituting $q_i=x$, $i=1,2,\dots,n$, into the Abel polynomial $A_{K_n}$ of the complete graph on $n$ vertices, it becomes the conventional Abel polynomial $A_n(x)=x(x+n)^{n-1}$ [1]. The polynomials $A_n$, $n=0,1,2,\dots$, form a universal binomial sequence of polynomials [56]. Theorem 2.10 (see [18]). The Abel polynomial is an umbral graph invariant, that is, its extension by linearity to the Hopf algebra of graphs $\mathcal{G}$ is a graded Hopf algebra homomorphism. 2.4.3. Integrability of umbral invariantsTheorem 2.11. Let $I$ be an umbral graph invariant taking values in the ring of polynomials in infinitely many variables $q_1,q_2,\dots$ . Define the generating function where summation is carried over all the isomorphism classes of graphs and $\left|\operatorname{Aut}(G)\right|$ is the order of the automorphism group of $G$. Define the constants $i_n$ as the sums
$$
\begin{equation*}
i_n=n!\sum_{G\textrm{ is connected}} \frac{[q_n]I_G(q_1,q_2,\dots)}{|\operatorname{Aut}(G)|}
\end{equation*}
\notag
$$
of all the coefficients of the monomial $q_n$. Assume that for all $n=1,2,\dots$ the constant $i_n$ is not zero. Then after rescaling the variables the generating function $\mathcal{I}^\circ$ becomes the following linear combination of the one-part Schur polynomials:We underline that after rescaling mentioned in this theorem each umbral graph invariant $I$ becomes one and the same generating function. Summation over the connected graphs in the expression for $i_n$ can be replaced by summation over all graphs, since for any disconnected graph $G$ the coefficient of the monomial $q_n$ in the polynomial $I_G(q_1,q_2,\dots)$ is $0$. Since any linear combination of one-part Schur polynomials is a $\tau$-function of the KP hierarchy, we have the following. Corollary 2.12. After rescaling the variables as mentioned in Theorem 2.11, the generating function $\mathcal{I}$ becomes a $\tau$-function for the KP hierarchy. 3. Hopf algebra of chord diagrams and weight systems associated with Lie algebrasBoth the space of chord diagrams and the space of graphs are equipped with natural Hopf algebra structures. In this section we describe the relationship of this structure with the weight systems constructed from Lie algebras. This is a large and important class of weight systems related to quantum knot invariants. However, finding values of weight systems in this class is computationally a rather complicated problem since it requires computations in a noncommutative algebra. We recall known results and describe some new ones that help one to overcome these difficulties and obtain explicit answers in the case of the Lie algebras $\mathfrak{sl}(2)$ and $\mathfrak{gl}(N)$. 3.1. The structure of the Hopf algebra of chord diagramsSimilarly to graphs, chord diagrams generate a Hopf algebra. An essential distinction of this Hoph algebra from the Hopf algebra of graphs is that it is well defined only in the quotient space of chord diagrams modulo the subspace spanned by the $4$-term relations. Without taking this quotient there is no way to introduce multiplication consistently (while comultiplication is defined in a natural way). We define the product $C_1C_2$ of chord diagrams $C_1$ and $C_2$ as the chord diagram obtained by gluing their Wilson loops, cut at arbitrary points distinct from the endpoint of chords, preserving the orientations of these loops (see Fig. 6). This product is well defined modulo the $4$-term relations. Comultiplication takes any chord diagram $C$ to the sum of tensor products of chord diagrams obtained by dividing the set of chords in $C$ into two disjoint subsets:
$$
\begin{equation*}
\mu\colon C\mapsto \sum_{I\sqcup J=V(C)}C\big|_I\otimes C\big|_J.
\end{equation*}
\notag
$$
These operations transform the vector space
$$
\begin{equation*}
\mathcal{C}=\mathcal{C}_0\oplus\mathcal{C}_1\oplus\mathcal{C}_2\oplus\cdots,
\end{equation*}
\notag
$$
where $\mathcal{C}_n$ is spanned by the chord diagrams with $n$ chords, modulo the $4$-term relations, into a graded commutative cocommutative connected Hopf algebra [39]. The map taking a chord diagram to its intersection graph is extended by linearity to a homomorphism of the Hopf algebra of chord diagrams to the Hopf algebra of graphs modulo the $4$-term relations. The Hopf algebra of chord diagrams is naturally isomorphic to the Hopf algebra of Jacobi diagrams. A Jacobi diagram is an embedded $3$-regular graph with distinguished oriented loop, called the Wilson loop. The grading of such a diagarm is equal to half the number of vertices (it is easy to see that in a $3$-regular graph the number of vertices is necessarily even). Denote by $\mathcal{J}_n$ the space spanned by the Jacobi diagrams of grading $n$ considered modulo A skew-symmetry relation states that the change of orientation at any vertex of the diagram results in the change of sign of the corresponding element; an STU relation is shown in Fig. 7. It allows one to represent any Jacobi diagram as a linear combination of chord diagrams. This correspondence establishes an isomorphism between $\mathcal{J}$ and $\mathcal{D}$ [5].Similarly to the case of chord diagrams, the product of two Jacobi diagrams is defined by gluing their Wilson loops cut at arbitrary points distinct from the vertices of the factors. After removing the Wilson loop, a Jacobi diagram splits into a number of connected components (the connected components of a chord diagram are its chords). Comultiplication takes a Jacobi diagram to the sum of tensor products of its subdiagrams obtained by dividing the set of its connected components into two subsets in all possible ways (see Fig. 8). In particular, connected Jacobi diagrams are primitive elements of the Hopf algebra $\mathcal{J}$. These primitive elements span each homogeneous subspace $P(\mathcal{J}_n)$ of primitive elements (though they are usually subject to some linear relations). As a consequence, each space $P(\mathcal{J}_n)$, as well as the space $P(\mathcal{C}_n)$, which is isomorphic to the former, admits the natural filtration
$$
\begin{equation*}
\{0\}\subset P^{(1)}(\mathcal{J}_n)\subset P^{(2)}(\mathcal{J}_n) \subset\dots \subset P^{(n+1)}(\mathcal{J}_n)=P(\mathcal{J}_n),
\end{equation*}
\notag
$$
where the subspace $P^{(k)}(\mathcal{J}_n)$ is spanned by the connected Jacobi diagrams with at most $k$ vertices on the Wilson loop. A conjecture in [63] states that the projection $\pi(C)$ of a given chord diagram $C$ with $n$ chords onto the subspace of primitive elements lies in the subspace $P^{(k+1)}(\mathcal{J}_n)$, where $k$ is half the circumference of the intersection graph $g(C)$. (The circumference of a simple graph is the length of the longest cycle in it.) Results concerning the values of the weight systems associated with Lie algebras at the projections of chord diagrams onto the subspace of primitive elements that are stated below confirm this conjecture. 3.2. A universal construction of a weight system associated with a Lie algebraWith each metrized Lie algebra a weight system is associated, which takes values in the centre of the universal enveloping algebra of this Lie algebra. This centre is typically a ring of polynomials in several generators, namely, the Casimir elements of the Lie algebra. We describe below the construction of this weight system and provide various algorithms for its computation which lead to explicit formulae. 3.2.1. The definition of the weight systemA universal construction of the weight system obtained from a metrized Lie algebra looks as follows. Let $\mathfrak{g}$ be a Lie algebra equipped with an $\mathrm{ad}$-invariant scalar product (non-degenerate symmetric bilinear form) $\langle\,\cdot\,{,}\,\cdot\,\rangle$; here $\mathrm{ad}$-invariance means that $\langle [a,b],c\rangle=\langle a,[b,c]\rangle$ for any three elements $a,b,c\in\mathfrak{g}$. Choose an arbitrary basis $e_1,\dots,e_d$ in $\mathfrak{g}$, $d=\dim\mathfrak{g}$, and denote the elements of the dual basis by $e_1^*,\dots,e_d^*$: $\langle e_i,e_j^*\rangle=\delta_{i,j}$, $i,j=1,\dots,d$. Now let $C$ be a chord diagram with $n$ chords. Choose an arbitrary point on a circle that is distinct from the endpoints of the chords and call it the cut point. Then, for each chord $a$, pick an index $i_a$ in the range $1,\dots,d$, and assign the basic element $e_{i_a}$ to one endpoint of the chord and the element $e_{i_a}^*$ of the dual basis to its other endpoint. Multiply the resulting $2n$ elements of the Lie algebra in the order prescribed by the orientation of the Wilson loop, starting from the cut point. The resulting monomial is considered as an element of the universal enveloping algebra $U\mathfrak{g}$ of the Lie algebra under consideration. Sum the monomials obtained over all $d^n$ possible ways to put indices on the chords; denote the resulting sum by $w_\mathfrak{g}(C)\in U\mathfrak{g}$. For example, for the arc diagram obtained by cutting the corresponding chord diagram (see Fig. 9) the resulting element of the universal enveloping algebra is equal to Theorem 3.1 (see [39]). 1. The element $w_\mathfrak{g}(C)$ is independent of the choice of the basis $e_1,\dots,e_d$ in the Lie algebra. 2. $w_\mathfrak{g}(C)$ is independent of the choice of a cut point in the chord diagram. 3. $w_\mathfrak{g}(C)$ belongs to the centre $ZU\mathfrak{g}$ of $U\mathfrak{g}$. 4. The invariant $w_\mathfrak{g}$ satisfies the $4$-term relations, and thus is a weight system. 5. The resulting weight system taking values in the commutative ring $ZU\mathfrak{g}$ is multiplicative, that is, $w_\mathfrak{g}(C_1C_2)=w_\mathfrak{g}(C_1)w_\mathfrak{g}(C_2)$ for any two chord diagrams $C_1$ and $C_2$. 3.2.2. Jacobi diagrams and the values of the weight system at primitive elementsThe definition of the weight system associated with a Lie algebra has a convenient reformulation in terms of Jacobi diagrams. Given a metrized Lie algebra $\mathfrak{g}$ consider the linear $3$-form $\omega(a,b,c)=\langle [a,b],c\rangle$ treated as an element of the third tensor power $\mathfrak{g}^*\otimes\mathfrak{g}^*\otimes\mathfrak{g}^*$. Denote by $\omega^*\in\mathfrak{g}\otimes\mathfrak{g}\otimes\mathfrak{g}$ the corresponding dual tensor obtained by identifying $\mathfrak{g}$ with the dual space $\mathfrak{g}^*$ using the scalar product $\langle\,\cdot\,{,}\,\cdot\,\rangle$. Note that $\omega^*$ is invariant with respect to cyclic permutations of the tensor factors, and it changes sign under transpositions of any two factors. Now consider a Jacobi diagram. We associate the tensor $\omega^*$ with each of its interior vertices by labelling factors of the tensor product with edges exiting from this vertex. With each interior edge, that is, an edge connecting two interior vertices of the diagram, we associate the contraction of tensors corresponding to the endpoints of the edge by using the scalar product. The result of this contraction is an element of a tensor power of $\mathfrak{g}$ whose factors are labelled by the vertices lying on the Wilson loop. Finally, to this tensor we apply the homomorphism to the universal enveloping algebra that sends the tensor product of some elements of $\mathfrak{g}$ to their product in $U\mathfrak{g}$ in the order they follow one another on the Wilson loop oriented counterclockwise starting from the cut point. The resulting element of $U\mathfrak{g}$ is nothing but the value of the weight system $w_{\mathfrak{g}}$ at the Jacobi diagram in question. This definition is particularly useful for the efficient computation of the values of the weight system $w_\mathfrak{g}$ at primitive elements represented by connected Jacobi diagrams. The universal enveloping algebra $U\mathfrak{g}$ of the Lie algebra $\mathfrak{g}$ admits a filtration by vector subspaces:
$$
\begin{equation*}
U^{(0)}{\mathfrak{g}}\subset U^{(1)}{\mathfrak{g}}\subset U^{(2)}{\mathfrak{g}}\subset\dots\subset U{\mathfrak{g}},\qquad U^{(0)}{\mathfrak{g}}\cup U^{(1)}{\mathfrak{g}}\cup U^{(2)}{\mathfrak{g}}\cup\dots=U{\mathfrak{g}},
\end{equation*}
\notag
$$
where $U^{(k)}\mathfrak{g}$ is spanned by the monomials of degree at most $k$ in the elements of $\mathfrak{g}$. This filtration, in turn, induces a filtration in the centre $ZU\mathfrak{g}$ of the universal enveloping algebra. It was shown in [20] that for the weight system corresponding to a given metrized Lie algebra $\mathfrak{g}$, its value at a primitive element lying in the filtration term $P^{(k)}$ belongs to $ZU^{(k)}$. 3.3. The $\mathfrak{sl}(2)$-weight systemThe Lie algebra $\mathfrak{sl}(2)$ is the simplest noncommutative Lie algebra with non-degenerate $\mathrm{ad}$-invariant scalar product. In contrast to more complicated Lie algebras, the $\mathfrak{sl}(2)$-weight system admits the Chmutov–Varchenko recurrence relation, which simplifies dramatically its explicit computation. Nevertheless, even with this recurrence relation computation remains quite laborious and leads to explicit answers only in a limited number of cases. In particular, no explicit formula for the values of the $w_{\mathfrak{sl}(2)}$-weight system at chord diagrams all of whose chords intersect pairwise was known until recently. We describe below the corresponding result due to Zakorko, as well as the result of Zinova and Kazarian about the values of $w_{\mathfrak{sl}(2)}$ at chord diagrams whose intersection graphs are complete bipartite. The values of $w_{\mathfrak{sl}(3)}$ at some chord diagrams with complete bipartite intersection graphs were calculated in [62]. 3.3.1. The Chmutov–Varchenko recursion relationThe weight system $w_\mathfrak{g}$ associated with a given Lie algebra $\mathfrak{g}$ takes values in the commutative ring $ZU\mathfrak{g}$. However, the terms of the expression for $w_\mathfrak{g}(C)$ lie in the complicated noncommutative algebra $U\mathfrak{g}$. Therefore, a direct application of the definition is not efficient in practice, and one needs to find methods for more efficient computation of such a weight system that would deal with commutative rings (say, rings of polynomials) at each step. The simplest noncommutative Lie algebra is $\mathfrak{sl}(2)$. An efficient algorithm for computing this weight system was proposed by Chmutov and Varchenko [20]. The centre of the universal enveloping algebra $U\mathfrak{sl}(2)$ is the ring of polynomials of one variable, which is represented by the Casimir element. We denote this generator by $c$. Thus, the weight system $w_{\mathfrak{sl}(2)}$ takes values in the algebra of polynomials in $c$. The value $w_{\mathfrak{sl}(2)}(C)$ at a chord diagram $C$ with $n$ chords is a polynomial of degree $n$ in $c$ with leading coefficient $1$ and zero free term (for $n>0$). Theorem 3.2. The weight system $w_{\mathfrak{sl}(2)}$ associated with the Lie algebra $\mathfrak{sl}(2)$ satisfies the following relations. 1. $w_{\mathfrak{sl}(2)}$ is a multiplicative weight system: $w_{\mathfrak{sl}(2)}(C_1C_2)=w_{\mathfrak{sl}(2)}(C_1)w_{\mathfrak{sl}(2)}(C_2)$ for arbitrary chord diagrams $C_1$ and $C_2$. As a consequence, the value of the weight system at the empty chord diagram is equal to $1$. 2. If the diagram $C$ is obtained from a diagram $C'$ by adding a chord disjoint from the chords in $C'$, then 3. If the diagram $C$ is obtained from a diagram $C'$ by adding a chord intersecting exactly one chord in $C'$, then
$$
\begin{equation*}
w_{\mathfrak{sl}(2)}(C)=(c-1)w_{\mathfrak{sl}(2)}(C').
\end{equation*}
\notag
$$
4. The $6$-term relations shown in Fig. 10 hold. As usual, in these relations it is assumed that, apart from the chords shown, all diagrams in the relations contain some other chords, which are the same for all six diagrams. The Chmutov–Varchenko relations are sufficient to compute the value of the weight system at an arbitrary chord diagram. Indeed, if relations 1–3 are not applicable to a given chord diagram, then this diagram contains necessarily a chord to which relation 4 can be applied. All diagrams obtained by applying the relations are simpler than the original ones in the following sense: the two diagrams on the right-hand side have fewer chords than each diagram on the left-hand side; all diagrams on the left-hand side have an equal number of chords, but the last three of them have fewer pairs of intersecting chords than the first diagram. This implies that by applying these relations repeatedly the value of the weight system is computed in a unique way in finitely many steps. The Chmutov–Varchenko relations can be also used for an axiomatic definition of the weight system $w_{\mathfrak{sl}(2)}$. With this approach, the equalities of the theorem are taken as the definition of the weight system. Then the assertion that the function is well defined becomes a non-trivial statement, which claims that the result of computation is independent of the order in which the Chmutov–Varchenko relations are applied. The $4$-term relations for the function constructed are a corollary of the Chmutov–Varchenko relations, that is, this is a weight system indeed. 3.3.2. The $\mathfrak{sl}(2)$-weight system for graphsThe following result due to Chmutov and Lando is specific for the Lie algebra $\mathfrak{sl}(2)$ and the weight system associated with it. Its analogue for the Lie algebra $\mathfrak{sl}(3)$, for instance, does not hold. Theorem 3.3 (see [19]). The value of the weight system $w_{\mathfrak{sl}(2)}$ at any chord diagram is uniquely determined by its intersection graph. This theorem implies that the weight system $w_{\mathfrak{sl}(2)}$ defines a function on those graphs that are the intersection graphs of chord diagrams. This function vanishes at those combinations of intersection graphs that are involved into $4$-term relations. Conjecture 3.4 (Lando). The weight system $w_{\mathfrak{sl}(2)}$ admits an extension to a function on the graphs satisfying the $4$-term relation for graphs. This extension is unique. The existence of such an extension would mean that $w_{\mathfrak{sl}(2)}$ vanishes at any linear combination of intersection graphs that is a consequence of the $4$-term relations for graphs (such a linear combination is not necessarily a consequence of the $4$-term relations for chord diagrams). The uniqueness of such an extension is not specific to $w_{\mathfrak{sl}(2)}$. It is related to the question of whether or not the map sending a chord diagram to its intersection graph is epimorphic (see § 1.3). The conjecture was checked using computer calculations for graphs with at most eight vertices (Krasilnikov [40]). Note that for the extension obtained by Krasilnikov the values of $w_{\mathfrak{sl}(2)}$ at some graphs with eight vertices are not integers (all such graphs are not intersection graphs since the Chmutov–Varchenko relations guarantee that the values of the weight system at all intersection graphs are polynomials with integer coefficients). There are also some other pieces of evidence supporting Conjecture 3.4. For instance, the required extension is known for the top coefficient of the value of $w_{\mathfrak{sl}(2)}$ at the projection of a chord diagram onto the subspace of primitive elements. The value $w_{\mathfrak{sl}(2)}(\pi(C))$ of the weight system $w_{\mathfrak{sl}(2)}$ at the projection of a chord diagram $C$ with $2n$ chords onto the subspace of primitive elements is a polynomial of degree at most $n$. Theorem 3.5 (see [41] and [6]). The coefficient of $c^n$ in the value $w_{\mathfrak{sl}(2)}(\pi(C))$ of the weight system $w_{\mathfrak{sl}(2)}$ at the projection of a chord diagram $C$ with $2n$ chords onto the subspace of primitive elements coincides with $2\log \nu(g(C))$, the doubled logarithm of the non-degeneracy of the intersection graph of the diagram (the logarithm is understood in the sense of convolution in the Hopf algebra). Since the non-degeneracy is a $4$-invariant of a graph, this result supports the conjecture. One possible approach to the proof of Conjecture 3.4 is to look for a $4$-invariant of graphs that takes values in the ring of polynomials in one variable and whose values at intersection graphs coincide with those of $w_{\mathfrak{sl}(2)}$. In order to construct such an invariant it is important to have a large range of explicitly computed values of $w_{\mathfrak{sl}(2)}$ at graphs: these values can indicate which characteristics of the graph are reflected in $w_{\mathfrak{sl}(2)}$. In many ways, the results presented below have been inspired by this problem. In some respects the weight system $w_{\mathfrak{sl}(2)}$ resembles very much the chromatic polynomial of a graph:
Thus it is worthwhile to know whether an analogue of a theorem of Huh [33], who proved it in the case of the chromatic polynomial, holds for the weight system $w_{\mathfrak{sl}(2)}$ as well. Problem. Is it true that the sequence of absolute values of the coefficients of the weight system $w_{\mathfrak{sl}(2)}$ is logarithmically convex for an arbitrary chord diagram? In particular, is it true that this sequence is unimodular, that is, it is first increasing and then decreasing? Huh’s proof relates the chromatic polynomial to the geometry of algebraic manifolds. It would be interesting to find a similar relationship for the $\mathfrak{sl}(2)$-weight system. 3.3.3. The values of the $\mathfrak{sl}(2)$-weight system on complete graphsThe Chmutov–Varchenko relations enable one both to compute the values of the weight system $w_{\mathfrak{sl}(2)}$ at concrete chord diagrams and to obtain closed formulae for some infinite series of chord diagrams. In particular, consider the chord diagram $K_n$ formed by $n$ pairwise intersecting chords. The intersection graph of this diagram is the complete graph on $n$ vertices. For complete graphs the computation of one graph invariant or another causes usually no difficulties because of the high symmetry of complete graphs. However, in the case of the weight system $w_{\mathfrak{sl}(2)}$ this problem has proved to be surprisingly difficult, and the answer is rather unexpected. The following statement was suggested by Lando around 2015 as a conjecture. It was partially proved (for the linear terms of polynomials) in [7]. Theorem 3.6 (see [65]). The generating series for the values of the weight system associated with the Lie algebra $\mathfrak{sl}(2)$ at complete graphs admits the following expansion in an infinite continued fraction: where It is useful to compare this expansion in a continued fraction with a similar expansion for the generating function of the chromatic polynomials of complete graphs:
$$
\begin{equation*}
\begin{aligned} \, \sum_{n=0}^\infty \chi_{K_n}(c)t^n&=1+ct+c(c-1)t^2+c(c-1)(c-2)t^3 \\ &\qquad+c(c-1)(c-2)(c-3)t^4+\cdots \\ &=\frac1{1+a_0t+\dfrac{b_1t^2}{1+a_1t+\dfrac{b_2t^2}{1+a_2t+\cdots}}}\,, \end{aligned}
\end{equation*}
\notag
$$
where As an intermediate step of computations, the proof of this theorem in [65] also contains the following efficient way of computing the values of the weight system from the theorem. Consider the linear operator $T$ acting as follows on the space of polynomials in one variable $x$: and for any polynomial $f$.Theorem 3.7 (see [65]). The value of the weight system $\mathfrak{sl}(2)$ at a chord diagram with complete intersection graph is equal to the value of the polynomial $T^n(1)$ at the point $x=c$, From the known values of $w_{\mathfrak{sl}(2)}$ at complete graphs it is easy to find its values at their projections onto the subspace of primitive elements. Indeed, the polynomials in complete graphs form a Hopf subalgebra of the Hopf algebra of graphs $\mathcal{G}$. The order of the automorphism group of the complete graph $K_n$ on $n$ vertices is $n!$. This enables one to represent the exponential generating function for the projections of complete graphs onto the subspace of primitives as the logarithm of the exponential generating function for complete graphs:
$$
\begin{equation*}
\sum_{n=1}^\infty\pi(K_n)\,\frac{t^n}{n!}= \log \sum_{n=0}^\infty K_n\frac{t^n}{n!}\,.
\end{equation*}
\notag
$$
Applying $w_{\mathfrak{sl}(2)}$ to both parts of this identity and substituting in the values $w_{\mathfrak{sl}(2)}(K_n)$ that we know already, we obtain the first terms of the expansion:
$$
\begin{equation*}
\begin{aligned} \, \sum_{n=1}^\infty w_{\mathfrak{sl}(2)}(\pi(K_n))\,\frac{t^n}{n!}&= c\,\frac{t}{1!}-c\,\frac{t^2}{2!}+2c\,\frac{t^3}{3!}+ (2c^2-7c)\frac{t^4}{4!}-(24c^2-38c)\frac{t^5}{5!} \\ &\qquad-(16c^3-284c^2+295c)\frac{t^6}{6!}+\cdots\,. \end{aligned}
\end{equation*}
\notag
$$
3.3.4. The Algebra of sharesDefinition 3.8. A share with $n$ chords is an ordered pair of oriented intervals in which $2n$ pairwise distinct points, grouped into $n$ disjoint pairs, are fixed, which is considered up to the orientation-preserving diffeomorphisms of each of the two intervals. As the intervals we often take two arcs of the Wilson loop. In this case a share is the part of a chord diagram that is formed by the chords both of whose endpoints belong to a fixed pair of arcs, while no other chord has an endpoint on these arcs. If a pair of arcs of a chord diagram forms a share, then its complement is also a share. In this case we call the chord diagram a join of two shares and denote it by $S_1\mathbin{\#}S_2$ (see Fig. 11). In a join the end of the first interval of the share $S_1$ is attached to the beginning of the first interval in $S_2$, the end of the first interval in $S_2$ is attached to the beginning of the second interval in $S_1$, the end of the second interval in $S_1$ is attached to the beginning of the second interval in $S_2$, and, finally, the end of the second interval in $S_2$ is attached to the beginning of the first interval in $S_1$. Taking the join is a noncommutative operation. With each share $S$ one can associate a chord diagram by attaching the end of each of the two intervals to the beginning of the other, thus combining these intervals into a Wilson loop. We denote this chord diagram by $\overline{S}$ and call it the closure of $S$. We also call $g(\overline{S})$ the intersection graph of the share $S$ and denote it by $g(S)$. Two shares can be multiplied by attaching their intervals with coinciding numbers (see Fig. 12). This multiplication is noncommutative. Shares are a special case of tangle diagrams (see [17], § 5.10). Examples of shares with irreversible orientation were presented in [26]. The irreversibility is established using a universal weight system associated with the Lie algebra $\mathfrak{gl}(4)$. The space spanned by the isomorphism classes of shares can be endowed with the relations analogous to the Chmutov–Varchenko relations in Theorem 3.2. Namely, we can assume that all diagrams taking part in a $6$-term relation are, in fact, shares. There is, however, some subtlety in defining relations 2 and 3 in the theorem. Namely, suppose a share $S$ is obtained from a share $S'$ by adding a single chord both of whose endpoints belong to the same interval number $i$, $i\in\{1,2\}$, which intersects at most one of the other chords. Then the relations for the shares have the form in the cases where the chord in question intersects none of the other chords or just one of them, respectively. The elements $c_1$ and $c_2$ are defined in Proposition 3.9 below.Denote by $\mathcal{S}$ the quotient space of the vector space spanned by all shares modulo the subspace spanned by the $6$-term relations and relations (8). This quotient space is endowed with the algebra structure induced by the operation of multiplication of shares. Note that since the $6$-term relations are not homogeneous, the algebra $\mathcal{S}$ is filtered rather than graded. Proposition 3.9. The algebra $\mathcal{S}$ is commutative and isomorphic to the algebra of polynomials in the three generators $c_1$, $c_2$, and $x$ shown in Fig. 13. This proposition states that, modulo the $6$-term relations and relations (8), each share admits a unique representation as a linear combination of the shares $1,x,x^2,x^3,\dots$, where the share $x^n$ is formed by $n$ parallel chords with endpoints on distinct intervals; the coefficients in these linear combinations are polynomials in $c_1$ and $c_2$. One reason for introducing the algebra $\mathcal{S}$ is the following observation. Proposition 3.10. Assume that two shares (or two linear combinations of shares) $S_1$ and $S_2$ represent the same element of $\mathcal{S}$. Then for an arbitrary share $R$ the $\mathfrak{sl}(2)$-weight system takes equal values at the chord diagrams obtained by joining $S_1$ and $S_2$ with $R$: As the additional share $R$ one can choose, for example, the tuple of $n$ mutually parallel chords with endpoints on distinct arcs, or the tuple of $n$ pairwise intersecting chords with endpoints on distinct arcs. 3.3.5. The values of the $\mathfrak{sl}(2)$-weight system at complete bipartite graphsThe chord diagrams whose intersection graphs are complete bipartite form another wide class of chord diagrams for which the values of $w_{\mathfrak{sl}(2)}$ are given by explicit formulae. Denote by $K_{m,n}$ the chord diagram formed by $m$ parallel horizontal chords and $n$ parallel vertical chords. The intersection graph of such a chord diagram is the complete bipartite graph that has $m$ vertices in one part and $n$ vertices in the other. Equivalently, $K_{m,n}$ is the join of the two shares formed by $m$ and $n$ parallel chords, respectively, which have their endpoints on distinct arcs. For each $m=0,1,2,3,\dots$, consider the generating function
$$
\begin{equation*}
G_m=G_m(c,t)=\sum_{n=0}^\infty w_{\mathfrak{sl}(2)}(K_{m,n})t^n
\end{equation*}
\notag
$$
of the values of the weight system $w_{\mathfrak{sl}(2)}$ at the chord diagrams $K_{m,n}$. Theorem 3.11. The generating functions $G_{m}$ satisfy the relation where the coefficients $s_{i,m}$ are given by the generating power series Note that $G_m$ also enters the right-hand side of the above equation with coefficient $s_{m,m}=c-m(m-1)/2$. Moving this term to the left-hand side, we can make the recurrence more explicit:
$$
\begin{equation*}
G_m=\frac{1}{1-s_{m,m} t}\biggl(c^m+t\sum_{i=0}^{m-1}s_{i,m} G_i\biggr).
\end{equation*}
\notag
$$
By induction this implies the following. Corollary 3.12. The generating function $G_m$ can be represented as a finite linear combination of the geometric series The coefficients of these geometric series are polynomials in $c$. For small values of $m$ recurrence yields
$$
\begin{equation*}
\begin{aligned} \, G_0&=\frac{1}{1-ct}\,, \\ G_1&=\frac{c}{1-(c-1)t}\,, \\ G_2&=\frac{c^2}{3 (1-ct)}+\frac{c}{2\,(1-(c-1)t)}+ \frac{c(4 c-3)}{6(1-(c-3)t)}\,, \\ G_3&=\frac{c^2}{6(1-ct)}+\frac{c(3c^2-2c+2)}{5(1-(c-1)t)}+ \frac{c(4 c-3)}{3(1-(c-3)t)}+\frac{c(c-2)(4 c-3)}{10(1-(c-6)t)}\,. \end{aligned}
\end{equation*}
\notag
$$
The above statement admits the following generalization. Given an arbitrary share $S$, denote by $(S,n)$ the chord diagram that is the join of $S$ and the share $x^n$ consisting of $n$ parallel chords. Introduce the generating function
$$
\begin{equation*}
f_S=\sum_{n=0}^\infty w_{\mathfrak{sl}(2)}((S,n))\, t^n.
\end{equation*}
\notag
$$
Corollary 3.13. The generating function $f_S$ can be represented as a finite linear combination of geometric series of the form where $m$ is the number of those chords of $S$ whose endpoints belong to distinct arcs. The coefficients of these progressions are polynomials in $c$. Indeed, if a share $S$ can be presented as a linear combination of the basis shares $x^k$, modulo the $6$-term relations and relations (8), then the series $f_S$ can be expressed as the linear combination of the series
$$
\begin{equation*}
\sum_{n=0}^\infty w_{\mathfrak{sl}(2)}((x^k,n))t^n= \sum_{n=0}^\infty w_{\mathfrak{sl}(2)}(K_{k,n})t^n=G_k
\end{equation*}
\notag
$$
with the same coefficients, that is, and we can apply the above corollary. Similarly to the case of complete graphs, polynomials in complete bipartite graphs form a Hopf subalgebra in $\mathcal{G}$. There are formulae for the values of the weight system $w_{\mathfrak{sl}(2)}$ at the projections of complete bipartite graphs onto the subspace of primitives, which generalize the formula for the logarithm of the exponential generating function for complete graphs (see details in [31]). 3.3.6. The values of the $\mathfrak{sl}(2)$-weight system at graphs that are not intersection graphsNot each graph is the intersection graph of some chord diagrams, but using $4$-term relations for graphs one can try to express it in terms of intersection graphs and extend to it the $\mathfrak{sl}(2)$-weight system. The formulae in the previous section enable one to obtain such an extension not only to some particular graph, but also to infinite sequences of graphs. Given an arbitrary graph $G$, denote by $(G,n)$ its connected sum with $n$ isolated vertices, that is, the graph obtained by adding $n$ vertices to $G$ and connecting each additional vertex with each vertex of $G$. Now take the graph $C_5$, the cycle on $5$ vertices, as $G$. For $n\geqslant1$ the graph $(C_5,n)$ is not an intersection graph. Proposition 3.14 (see [30]). Suppose Conjecture 3.4 about the extendability of the $\mathfrak{sl}(2)$-weight system to the space of graphs is valid. Then the values of an extended weight system at the graphs $(C_5,n)$ are given by the generating function The proof is obtained by using the $4$-term relation shown in Fig. 14. Each graph on the right-hand side is an intersection graph. Moreover, it is the intersection graph of a chord diagram of the form $(S,n)$ for some share $S$ (see Fig. 15).Using the argument from the previous section we can express each share thus obtained in terms of the basic shares $x^m$, $m=0,1,\dots,5$, and can express in this way the generating function of the graphs $(C_5,n)$ in terms of the corresponding generating functions of complete bipartite graphs. 3.4. The $\mathfrak{gl}(N)$-weight systemUntil recently no recursion similar to the Chmutov–Varchenko recursion was known for Lie algebras other than $\mathfrak{sl}(2)$, and essentially the only known way to compute the values of the weight system associated with one Lie algebra or another was to apply the definition directly, which was extremely laborious. Here we explain the results presented in the recent paper [63] and devoted to the computation of the weight systems associated with the Lie algebras $\mathfrak{gl}(N)$. In [64] these results were extended to the weight systems corresponding to the Lie suparalgebras $\mathfrak{gl}(m|n)$. As a basis in $\mathfrak{gl}(N)$ we can choose the matrix units $E_{ij}$, which have one at the intersection of the $i$th row and $j$th column, all other entries being zeros. The commutator of two matrix units has the form $[E_{ij},E_{kl}]=\delta_{jk}E_{il}-\delta_{il}E_{jk}$. The standard invariant scalar product is given by $\langle x,y\rangle=\operatorname{Tr}(xy)$, and the dual basis with respect to this scalar product is $E_{ij}^*=E_{ji}$. The centre $ZU(\mathfrak{gl}(N))$ is generated freely by the Casimir elements $C_1,C_2,\dots,C_N$, where
$$
\begin{equation*}
C_{1}=\sum_{i=1}^NE_{ii},\qquad C_{2}=\sum_{i,j=1}^NE_{ij}E_{ji},
\end{equation*}
\notag
$$
and, more generally,
$$
\begin{equation*}
C_{k}=\sum_{i_1,i_2,\dots,i_k=1}^NE_{i_1i_2}E_{i_2i_3}\cdots E_{i_k i_1}.
\end{equation*}
\notag
$$
Casimir elements with indices greater than $N$ are defined similarly. They also belong to the centre, but can be expressed as polynomials in the Casimir elements with indices at most $N$. Thus, the values of the weight system associated with the Lie algebra $\mathfrak{gl}(N)$ are polynomials in the Casimir elements. For example, it is easy to see that for the chord diagram $K_1$, which consists of a single chord, we have $w_{\mathfrak{gl}(N)}(K_1)=C_2$. Theorem 3.15 (see [63]). There is a universal weight system, denoted by $w_{\mathfrak{gl}}$ and taking values in the ring of polynomials in infinitely many variables $N,C_1,C_2,\dots$, whose values for a fixed positive integer $N$ coincide with the values of the $\mathfrak{gl}(N)$- weight system. It is easy to see that for each chord diagram $C$ with $n$ chords the value of $w_{\mathfrak{gl}(N)}(C)$ for $N\geqslant n$ is a polynomial in $C_1,\dots,C_{n}$. The theorem asserts that the coefficients of this polynomial are polynomials in $N$. Moreover, the universal formula obtained for $w_{\mathfrak{gl}(N)}(C)$ remains valid for $N<n$ as well. Below we define the weight system $w_{\mathfrak{gl}}$ at arbitrary permutations and give a recurrence relation for its computation. 3.4.1. The $\mathfrak{gl}(N)$-weight system on the permutations and recurrence relationsLet $m$ be a positive integer, and let $S_m$ be the group of all permutations of the elements $\{1,2,\dots,m\}$; for an arbitrary $\sigma\in S_m$ we set
$$
\begin{equation*}
w_{\mathfrak{gl}(N)}(\sigma)=\sum_{i_1,\dots,i_m=1}^NE_{i_1i_{\sigma(1)}} E_{i_2i_{\sigma(2)}}\cdots E_{i_mi_{\sigma(m)}}\in U\mathfrak{gl}(N).
\end{equation*}
\notag
$$
The element thus constructed belongs, in fact, to the centre $ZU\mathfrak{gl}(N)$. In addition, it is invariant under conjugation by the cyclic permutation:
$$
\begin{equation*}
w_{\mathfrak{gl}(N)}(\sigma)=\sum_{i_1,\dots,i_m=1}^N E_{i_2i_{\sigma(2)}} \cdots E_{i_mi_{\sigma(m)}}E_{i_1i_{\sigma(1)}}.
\end{equation*}
\notag
$$
For example, the Casimir element $C_m$ corresponds to the cyclic permutation $1\mapsto2\mapsto\cdots\mapsto m\mapsto 1$. On the other hand any arc diagram with $n$ arcs can be regarded as an involution without fixed points on the set of $m=2n$ elements. The value of $w_{\mathfrak{gl}(N)}$ at the permutation given by this involution coincides with the value of the $\mathfrak{gl}(N)$-weight system at the corresponding chord diagram. For example, for the chord diagram $K_n$ we have
$$
\begin{equation*}
w_{\mathfrak{gl}(N)}(K_n)= w_{\mathfrak{gl}(N)}((1\, n{+}1)(2\, n{+}2)\cdots(n\, 2n)).
\end{equation*}
\notag
$$
Any permutation can be represented by a directed graph. The $m$ vertices of this graph correspond to the permuted elements. They are placed along an oriented circle and ordered cyclically in the direction of the circle. The directed edges of the graph show the action of the permutation (so that there is one incoming and one outgoing edge at each vertex). The directed graph $G(\sigma)$ consists of these $m$ vertices and $m$ edges (see, for example, Fig. 16; the circle containing the vertices of the graph is shown by the horizontal line). Theorem 3.17 (see [63]). The value of the weight system $w_{\mathfrak{gl}(N)}$ at a permutation possesses the following properties. (a) The weight system $w_{\mathfrak{gl}(N)}$ is multiplicative with respect to connected sums (concatenations) of permutations. Therefore, the value of $w_{\mathfrak{gl}(N)}$ at the empty graph (without vertices) is $1$. (b) At the cyclic permutation of elements whose cyclic order is consistent with the permutation the value of $w_{\mathfrak{gl}(N)}$ coincides with the corresponding Casimir element,
$$
\begin{equation*}
w_{\mathfrak{gl}(N)}(1\mapsto2\mapsto\cdots\mapsto m\mapsto 1)=C_m.
\end{equation*}
\notag
$$
(c) For any two neighbouring elements $k$ and $k+1$ of the set $\{1,2,\dots,m\}$ the values of the invariant $w_{\mathfrak{gl}_N}$ at an arbitrary permutation $\sigma\in S_m$ satisfy the identity shown in Fig. 17. On the graphs on the left-hand side of this identity two neighbouring vertices and the edges incident to them are shown. In the graphs on the right-hand side these two vertices are replaced by a single one. All other vertices and (half-)edges are the same for all four graphs participating in the identity shown in Fig. 17. In the exceptional case where $\sigma(k+1)=k$ the identity acquires the form shown in Fig. 18. Using the identity from the theorem each graph can be reduced to a monomial in the generators $C_k$ (that is, a concatenation of independent cycles) modulo the graphs with fewer vertices. This leads to recursive computation of the values of the invariant $w_{\mathfrak{gl}(N)}$. Corollary 3.18. The value of $w_{\mathfrak{gl}(N)}$ at an arbitrary permutation belongs to the centre $ZU\mathfrak{gl}(N)$ of the universal enveloping algebra and is a polynomial in $N, C_1,C_2,\dots$ . This polynomial is universal (the same for all the $\mathfrak{gl}(N)$). We denote the mapping taking a permutation to this universal polynomial by $w_{\mathfrak{gl}}$. Theorem 3.15 specializes Corollary 3.18 to the case when the permutation is an involution without fixed points. Below we present a table of values of $w_{\mathfrak{gl}}$ at the chord diagrams $K_n$, for a few first values of $n$:
$$
\begin{equation*}
\begin{aligned} \, w_{\mathfrak{gl}}(K_2)&=C_1^2+C_2^2-N\,C_2, \\ w_{\mathfrak{gl}}(K_3)&=C_2^3+3 C_1^2 C_2+2 C_2 N^2+(-2 C_1^2-3 C_2^2) N, \\ w_{\mathfrak{gl}}(K_4)&=3 C_1^4-4 C_1^3+6 C_2^2 C_1^2+2 C_1^2- 8 C_3 C_1+C_2^4+6 C_2^2 \\ &\qquad+(-6 C_2^3-14 C_1^2 C_2+6 C_1 C_2-2 C_2+2 C_4) N \\ &\qquad+(6 C_1^2+11 C_2^2-2 C_3) N^2-6 C_2 N^3, \\ w_{\mathfrak{gl}}(K_5)&=C_2^5+10 C_1^2 C_2^3+30 C_2^3+15 C_1^4 C_2- 20 C_1^3 C_2+10 C_1^2 C_2-40 C_1 C_3 C_2 \\ &\qquad+(-20 C_1^4+48 C_1^3-50 C_2^2 C_1^2-32 C_1^2 \\ &\qquad\qquad\qquad\;\;+30 C_2^2 C_1+96 C_3 C_1-10 C_2^4-82 C_2^2+ 10 C_2 C_4) N \\ &\qquad+(35 C_2^3+70 C_1^2 C_2-72 C_1 C_2-10 C_3 C_2+32 C_2-24 C_4) N^2 \\ &\qquad+(-24 C_1^2-50 C_2^2+24 C_3) N^3+24 C_2 N^4. \end{aligned}
\end{equation*}
\notag
$$
Similarly to the case of $\mathfrak{sl}(2)$, the values of the weight system $w_{\mathfrak{gl}(N)}$ at the projections of complete graphs onto the subspace of primitives can be computed by taking the logarithm of the corresponding exponential generating function. 3.4.2. Computing the $\mathfrak{gl}(N)$-weight system by means of the Harish–Chandra isomorphismIn this section we describe one more way, proposed in [63], to compute the $\mathfrak{gl}(N)$-weight system. The algebra $U\mathfrak{gl}(N)$ admits the decomposition into a direct sum
$$
\begin{equation}
U\mathfrak{gl}(N)=(\mathfrak{n}_-\,U\mathfrak{gl}(N)+ U\mathfrak{gl}(N)\,\mathfrak{n}_+)\oplus U\mathfrak{h},
\end{equation}
\tag{9}
$$
where $\mathfrak{n}_-$, $\mathfrak{h}$, and $\mathfrak{n}_+$ are, respectively, the subalgebras of low-triangular, diagonal, and upper-triangular matrices in $\mathfrak{gl}(N)$. Definition 3.19. The Harish–Chandra projection is the linear projection onto the second summand in (9), Theorem 3.20 (Harish–Chandra isomorphism; see [54]). The restriction of the Harish–Chandra projection to the centre $ZU\mathfrak{gl}(N)$ is an injective homomorphism of commutative algebras, and its isomorphic image consists of symmetric functions in the shifted matrix units $x_i=E_{ii}+N-i$, $i=1,\dots,N$. The isomorphism in the theorem enables one to identify the codomain $\mathbb{C}[C_1,C_2,\dots,C_N]$ of the weight system $w_{\mathfrak{gl}(N)}$ with the ring of symmetric functions in the generators $x_1,\dots,x_N$. The images of the generators $C_k$ under this isomorphism admit the following explicit expression:
$$
\begin{equation*}
1-Nu-\sum_{k=1}^\infty\phi(C_k)u^{k+1}= \prod_{i=1}^N\frac{1-(x_i+1)u}{1-x_iu}\,.
\end{equation*}
\notag
$$
The computation of the values of the $\mathfrak{gl}(N)$-weight system at a given chord diagram by means of the Harish–Chandra isomorphism consists in applying the projection $\phi$ to each monomial in the definition of the weight system in turn and finding its contribution to the final value. The total contribution is obtained by summing elements of a commutative ring. As a result, one can considerably reduce the required amount of random-access memory. Nevertheless, the running time grows rather rapidly with $N$, since the number of the monomials involved in the definition, which is $N^{2n}$ for a chord diagram with $n$ chords, also grows. Note also that the Harish–Chandra projection can be applied to the computation of the $w_{\mathfrak{gl}(N)}$-weight system for fixed $N$, and it does not reveal the universal (polynomial) dependence of the values of this system on $N$. 3.5. The $\mathfrak{sl}(N)$-weight systemThe Lie algebra $\mathfrak{gl}(N)$ is not simple; it can be represented as the direct sum of the simple Lie algebra $\mathfrak{sl}(N)$ and a one-dimensional Abelian Lie algebra. Therefore, the centre of the universal enveloping algebra $\mathfrak{gl}(N)$ is the tensor product of the centres of the universal enveloping algebras of $\mathfrak{sl}(N)$ and $\mathbb{C}$, so that it can be identified with the ring of polynomials in $C_1$ with coefficients in $ZU\mathfrak{sl}(N)$ Therefore, the values of the weight system $w_{\mathfrak{sl}(N)}$ can be obtained from those of $w_{\mathfrak{gl}(N)}$ by setting $C_1=0$ and $C_k=\widetilde C_k$, $k\geqslant2$, where $\widetilde C_k$ is the projection of the corresponding Casimir element in $ZU\mathfrak{gl}(N)$ onto $ZU\mathfrak{sl}(N)$ The result of this substitution is a polynomial in $\widetilde C_2,\widetilde C_3,\dots$ . More explicitly, set
$$
\begin{equation*}
\widetilde E_{ij}=E_{ij}-\delta_{ij}N^{-1}C_1\in \mathfrak{sl}(N)\subset\mathfrak{gl}(N).
\end{equation*}
\notag
$$
Then
$$
\begin{equation*}
\widetilde C_{k}=\sum_{i_1,i_2,\dots,i_k=1}^N\widetilde E_{i_1i_2} \widetilde E_{i_2i_3}\cdots \widetilde E_{i_k i_1}= \sum_{i=0}^k\begin{pmatrix} k \\ i\end{pmatrix}(-1)^iC_{k-i} \biggl(\frac{C_1}{N}\biggr)^i,
\end{equation*}
\notag
$$
where we set $C_0=N$ and
$$
\begin{equation*}
ZU\mathfrak{sl}(N)=\mathbb{C}[\widetilde C_2,\dots,\widetilde C_N]\subset ZU\mathfrak{gl}(N)=\mathbb{C}[C_1,\dots,C_N].
\end{equation*}
\notag
$$
Alternatively, the weight system $w_{\mathfrak{sl}(N)}$ can be computed by extending it to the permutations by means of recurrence relations similar to those in the case of $\mathfrak{gl}(N)$: just replace there $w_{\mathfrak{gl}(N)}$ by $w_{\mathfrak{sl}(N)}$ and the $C_k$ by the $\widetilde C_k$ and set $\widetilde C_1=0$. Similarly to the $w_{\mathfrak{gl}}$-weight system, the result is a universal polynomial in $N,\widetilde C_2,\widetilde C_3,\dots$, which we denote by $w_{\mathfrak{sl}}$. Since there are fewer generators, the computation of $w_{\mathfrak{sl}(N)}$ is more efficient, and the answer is more compact. For example, for the chord diagrams $K_n$ we obtain
$$
\begin{equation*}
\begin{aligned} \, w_{\mathfrak{sl}}(K_2)&=\widetilde C_2^2-\widetilde C_2 N, \\ w_{\mathfrak{sl}}(K_3)&=\widetilde C_2^3-3 \widetilde C_2^2 N+ 2 \widetilde C_2 N^2, \\ w_{\mathfrak{sl}}(K_4)&=\widetilde C_2^4+6 \widetilde C_2^2- 2 (3 \widetilde C_2^3+\widetilde C_2-\widetilde C_4) N+ (11 \widetilde C_2^2-2 \widetilde C_3) N^2-6 \widetilde C_2 N^3, \\ w_{\mathfrak{sl}}(K_5)&=\widetilde C_2^5+30 \widetilde C_2^3- 2 (5 \widetilde C_2^4+41 \widetilde C_2^2-5 \widetilde C_4 \widetilde C_2) N \\ &\qquad+(35 \widetilde C_2^3-10 \widetilde C_3 \widetilde C_2+ 32 \widetilde C_2-24 \widetilde C_4) N^2 \\ &\qquad-2 (25 \widetilde C_2^2-12 \widetilde C_3) N^3+24 \widetilde C_2 N^4, \\ w_{\mathfrak{sl}}(K_6)&=\widetilde C_2^6+90 \widetilde C_2^4+ 264 \widetilde C_2^2-240 \widetilde C_4 \widetilde C_2+ 160 \widetilde C_3^2 \\ &\qquad+(-15 \widetilde C_2^5-552 \widetilde C_2^3+ 30 \widetilde C_4 \widetilde C_2^2+64 \widetilde C_3 \widetilde C_2- 72 \widetilde C_2+88 \widetilde C_4-16 \widetilde C_6) N \\ &\qquad+(85 \widetilde C_2^4-30 \widetilde C_3 \widetilde C_2^2+ 1014 \widetilde C_2^2-174 \widetilde C_4 \widetilde C_2- 88 \widetilde C_3+32 \widetilde C_5) N^2 \\ &\qquad+(-225 \widetilde C_2^3+174 \widetilde C_3 \widetilde C_2- 416 \widetilde C_2+224 \widetilde C_4) N^3 \\ &\qquad+2 (137 \widetilde C_2^2-120 \widetilde C_3) N^4- 120 \widetilde C_2 N^5, \\ w_{\mathfrak{sl}}(K_7)&=\widetilde C_2^7+210 \widetilde C_2^5+ 3192 \widetilde C_2^3-1680 \widetilde C_4 \widetilde C_2^2+ 1120 \widetilde C_3^2 \widetilde C_2 \\ &\qquad+(-21 \widetilde C_2^6-2212 \widetilde C_2^4+ 70 \widetilde C_4 \widetilde C_2^3+448 \widetilde C_3 \widetilde C_2^2 \\ &\qquad\qquad\qquad\;\;-10680 \widetilde C_2^2+7432 \widetilde C_4 \widetilde C_2- 112 \widetilde C_6 \widetilde C_2-4096 \widetilde C_3^2) N \\ &\qquad+(175 \widetilde C_2^5-70 \widetilde C_3 \widetilde C_2^3+ 8358 \widetilde C_2^3-714 \widetilde C_4 \widetilde C_2^2 \\ &\qquad\qquad\qquad\;\;-2792 \widetilde C_3 \widetilde C_2+224 \widetilde C_5 \widetilde C_2+ 3456 \widetilde C_2-3392 \widetilde C_4+544 \widetilde C_6) N^2 \\ &\qquad+(-735 \widetilde C_2^4+714 \widetilde C_3 \widetilde C_2^2- 12892 \widetilde C_2^2 \\ &\qquad\qquad\qquad\;\;+2212 \widetilde C_4 \widetilde C_2+3392 \widetilde C_3- 1088 \widetilde C_5) N^3 \\ &\qquad+4 (406 \widetilde C_2^3-581 \widetilde C_3 \widetilde C_2+ 1316 \widetilde C_2-464 \widetilde C_4) N^4 \\ &\qquad-12 (147 \widetilde C_2^2-200 \widetilde C_3) N^5+ 720 \widetilde C_2 N^6. \end{aligned}
\end{equation*}
\notag
$$
The values of the weight system $w_{\mathfrak{gl}}$ can be recovered from those of $w_{\mathfrak{sl}}$ by using the Hopf algebra structure of the space of chord diagrams. Namely, for any primitive element $P$ of degree greater than one, in the algebra of chord diagrams we have $w_{\mathfrak{gl}(N)}(P)=w_{\mathfrak{sl}(N)}(P)\in ZU\mathfrak{sl}(n)$, that is, $w_{\mathfrak{gl}(N)}(P)$ can be expressed as a polynomial in $\widetilde C_2,\widetilde C_3,\dots$ . For $P=K_1$ we have
$$
\begin{equation*}
w_{\mathfrak{gl}(N)}(K_1)=C_2=\widetilde C_2+\frac{C_1^2}{N}= w_{\mathfrak{sl}(N)}(K_1)+\frac{C_1^2}{N}\,.
\end{equation*}
\notag
$$
This enables us to recover the values of $w_{\mathfrak{gl}}$ from the known values of $w_{\mathfrak{sl}}$ by representing a given chord diagram as a polynomial in primitive elements. More explicitly, given a chord diagram $C$, we have
$$
\begin{equation*}
w_{\mathfrak{gl}}(C)=\sum_{I\sqcup J=V(C)} \biggl(\frac{C_1^2}{N}\biggr)^{|I|} w_{\mathfrak{sl}}(C|_J).
\end{equation*}
\notag
$$
In particular, the exponential generating functions of the values of $w_{\mathfrak{gl}}$ and $w_{\mathfrak{sl}}$ at the chord diagrams $K_n$ satisfy the relation
$$
\begin{equation*}
1+\sum_{n=1}^\infty w_{\mathfrak{gl}}(K_n)\frac{x^n}{n!}= e^{C_1^2/N}\biggl(1+\sum_{n=1}^\infty w_{\mathfrak{sl}}(K_n) \frac{x^n}{n!}\biggr).
\end{equation*}
\notag
$$
3.6. The $\mathfrak{gl}(1|1)$-weight systemIn addition to metrized Lie algebras, weight systems can be constructed from metrized Lie superalgebras. Such a weight system takes values in the centre of the universal enveloping algebra of the corresponding Lie superalgebra. The general construction of such a weight system is very similar to that for Lie algebras, and we do not present it here. Similarly to the case of a Lie algebra, for a more or less complicated Lie superalgebra the computation of its values is rather laborious. In [29] this construction was elaborated for the simplest Lie superalgebra $\mathfrak{gl}(1|1)$. The corresponding weight system $w_{\mathfrak{gl}(1|1)}$ takes values in the ring of polynomials in two variables, the subring of the centre $ZU\mathfrak{gl}(1|1)$ of the universal enveloping algebra that is generated by the Casimir elements of grading $1$ and $2$. In [29] recurrence relations for the values of this weight system, which are similar to the Chmutov–Varchenko relations for $w_{\mathfrak{sl}(2)}$, were deduced. It was proved in [19] that the value of this weight system only depends on the intersection graph of the chord diagram. The skew characteristic polynomial of graphs (see § 1.3.5) is nothing but the extension of the weight system $w_{\mathfrak{gl}(1|1)}$ to a $4$-invariant of graphs. In its turn the weight system $w_{\mathfrak{gl}(m|n)}$ (for arbitrary $m$ and $n$) was defined for permutations in [64], where recurrence relations for its values were also derived. In particular, it was proved that that $w_{\mathfrak{gl}(m|n)}$ is the specialization of the universal weight system $w_\mathfrak{gl}$ with regard to the substitution $N=m-n$ and the replacement of the Casimir elements $C_1,C_2,\dots$ in $U\mathfrak{gl}(N)$ by their counterparts in $U\mathfrak{gl}(m|n)$. 4. Embedded graphs and delta-matroidsA chord diagram can be treated as an embedded graph with a single vertex on an orientable surface. One of the key problems in the theory of weight systems is how one can extend a given weight system to the embedded graphs with arbitrarily many vertices. Such generalized weight systems are associated with finite-type invariants of links in the same way as ordinary weight systems are associated with finite-type invariants of knots. There are various approaches to extending weight systems and graph invariants to embedded graphs. The best developed approach consists in interpreting an embedded graph as an ordinary graph to which some information about the embedding is added (see [27], for example). Various extensions of the classical Tutte polynomial have been constructed in this way [8], [28]. In this section we describe another approach to constructing extensions, which has been under development in the last few years. This approach is based on the analysis of the Hopf algebra structure on the space of delta-matroids. It leads to invariants satisfying $4$-term relations and thus being generalized weight systems. Delta-matroids (also known under the name of Lagrangian matroids) were introduced by Bouchét [9], [11] around 1990. These combinatorial structures spot equally well the essential features of both abstract and embedded graphs. A thorough description of the connections between embedded graphs and delta-matroids can be found in [21] and [22]. Hopf algebra structures on various spaces of delta-matroids and $4$-term relations for them were introduced in [45]. 4.1. Embedded graphs and $4$-term relationsEmbedded graphs, also known under the name of ribbon graphs, are the subject of topological graph theory. An orientable embedded graph can be defined as an abstract graph (perhaps with loops and multiple edges) endowed with a cyclic order on the half-edges incident to each vertex. We consider below only orientable connected embedded graphs. Such a graph admits a presentation as an orientable surface with boundary formed by the discs associated with vertices and the ribbons associated with edges; each ribbon is attached to one or two discs on its shorter sides (see Fig. 19). With each chord diagram one can associate a ribbon graph with a single vertex by transforming the Wilson loop into the vertex by attaching a disc to it and replacing each chord by a ribbon in such a way that the surface remains orientable. The $4$-term relations (1) can be interpreted as valid for an arbitrary embedded graph, not necessarily a single-vertex one. In this more general case the ends of the two edges taking part in a relation can be attached to the boundaries of different vertices (two or even three). We call these relations generalized $4$-term relations, and we call invariants of embedded graphs satisfying them generalized weight systems. Vassiliev’s first move for embedded graphs interchanges the two neighbouring ends of two ribbons, and the second Vassiliev move consists in sliding an end of a ribbon (a handle) along another ribbon. Below we will be interested first of all in the question of how one can extend a weight system to a generalized weight system. The weight systems we are going to construct is based on the Hopf algebra structure on the space of delta-matroids. 4.2. Delta-matroids of graphs and embedded graphs, and $4$-term relations for themA set system is a pair $(E;S)$ consisting of a finite set $E$ and a subset $S\subset 2^E$ of the set of its subsets. A set system $(E;S)$ is said to be proper if $S$ is non-empty; we consider only proper set systems below. Definition 4.1. A proper set system $(E;S)$ is called a delta-matroid if the following symmetric exchange axiom is valid for it: Here $\Delta$ denotes the symmetric set difference: $X\mathbin{\Delta} Y=(X\setminus Y)\cup(Y\setminus X)$. The element $b$ in the symmetric exchange axiom can either coincide with $a$ or be different from it. Elements of $S$ are called admissible sets for the delta-matroid $(E;S)$. With each simple graph $G$ and any embedded graph $\Gamma$ we can associate a delta- matroid. For a graph, the construction is as follows. Recall that a graph $G$ is said to be non-degenerate if the determinant of its adjacency matrix over the two-element field $\mathbb{F}_2$ is $1$. The delta-matroid $\delta(G)=(V(G);S(G))$ of a graph $G$ is the set system consisting of the vertex set $V(G)$ of $G$ and a set $S(G)\subset 2^{V(G)}$ of its subsets, where a subset $U\subset V(G)$ of the vertex set of the graph is admissible (that is, $U\in S(G)$) if and only if the induced subgraph $G\big|_U$ is non-degenerate. In turn, the delta-matroid $\delta(\Gamma)=(E(\Gamma);S(\Gamma))$ of an embedded graph $\Gamma$ is the system of sets consisting of the edge set $E(\Gamma)$ of $\Gamma$ and a set $S(\Gamma)\subset 2^{E(\Gamma)}$ of its subsets, where a subset $U\subset E(\Gamma)$ of the edge set is admissible (that is, $U\in S(\Gamma)$) if and only if the spanning embedded subgraph $\Gamma\big|_U$ has a connected boundary. If an embedded graph $\Gamma$ has genus $0$ (that is, this graph is embedded into the sphere), then a set of edges of $\Gamma$ is admissible if and only if the corresponding spanning subgraph $\Gamma\big|_U$ is a tree. For an arbitrary genus, admisssible subsets of the delta-matroid $\delta(\Gamma)$ are also called quasitrees. Bouchét proved that the set systems $\delta(G)$ and $\delta(\Gamma)$ are indeed delta-matroids. In addition, if $\Gamma$ is an embedded graph with a single vertex, that is, a chord diagram, then the corresponding definitions are compatible. Theorem 4.2. If $C$ is a chord diagram, that is, an embedded graph with a single vertex, then the delta-matroid $\delta(C)$ is naturally isomorphic to the delta-matroid $\delta(g(C))$ of the intersection graph of $C$. In other words, the boundary of a chord diagram $C$ is connected if and only if its intersection graph is non-degenerate. The last assertion has been rediscovered many times (see [59], for instance). The delta-matroid of a graph, as well as the delta-matroid of an orientable embedded graph, is even. A delta-matroid $(E;S)$ is said to be even if the cardinalities of all admissible sets in it have the same parity: $|X|\equiv|Y|\!\!\mod 2$ for all $X,Y\in S$. Since we are first of all interested in graphs embedded into orientable surfaces, we speak below only about even delta-matroids, although most constructions can also be extended to delta-matroids that are not even (see § 4.5). We introduce the twist (or partial dual) of a delta-matroid in the following way. Let $U\subset E$ be a subset of the base set $E$ of a delta-matroid $D=(E;S)$. The twist $D*U$ of $D$ in the subset $U$ is the system of sets $D*U=(E;S*U)$, where $S*U=\{X\mathbin{\Delta} U\colon X\in S\}$. For delta-matroids of embedded graphs the twist operation corresponds to partial duality introduced in [15]. The twist of a delta-matroid in an arbitrary subset of its base set is a delta-matroid [11]. Definition 4.3. The delta-matroid $\delta(G)$ of a graph $G$ is said to be graphic. The twist of a graphic delta-matroid in a subset of its base set is called a binary delta-matroid. In particular, the delta-matroid $\delta(\Gamma)$ of any embedded graph $\Gamma$ on an orientable surface is even and binary. For delta-matroids a $4$-term relation is defined. Its definition requires defining two operations on delta-matroids, namely, the first and second Vassiliev moves. Each of these operations is specified by a chosen ordered pair of elements of the delta-matroid. The result $\widetilde{D_{ab}}$ of sliding the handle $a$ along the handle $b$ (see [48]) in a delta- matroid $D=(E;S)$, $a,b\in E$, is defined by $\widetilde{D_{ab}}=(E;\widetilde{S_{ab}})$, where
$$
\begin{equation*}
\widetilde{S_{ab}}=S\mathbin{\Delta}\{X \sqcup a\colon X \sqcup b \in S \text{ and } X \subseteq E \setminus \{a,b\}\}.
\end{equation*}
\notag
$$
The result ${D'_{ab}}$ of the interchange of the ends of the handles $a$ and $b$ in a delta- matroid $D=(E;S)$, $a,b\in E$, is defined by ${D'_{ab}}=(E;{S'_{ab}})$, where
$$
\begin{equation*}
{S'_{ab}}=S\mathbin{\Delta}\{X \sqcup \{a,b\}\colon X \in S \text{ and } X \subseteq E \setminus \{a,b\}\}.
\end{equation*}
\notag
$$
Both the first and second Vassiliev moves take a binary delta-matroid to a delta- matroid of the same type. A function $f$ on the even binary delta-matroids satisfies the $4$-term relations if for any such delta-matroid $D=(E;S)$ and any pair $a,b\in E$ of elements of the base set we have
$$
\begin{equation*}
f(D)-f(D'_{ab})=f(\widetilde{D_{ab}})-f(\widetilde{D'_{ab}}).
\end{equation*}
\notag
$$
If a function on the even binary delta-matroids satisfies the $4$-term relations, then its restriction to the delta-matroids of embedded graphs on orientable surfaces satisfies the generalized $4$-term relations for them. 4.3. The Hopf algebras of delta-matroidsTwo set systems $(E_1;S_1)$ and $(E_2;S_2)$ are said to be isomorphic if there is a one-to-one map of $E_1$ to $E_2$ that takes the set of subsets $S_1$ one-to-one to the set of subsets $S_2$. Denote by $\mathcal{B}^e_n$ the vector space spanned by the isomorphism classes of even binary delta-matroids on $n$-element sets and set
$$
\begin{equation*}
\mathcal{B}^e=\mathcal{B}^e_0\oplus\mathcal{B}^e_1\oplus \mathcal{B}^e_2\oplus\cdots\,.
\end{equation*}
\notag
$$
The vector space $\mathcal{B}^e$ can be endowed with the natural structure of a graded commutative cocommutative Hopf algebra. In this algebra multiplication is given by the disjoint union, while comultiplication is given by partitioning the base set of a delta-matroid into two disjoint subsets in all possible ways. A delta-matroid is said to be connected if it cannot be represented as a product of two delta-matroids with smaller base sets. The quotient of the vector space $\mathcal{B}^e$ modulo the subspace of $4$-term relations inherits a Hopf algebra structure. We are not going to use this Hopf algebra, and do not introduce any notation for it. Remark. In contrast to the graphs and delta-matroids, the embedded graphs do not generate a natural Hopf algebra as far as we know. 4.4. Extending graph invariants to embedded graphs and delta-matroidsIn this section we explain how one can extend the $4$-invariants of graphs described in § 2 to the embedded graphs. The extensions obtained happen to be defined on the binary delta-matroids; their definition uses the Hopf algebra structure on the vector space of binary delta-matroids. 4.4.1. The interlace polynomialThe interlace polynomial of a graph, which we defined above, admits a natural extension to binary delta-matroids. Definition 4.4. The distance of a set system $D=(E;S)$ to a subset $U\subset E$ is the number The interlace polynomial $L_D(x)$ of a delta-matroid $D=(E;S)$ is the polynomial (see [49]).Theorem 4.5. If $D=D(G)$ is the delta-matroid of a graph $G$, then the interlace polynomial $L_D$ of $D$ is related to the interlace polynomial of $G$ in the following way: Theorem 4.6 (see [38]). The interlace polynomials of even binary delta-matroids satisfy the $4$-term relations for these matroids. Theorem 4.7. The space of values of the interlace polynomial on the subspace of primitive elements of $\mathcal{B}^e_n$ has dimension $n$. This implies that the dimension of the space of primitive elements in $\mathcal{B}^e_n$ is at least $n$. 4.4.2. Stanley’s symmetrized chromatic polynomialThe notion of the umbral invariant of graphs admits a natural extension to invariants of delta-matroids. To define such an invariant, it suffices to specify, for each connected delta-matroid $D=(E;S)$, the coefficient of $q_n$ in the value of the umbral invariant of this delta-matroid, where $n=|E|$. A way to extend umbral graph invariants to umbral invariants of delta-matroids was proposed in [50]. It is based on the combinatorial Hopf algebra structure introduced in [2]. Below we restrict ourselves to commutative cocommutative combinatorial Hopf algebras. A combinatorial Hopf algebra is a pair $(\mathcal{H},\xi)$ consisting of a connected graded Hopf algebra $\mathcal{H}$ and a character (that is, a multiplicative map) $\xi\colon \mathcal{H}\to\mathbb{C}$. The polynomial Hopf algebra $\mathbb{C}[q_1,q_2,\dots]$ becomes a combinatorial Hopf algebra if we endow it with the canonical character $\zeta$ that takes each variable $q_k$ to $1$. This combinatorial Hopf algebra is a terminal object in the category of combinatorial Hopf algebras, that is, with each combinatorial Hopf algebra $(\mathcal{H},\xi)$ a unique umbral invariant (a graded Hopf algebra homomorphism) $\mathcal{H}\to\mathbb{C}[q_1,q_2,\dots]$ taking $\xi$ to $\zeta$ is associated. It was proved in [2] that Stanley’s symmetrized chromatic polynomial is the graded Hopf algebra homomorphism $\mathcal{G}\to\mathbb{C}[q_1,q_2,\dots]$ corresponding to the character $\xi\colon \mathcal{G}\to\mathbb{C}$ that takes the graph with a single vertex to $1$ and each connected graph with $n\geqslant2$ vertices to $0$. This structure makes it possible to define [50] Stanley’s symmetrized chromatic polynomial of delta-matroids as the graded homomorphism $W\colon \mathcal{B}^e\to\mathbb{C}[x;q_1,q_2,\dots]$ from the Hopf algebra of even binary delta-matroids to the Hopf algebra of polynomials in the variables $q$ with coefficients in the ring of polynomials in the variable $x$ that is associated with the character taking the delta-matroid $(\{1\};\{\varnothing\})$ to $1$, the delta-matroid $(\{1\};\{\{1\}\})$ to $x$, and each connected delta-matroid of grading $n\geqslant2$ to $0$. These two delta-matroids on a $1$-element set span the homogeneous subspace $\mathcal{B}^e_1$. Theorem 4.8. Stanley’s symmetrized chromatic polynomial of delta-matroids satisfies the $4$-term relations for delta-matroids. 4.4.3. The transition polynomialThe transition polynomial also admits an extension to the delta-matroids which satisfies the $4$-term relations for them. In order to define the transition polynomial we need a few further definitions. Let $D=(E;S)$ be a delta-matroid, and let $U\subset E$ be a subset of its base set. The polynomial
$$
\begin{equation*}
Q_D(s,t,x)=\sum_{E=\Phi\sqcup X\sqcup\Psi} s^{|\Phi|}t^{|X|}x^{d_{D+\Phi*X\overline*\Psi}(\varnothing)}
\end{equation*}
\notag
$$
is called the transition polynomial of the delta-matroid $D=(E;S)$. Here for an element $u\in E$ the operation $+$ is defined by
$$
\begin{equation*}
D+u=(E,S\mathbin{\Delta}\{F\cup\{u\}\colon F\in S,\, u\notin F\}).
\end{equation*}
\notag
$$
The operation $\overline*$ is defined by These two operations are extended to an arbitrary subset $A\subset E$. This definition is a specialization of the definition of the weighted transition polynomial in [12]. Theorem 4.9 (see [25]). The transition polynomials of even binary delta-matroids satisfy the $4$-term relations for these delta-matroids. 4.4.4. The skew characteristic polynomialGraph non-degeneracy extends naturally to embedded graphs and delta-matroids. A delta-matroid $(E;S)$ is said to be non-degenerate if $E\in S$, that is, if the whole set $E$ is admissible. For embedded graphs this means that an embedded graph is non-degenerate if and only if its boundary is connected. For chord diagrams this definition is compatible with the one we already know. The non-degeneracy $\nu(D)$ of a delta-matroid is $1$ if $D$ is non-degenerate, and it is $0$ otherwise. We can define the skew characteristic polynomial of a delta-matroid $D=(E;S)$ by
$$
\begin{equation*}
Q_D(x)=\sum_{U\subset E} x^{|U|}\nu\bigl(D\big|_U\bigr).
\end{equation*}
\notag
$$
Similarly to the case of graphs, this statement follows from the fact that the second Vassiliev move preserves non-degeneracy. 4.5. Extending to non-orientable surfaces: framed chord diagrams, framed graphs, and not necessarily even delta-matroidsThe 4-term relations for chord diagrams, graphs, and embedded graphs have a non-orientable version, which we describe here briefly. It should not be separated from the orientable version: all constructions and, first of all, Hopf algebra structures require the simultaneous participation of both orientable and non-orientable objects. In each case the orientable objects generate Hopf subalgebras of the Hopf algebras of objects with no restrictions on their orientability. A framed chord diagram is a pair $(C,\varphi)$ consisting of a chord diagram $C$ and a framing $\varphi\colon V(C)\to\mathbb{F}_2$ taking each chord of $C$ to an element of the field $\mathbb{F}_2$. An isomorphism of framed chord diagrams is an isomorphism of the underlying chord diagrams which take the framing of the first diagram to that of the second. A framed graph is a pair $(G,\varphi)$ consisting of a simple graph $G$ and a framing $\varphi\colon V(G)\to\mathbb{F}_2$ that associates with any vertex of $G$ an element of the field $\mathbb{F}_2$. An isomorphism of framed graphs is an isomorphism of the underlying graphs which take the framing of the first graph to that of the second. Numbering the vertices of $G$ by the integers $1,\dots,n=|V(G)|$ one associates with a framed graph its adjacency matrix $A(G,\varphi)$. Non-diagonal elements of this matrix coincide with those of the adjacency matrix $A(G)$ of the simple graph $G$, and its diagonal elements coincide with the framings of the corresponding vertices. Isomorphism classes of framed graphs coincide with symmetric matrices over $\mathbb{F}_2$ considered up to renumbering their columns and rows simultaneously. There is a framed graph associated with any framed chord diagram, namely, its intersection graph. A framed chord diagram can be considered as a ribbon graph with a single vertex: an ordinary ribbon is associated with a chord with framing $0$, while a chord with framing $1$ is replaced by a half-twisted ribbon. If there is a chord with framing $1$, then the surface corresponding to the framed chord diagram is non-orientable. Framed chord diagrams, framed graphs, and framed weight systems were introduced and investigated in [44]. (A function $f$ on the framed chord diagrams taking values in a commutative ring is called a framed weight system if it satisfies a framed $4$-term relation.) A framed graph invariant $f$ is called a $4$-invariant if for any pair of vertices $a,b\in V(G)$ it satisfies the $4$-term relation
$$
\begin{equation*}
f((G,\varphi))-f((G'_{ab},\varphi))= f((\widetilde{G}_{ab},\widetilde{\varphi}_{ab}))- f((\widetilde{G}'_{ab},\widetilde{\varphi}_{ab})).
\end{equation*}
\notag
$$
There is a natural one-to-one correspondence between the vertex sets of any two graphs participating in this relation, and therefore $\varphi$ and $\widetilde\varphi_{ab}$ have a common domain of definition. Here $\widetilde{\varphi}_{ab}$ denotes the framing of the graph $\widetilde{G}_{ab}$ that coincides with $\varphi$ at all vertices but $a$, while $\widetilde{\varphi}_{ab}(a)=\varphi(a)+\varphi(b)$. In other words, the adjacency matrix $A(\widetilde{G}_{ab})$ of the framed graph $\widetilde{G}_{ab}$ can be obtained from $A(G)$ by means of the same transformation (5) as in the unframed case. The non-degeneracy and the skew characteristic polynomial are defined for framed graphs in the same way as for ordinary graphs. The non-degenracy of a graph is preserved by the second Vassiliev move. This implies that the skew characteristic polynomial is a $4$-invariant of framed graphs. In contrast to the skew characteristic polynomial of simple graphs, the skew characteristic polynomial of a framed graph may be neither even, nor odd. Any $4$-invariant of framed graphs defines a framed weight system, which takes a framed chord diagram to the value of the invariant at its framed intersection graph. In particular, both the non-degeneracy and the skew characteristic polynomial define framed weight systems. The delta-matroid of a framed graph and the delta-matroid of an arbitrary, maybe non-orientable, embedded graph are defined in the same way as in the orientable case. If a framed graph has a vertex with framing $1$, then the corresponding delta-matroid is not even: there are admissible sets containing an even and an odd number of elements alike. The delta-matroid of an embedded graph on a non-orientable surface is not even either. The isomorphism classes of binary delta-matroids generate a Hopf algebra containing the Hopf subalgebra $\mathcal{B}^e$.
Citation in format AMSBIB
\Bibitem{KazLan22} |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Contact us: |
Terms of Use
|
Registration to the website |
Logotypes |
|