\documentclass[12pt]{article}

\addtolength{\oddsidemargin}{-10mm}
\addtolength{\evensidemargin}{-10mm}
\addtolength{\textwidth}{25mm}
\addtolength{\textheight}{30mm}
\addtolength{\topmargin}{-10mm}

\def\G{\Gamma}
\def\g{\gamma}
\def\tG{\widetilde\Gamma}

\def\cG{{\cal G}}
\def\cF{{\cal F}}
\def\cT{{\cal T}}
\def\cP{{\cal P}}
\def\cD{{\cal D}}
\def\cW{{\cal W}}
\def\cB{{\cal B}}

\def\Z{{\bf Z}}
\def\C{{\bf C}}
\def\R{{\bf R}}

\def\mod{{\rm mod}}
\def\Hom{{\rm Hom}}
\def\sl{{\rm sl}}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{problem}{Problem}

 \author{Sergei~K.~Lando\footnote{Partly supported by the
Russian Foundation for Basic Research under Grant No.~01-98-00555.}}
\title{On a Hopf algebra in graph theory}
%\date{January 27, 1998}
\date{}
\pagestyle{myheadings}

\begin{document}

%\markboth{\hspace{1em}On a Hopf algebra in graph theory}{}
%%%%
      \makeatletter
%%%%  ^^^^^^^^^^^^^
\let\@mkboth\markboth
 \def\@oddfoot{}\def\@evenfoot{}%
  \def\@@evenhead{\hbox to \textwidth{\rm \thepage\hfil
\sl \leftmark\strut}}%        Left heading without rule...
  \def\@evenhead{\vtop to \headheight  {\@@evenhead\hrule\vss}} % and with rule
  \def\@@oddhead{\hbox to\textwidth{{ \rightmark}\hfil
\rm\thepage\strut}}% Ditto for right heading.
  \def\@oddhead{\vtop to \headheight   {\@@oddhead\hrule\vss}}
  \def\chaptermark#1{\markboth {\uppercase{%
   \@chapapp\ \thechapter.\hskip.5em\relax #1}}{}}%
  \def\sectionmark#1{\markright{\uppercase {%
%  \thechapter.\arabic{section}.\hskip
  On a Hopf algebra in graph theory %.5em%\relax #1
}}}
%%%%%
      \makeatother
%%%%% ^^^^^^^^^^^^

\markboth{\hspace{1em}On a Hopf algebra in graph theory}{}

\maketitle


\begin{center}
%{\it Sergei K. Lando}\\
Higher College of Mathematics,
Independent University of Moscow\\
11 Bol. Vlassievskii per.,
121002 Moscow Russia\\
{\bf e-mail}: lando@mccme.ru\\

and\\


Institute for System Research,
Russian Academy of Sciences
\end{center}

%\newpage



%\begin{center}
%
%On a Hopf Algebra in Graph Theory \\
%Sergei K. Lando\\
%Higher College of Mathematics,
%Independent University of Moscow\\
%11 Bol. Vlassievskii per.,
%121002 Moscow Russia\\
%{\bf e-mail}: lando@mccme.ru\\
%\end{center}
%
%\newpage

{\sc Abstract.} We introduce and start the study of a bialgebra of graphs,
which we call the {\it 4-bialgebra}, and of the dual {\it
bialgebra of 4-invariants}. The 4-bialgebra is
similar to the ring of graphs introduced by W.~T.~Tutte in~1946,
but its structure is more complicated.  The roots of the
definition are in low dimensional topology, namely, in
the recent theory of Vassiliev knot invariants.
In particular, 4-invariants of graphs determine
Vassiliev invariants of knots. The relation between the
two notions is discussed.


%\newpage


\section{Introduction}
In paper~\cite{T} W.~T.~Tutte introduced a ring
of graphs. The underlying module of this ring is spanned
over $\Z$ by finite graphs modulo the following relation:
\begin{equation}\label{e11}
\G-\G_e'-\G_e''=0,
\end{equation}
which we call the {\it Tutte relation}. Here $\G$ is a graph,
$e$ is a link, i.e., an edge in $\G$, which is not a loop,
the graph $\G_e'$
is obtained from $\G$ by deletion of the edge $e$,
and the graph $\G_e''$ is the result of contraction
of $e$. Of course,
Eq.~(\ref{e11}) is in fact a huge set of relations, one
for each pair (a graph, an edge in the graph).
The multiplication in the ring is induced by the disjoint
union of graphs.


By the time Tutte wrote his paper, a number of interesting
graph invariants was known satisfying the property
\begin{equation}\label{e12}
f(\G)=f(\G_e')+f(\G_e'').
\end{equation}
Tutte called such invariants $W$-functions, and they are
precisely the linear functions on his module.
Below, we call Tutte's $W$-functions {\it Tutte invariants}.
The {\it graph
complexity}, i.e., the number of spanning trees in
the graph, is an example of a Tutte invariant.

He also introduced $V$-functions, that is
$W$-functions satisfying the additional multiplicativity
requirement
\begin{equation}\label{e13}
f(\G_1\cdot\G_2)=f(\G_1)f(\G_2)
\end{equation}
for any two graphs $\G_1,\G_2$.
In other words, $V$-functions are ring
homomorphisms.
The chromatic polynomial (taken with the appropriate sign)
is an example of a $V$-function.

Tutte gave a complete description of all $V$-functions, which
is as follows. Eq.~(\ref{e11}) allows one to present each
graph as an equivalent linear combination
of graphs without links (since
both graphs $\G_e'$ and $\G_e''$ have less links
than the graph $\G$). A graph without links
is a disjoint union of graphs consisting of one
vertex and a number of loops, i.e., a product
of such graphs. Hence, one-vertex graphs are multiplicative
generators of the
ring of graphs, and any $V$-function is uniquely
determined by its values on one-vertex graphs with
$0,1,2,\dots$ loops. The main theorem of Tutte states that
a $V$-function can take arbitrary values on
one-vertex graphs with $n$  loops. In other words,
any graph is equivalent to  a unique linear combination
of linkless graphs. One more point of view is that Tutte's ring
is isomorphic to the polynomial ring in infinite number
of variables, $\Z[s_0,s_1,s_2,\dots]$,
where the variable $s_n$ corresponds to the one-vertex graph with
$n$ loops. A $W$-function is uniquely determined by its
values on disjoint unions of one-vertex graphs.

The main goal of the present paper is to introduce and to
start the study of a different,
more rich, ring of graphs.
For convenience, we consider not a ring, but an algebra
over the field $\C$
of complex numbers (although some remarks will be made about
the case of integer coefficients). This algebra carries
an additional structure of a coalgebra, whence it is a
bialgebra (or a Hopf algebra, what is almost the same).
The crucial difference between our algebra and Tutte's ring
is that we use a different equivalence relation, a 4-term
relation, instead of the original Tutte relation~(\ref{e11})
(which contains 3 terms).
That is why we call the resulting bialgebra the 4-bialgebra
of graphs.

The roots of our definition can be found in the low-dimensional
topology, namely, in Vassiliev's theory of knot invariants~\cite{V}.
Vassiliev introduced a class of knot invariants, which is
presumably a complete class of knot invariants, and showed
how these invariants can be computed by means of so-called
chord diagrams. Vassiliev's invariants are, essentially,
functions on chord diagrams satisfying some 4-term relations.
We describe these 4-term relations in Sec.~\ref{s3} below in the form suggested
by Birman and Lin~\cite{BL}.

S.~V.~Duzhin started the study of the intersection graphs of
chord diagrams from the Vassiliev invariants theory
point of view. He noted that the
chromatic polynomial of the intersection graph satisfies the
4-term relation, and that it determines, therefore, a Vassiliev invariant
of knots. This remark led finally to our joint
paper with S.~V.~Chmutov~\cite{CDL3}
(see also the discussion of intersection
graphs in~\cite{BG}). In this paper we
introduced and gave a complete description of
the bialgebra of weighted graphs, which is
very close to Tutte's ring in the following sense:
it has precisely one generator of each order.
However, it was obvious that the intersection graph of a chord
diagram carries much more information than that used in the
weighted bialgebra of graphs. The present paper is
intended to develop a natural answer to the question,
what information about the chord diagram is contained in
its intersection graph.

The paper is organized as follows. In Sec.~\ref{s2} the 4-bialgebra
of graphs is defined and its structure is described. According to the
general structure theorem for bialgebras, it is a polynomial
bialgebra. The only problem about its structure is the number
of generators of each order. Computations
elaborated by E.~Soboleva~\cite{S}
for the first few orders show that this algebra is much more rich than
Tutte's ring (and therefore, the computations themselves
are much more difficult). We also present some examples of 4-invariants
that are not Tutte invariants and give a description of primitive
elements in the 4-bialgebra based on paper~\cite{L2}.
However, very few steps are made in the study of this 4-bialgebra.

Section~\ref{s3} treats the connection between the
4-bialgebra of graphs and the bialgebra of chord diagrams in knot theory.
Section~\ref{s34} contains a number of open problems
concerning the 4-bialgebra.

I am grateful to S.~V.~Chmutov, S.~V.~Duzhin,
Yu.~Vol'vovskii, and D.~J.~A. Welsh
for valuable discussions, and to E.~Soboleva for calculations.
The paper was written during my stay at the University of Stockholm
in January 1998, and the fruitful atmosphere and hospitality
of the University added a lot to it.


\section{Bialgebra of graphs}\label{s2}
\subsection{4-term relations}\label{s21}
Let $\G$ be a graph. We restrict our consideration with graphs
without loops and multiple edges ({\it strict} graphs).

A {\it graph invariant} is simply a function on
(isomorphism classes of) graphs.
A graph invariant can take values in an arbitrary Abelian group or
in a commutative ring, although it is usually sufficient to keep
in mind either the ring $\Z$ of integers, or the field $\C$ of complex numbers.

Denote by $V(\G)$ the set of vertices of $\G$, and by
$E(\G)$ the set of its edges.
Let us associate with each pair of (distinct) vertices $A,B\in V(\G)$ of a graph
$\G$ two other graphs $\G_{AB}'$ and $\tG_{AB}$.

The graph $\G_{AB}'$ is obtained from $\G$ by erasing the edge $AB\in E(\G)$
in the case this edge exists, and by adding the edge otherwise.
In other words, we simply change the adjacency between the vertices
$A$ and $B$ in $\Gamma$. This operation is the analogue of the edge deletion,
but we prefer to formulate it in a slightly more symmetric way.

The graph $\tG_{AB}$ is obtained from $\G$ in the following way. For any vertex
$C\in V(\G)\setminus\{A,B\}$
we change its adjacency with $A$ if $C$ is joined with $B$,
and we do nothing otherwise. All other edges do not change.
Note that the graph $\tG_{AB}$ depends not only on the pair $(A,B)$,
but on the order of vertices  in the pair as well.

Note also that the operations $\G\mapsto\G_{AB}'$
and $\G\mapsto\tG_{AB}$ commute.

\begin{definition}\rm
A graph invariant is a {\it 4-invariant} if it satisfies the {\it 4-term relation}
\begin{equation}\label{e21}
f(\G)-f(\G_{AB}')=f(\tG_{AB})-f(\tG_{AB}')
\end{equation}
for each graph $\G$ and for any pair $A,B\in V(\G)$ of its vertices.
\end{definition}

In contrast to the Tutte relation,
all four graphs entering Eq.~(\ref{e21}) have the same number of vertices
(and the sets of their vertices are in a natural one-to-one correspondence).

As an immediate consequence of the definition we obtain the following
statement. Let $\tilde\chi(\G)=(-1)^{\#V(\G)}\chi(\G)$
denote the {\it modified chromatic polynomial} of a graph $\G$,
where $\chi(\G)$ is the usual chromatic polynomial
and $\#V(\G)$ is the number of vertices in $\G$.

\begin{proposition}
The modified chromatic polynomial of a graph is a 4-in\-va\-ri\-ant
(with values in the ring of polynomials in one variable).
\end{proposition}

\noindent
{\bf Proof.} Suppose that $\G$ contains an edge $e=AB\in E(\Gamma)$.
Approve the short notation $\tG=\tG_{AB}$.
For the modified chromatic polynomial we have
$$
\tilde\chi(\G)-\tilde\chi(\G_e')=\tilde\chi(\G_e''),\quad
\tilde\chi(\tG)-\tilde\chi(\tG_e')=\tilde\chi(\tG_e'')
$$
For the chromatic polynomial, the contraction of an edge
requires eliminating of multiple edges in the resulting
graph. After eliminating possible multiple edges we obtain
$\G_e''=\tG_e''$, what is obvious from the definitions.
The proposition is proved.

However, there is a lot of 4-invariants that are not Tutte invariants,
and not each Tutte invariant is a 4-invariant.
Probably the most obvious 4-invariant that is not Tutte
is the number $\#E(\G)$ of edges in
$\G$. The verification of Eq.~(\ref{e21}) is easy. Indeed, the difference
in both sides of  Eq.~(\ref{e21}) is either $1$ or $-1$
for any graph and any pair of its vertices.
Other examples of 4-invariants will be
presented later in this section.


\subsection{Bialgebra structure}\label{s22}

Consider the (infinite dimensional) vector
space over $\C$ spanned by all graphs as free generators.
In his original paper~\cite{T} Tutte suggested to treat the disjoint union
of graphs as a multiplication of the generators. This multiplication can
be extended by linearity to linear combinations of graphs making the space into a
commutative algebra. We denote this algebra by $\cG$.
The empty graph plays the role of the unit in this algebra.
The number of graph vertices induces a grading in $\cG$,
$$
\cG=\cG_0\oplus\cG_1\oplus\cG_2\oplus\dots,
$$
where $\cG_k$ is the finite dimensional linear space
freely spanned by graphs with $k$ vertices, $k=0,1,\dots$.
The multiplication $m:\cG\otimes\cG\to\cG$ preserves this grading:
$$
m:\cG_{n_1}\otimes\cG_{n_2}\to\cG_{n_1+n_2}.
$$


A {\it bialgebra} is a linear space endowed with two structures,
that of an algebra and of a coalgebra, which respect each other.
Precise definitions can be found in~\cite{Sw}.
Throughout the paper all bialgebras are supposed to
be associative and coassociative with a unit and a counit.
A bialgebra is a {\it Hopf algebra} if
it is supplied as well with an {\it antipode}, i.e.,
with an automorphism also satisfying
some natural requirements.

Nice examples of bialgebras and Hopf algebras
arising in combinatorics can be found in~\cite{JR}.

Let us define the second operation, the {\it comultiplication}
$\mu:\cG\to\cG\otimes\cG$ as follows.
For a set $V_1\subset V(\G)$ of vertices of a graph $\G$ let us
denote by $G(V_1)$ the induced subgraph of $\G$ with the set
of vertices $V_1$, i.e., $V_1$ is the set of vertices of $G(V_1)$, and
$e\in E(\G)$ is an edge in $G(V_1)$ iff both ends of $e$ belong to $V_1$.
We set
\begin{equation}\label{e24}
\mu(\G)=\sum_{V_1\subseteq V(\G)}G(V_1)\otimes G(V(G)\setminus V_1),
\end{equation}
where the sum is taken over all subsets $V_1$ of the set of vertices $V(\G)$.
There are $2^{V(G)}$ summands in the right hand side of the previous equation.
The comultiplication is extended to linear combinations of graphs by
linearity.

Figure~\ref{f21} demonstrates an example of a comultiplication.

\begin{figure}[t]
\begin{center}
\begin{picture}(300,60)(10,60)
%The first row
\put(18,97){$\mu($}
\put(30,100){\circle*{4}}
\put(30,100){\line(1,0){25}}
\put(55,100){\circle*{4}}
\put(55,100){\line(1,0){25}}
\put(80,100){\circle*{4}}
\put(83,97){$)$}
\put(90,97){$=\ 1\otimes$}
\put(125,100){\circle*{4}}
\put(125,100){\line(1,0){25}}
\put(150,100){\circle*{4}}
\put(150,100){\line(1,0){25}}
\put(175,100){\circle*{4}}
\put(180,97){$+\ 2$}
\put(205,100){\circle*{4}}
\put(212,97){$\otimes$}
\put(225,100){\circle*{4}}
\put(225,100){\line(1,0){25}}
\put(250,100){\circle*{4}}
\put(260,97){$+$}
\put(275,100){\circle*{4}}
\put(282,97){$\otimes$}
\put(295,100){\circle*{4}}
\put(305,100){\circle*{4}}
%The second row
\put(97,67){$+$}
\put(110,70){\circle*{4}}
\put(120,70){\circle*{4}}
\put(127,67){$\otimes$}
\put(140,70){\circle*{4}}
\put(150,67){$+\ 2$}
\put(175,70){\circle*{4}}
\put(175,70){\line(1,0){25}}
\put(200,70){\circle*{4}}
\put(207,67){$\otimes$}
\put(220,70){\circle*{4}}
\put(230,67){$+$}
\put(245,70){\circle*{4}}
\put(245,70){\line(1,0){25}}
\put(270,70){\circle*{4}}
\put(270,70){\line(1,0){25}}
\put(295,70){\circle*{4}}
\put(302,67){$\otimes\ 1$}

\end{picture}
\caption{Coproduct of a graph}\label{f21}
\end{center}
\end{figure}

The comultiplication, as well as the multiplication, respects
the grading:
$$
\mu:\cG_n\to\cG_0\otimes\cG_n\oplus\cG_1\otimes\cG_{n-1}\oplus\dots
\oplus\cG_n\otimes\cG_0.
$$

\begin{theorem} The multiplication and the comultiplication defined
above make the algebra of graphs into a
commutative cocommutative bialgebra.
\end{theorem}

We omit purely technical verification of the bialgebra axioms.

The bialgebra of graphs is too complicated: it carries the same
information as graphs themselves. It makes sense, therefore,
to look for some reasonable
quotient bialgebra, which is more easy to handle.

Similarly to Tutte relation~(\ref{e11}),
one can consider the quotient space of graphs modulo the 4-term relations,
\begin{equation}\label{e23}
\G-\G_{AB}'-\tG_{AB}+\tG_{AB}'=0
\end{equation}
for all graphs $\G$ and all pairs $A,B$ of their vertices. We denote this space
by $\cF$. This space inherits a bialgebra structure
from the bialgebra of graphs,
and we call it the {\it 4-bialgebra} of graphs. The dual space $\cF^*$
also carries a bialgebra structure, that of the dual bialgebra,
and it will be called the
{\it bialgebra of 4-invariants}.

By a slight abuse of language, below we shall make no difference
between a graph and the equivalence class it represents in $\cF$.


In contrast to the case of Tutte
relations, all terms in the 4-term relation have the same number of vertices.
Therefore,
the number of vertices induces a grading in $\cF$,
$$
\cF=\cF_0\oplus\cF_1\oplus\cF_2\oplus\dots,
$$
where $\cF_n\subset\cF$, $n=0,1,2,\dots$ is the subspace spanned by graphs with $n$ vertices
modulo the 4-term relations.


\begin{theorem}
The multiplication and the comultiplication defined
above induce a bialgebra structure on the space $\cF$ of graphs
modulo 4-term relations.
\end{theorem}


\noindent
{\bf Proof.}
The only thing we need to verify is that the multiplication and the comultiplication
both respect the 4-term relation~(\ref{e23}). For the disjoint union of graphs
this statement is obvious. In order to verify it for the comultiplication,
it is sufficient to consider two different cases. Namely, let $A,B\in V(\G)$
be two distinct vertices of a graph $\G$. The right hand side summands in
the comultiplication formula~(\ref{e24}) split into two groups:
those, where both vertices $A$ and $B$ belong either to the subset $V_1\subset V(\G)$,
or to its complement $V(\G)\setminus V_1$; and those, where $A$ and $B$ belong
to distinct subsets. Natural grouping of terms of the first kind
for the coproduct $\mu(\G-\G_{AB}'-\tG_{AB}+\tG_{AB}')$ provides zero
as the result, while the terms of the second kind group to zero already
for each of the coproducts $\mu(\G-\G_{AB}')$ and $\mu(\tG_{AB}-\tG_{AB}')$.

The theorem is proved.

\begin{remark}\rm Yu.~Vol'vovskii pointed out to me that the same multiplication
and comultiplication induce a bialgebra structure on the space of graphs
modulo the Tutte relations~(\ref{e11}). Note, however, that this bialgebra
is only filtered, not graded since the terms in the
Tutte relations have different
numbers of vertices.
\end{remark}

\begin{remark}\rm For a graph $\G$ denote by $\G^c$ the {\it complementary
graph} to $\G$, i.e., the graph with the same set $V(\G^c)=V(\G)$
of vertices, two vertices $A,B$ being adjacent in $\G^c$
iff they are disconnected in $\G$.

E.~Soboleva attracted my attention to the fact that
passing to the complementary graph preserves the 4-term relations.
This fact allows one to define the
{\it complementary 4-bialgebra} of graphs, isomorphic to the
4-bialgebra. The underlying space
of this bialgebra is the same space $\cF$, and the
comultiplication coincides with that for the 4-bialgebra.
The multiplication $m^c$ is given by the joint union of graphs (i.e.,
each pair of vertices $A\in V(\G_1)$, $B\in V(\G_2)$ in the product
$m^c(\G_1,\G_2)$ is connected by an edge).
\end{remark}

According to the structure theorem, see~\cite{MM,Sw},
a commutative cocommutative
bialgebra with unit over a field of
characteristic zero is isomorphic to a polynomial bialgebra.

\begin{definition}\rm The {\it polynomial bialgebra}
is the bialgebra with the algebra structure isomorphic to that
of the polynomial algebra $\C[x_1,x_2,\dots]$,
and the comultiplication defined on a monomial $y_1\dots y_n$
(where each of the $y_i$ is one of the variables $x_1,x_2,\dots$)
as follows:
\begin{eqnarray*}
\mu(y_1\dots y_n)&=&1\otimes y_1\dots y_n+y_1\otimes y_2\dots y_n
+y_2\otimes y_1y_3\dots y_n+\dots\\
&&+y_1y_2\otimes y_3\dots y_n+\dots + y_1\dots y_n\otimes 1.
\end{eqnarray*}
The sum in the right hand side is taken over all subsets of
the set $\{1,\dots,n\}$ of indices of $y_i$.
\end{definition}

Polynomial bialgebras are called in~\cite{JR}
{\it multivariate divided powers bialgebras}.
Note that a polynomial bialgebra is automatically a Hopf
algebra: one can define the antipode $s:x_i\mapsto-x_i$
on all generators and extend it to the whole bialgebra
by linearity.

If the bialgebra is graded, and the dimension of each grading
subspace is finite, then the isomorphic polynomial bialgebra
also can be chosen graded:
generators are chosen to form bases in each grading subspace.


\subsection{Examples of 4-invariants}\label{s23}

Probably the first non-trivial example of a 4-invariant that is not
a Tutte invariant was suggested by Chmutov and Varchenko in~\cite{CV}
(although the notion of a 4-invariant did not exist then).
Let a {\it vertex quadrangle}
in a graph $\G$ be a subset $\{A_1,A_2,A_3,A_4\}\subseteq V(\G)$
of the set of vertices consisting of four vertices
satisfying the following requirement:
there is a cyclic order  $(i,j,k,l)$ of the set of the indices
$\{i,j,k,l\}=\{1,2,3,4\}$ such that $E(\G)$
contains four edges $A_iA_j$, $A_jA_k$, $A_kA_l$, $A_lA_i$.
Then the number $Q^v(\G)$ of vertex quadrangles in $\G$ is a 4-invariant.

For example, one can check this statement for the 4-term relation
in Fig.~\ref{f22}: each of the graphs in the left hand side of the
equality contains one vertex quadrangle, while there are no vertex
quadrangles in both graphs in the right hand side.

\begin{figure}[t]
\begin{center}
\begin{picture}(300,60)(-50,60)
%The first row
\put(30,100){\circle*{4}}
\put(30,100){\line(1,0){25}}
\put(30,75){\circle*{4}}
\put(30,75){\line(1,0){25}}
\put(30,100){\line(0,-1){25}}
\put(30,100){\line(1,-1){25}}
\put(30,75){\line(1,1){25}}
\put(55,100){\line(0,-1){25}}
\put(55,100){\circle*{4}}
\put(55,75){\circle*{4}}

\put(22,70){${\scriptstyle A}$}
\put(57,70){${\scriptstyle B}$}

\put(63,85){$-$}

\put(80,100){\circle*{4}}
\put(80,100){\line(1,0){25}}
\put(80,75){\circle*{4}}
\put(80,100){\line(0,-1){25}}
\put(80,100){\line(1,-1){25}}
\put(80,75){\line(1,1){25}}
\put(105,100){\line(0,-1){25}}
\put(105,100){\circle*{4}}
\put(105,75){\circle*{4}}

\put(72,70){${\scriptstyle A}$}
\put(107,70){${\scriptstyle B}$}

\put(113,85){$=$}

\put(130,100){\circle*{4}}
\put(130,100){\line(1,0){25}}
\put(130,75){\circle*{4}}
\put(130,75){\line(1,0){25}}
\put(130,100){\line(1,-1){25}}
\put(155,100){\line(0,-1){25}}
\put(155,100){\circle*{4}}
\put(155,75){\circle*{4}}

\put(122,70){${\scriptstyle A}$}
\put(157,70){${\scriptstyle B}$}

\put(163,85){$-$}

\put(180,100){\circle*{4}}
\put(180,100){\line(1,0){25}}
\put(180,75){\circle*{4}}
\put(180,100){\line(1,-1){25}}
\put(205,100){\line(0,-1){25}}
\put(205,100){\circle*{4}}
\put(205,75){\circle*{4}}

\put(172,70){${\scriptstyle A}$}
\put(207,70){${\scriptstyle B}$}



%The second row

\end{picture}
\caption{4-term relation for graphs with 4 vertices}\label{f22}
\end{center}
\end{figure}

It is easy to see that the number of vertex quadrangles is not
a Tutte invariant. Indeed, for the 4-cycle it equals 1,
while for the other two terms in~(\ref{e11})
it is zero.

In order to prove that the number of vertex
quadrangles is indeed a 4-invariant, one can
verify this first for the graphs with 4 vertices,
what can be done by a direct computation. Denote
by $Q^v_4$ the 4-invariant equal to
the number of vertex quadrangles on all 4-vertex graphs,
and equal to zero on all graphs with other number
of vertices.
Now let $U$ denote the function on graphs,
identically equal to 1. This function descends to
a 4-invariant since it obviously satisfies the
4-term relation. Then we have $Q^v=Q^v_4U$,
i.e., the vertex quadrangle invariant is the product
of two invariants. A direct verification of
the fact that the number of vertex quadrangles satisfies
the 4-term relation is also simple.


An {\it edge quadrangle} is a subset $\{e_1,e_2,e_3,e_4\}\subseteq E(\G)$
of the set of edges of $\G$ forming a quadrangle after an appropriate
ordering. The number $Q^e(\G)$ of edge quadrangles is not a
4-invariant. However, it becomes a 4-invariant if considered modulo 2.
For example, the first graph in the left hand side of Fig.~\ref{f22}
contains 3 edge quadrangles, the number of edge quadrangles in the
second graph equals 1, while there are no edge quadrangles
in both graphs in the right hand side.
Either of the proofs described above for the number of vertex
quadrangles works in this case as well.


Similar statement is valid for the number $P^e(\G)$
of edge pentagons in a graph $\G$ considered $\mod\ 2$.
An {\it edge pentagon} is a cyclic chain of five edges
in $\G$ with five distinct vertices. For example,
the number of edge pentagons in the clique $K_5$
on 5 vertices is $P^e(K_5)=12\equiv 0\ \mod\ 2$.
Indeed, the number of different cyclic orderings
on the set of 5 vertices is 24, and two
different cyclic orderings result in the same chain
of edges iff they differ by reversing of the ordering.

Once again, this statement can be proved by direct
computation on the set of 5-vertex graphs~\cite{S}
and then the multiplication argument
can be applied.


A slightly more sophisticated example of a 4-invariant,
due to Yu.~Vol'vovskii,
is given by the following proposition.

Let us number the vertices of a graph $\G$ and
let $A(\G)$ denote the adjacency matrix of $\G$.
This means that the entry $a_{ij}$ of $A(\G)$ is $1$ if the $i$th
and the $j$th vertices are connected by an edge, and
$a_{ij}=0$ otherwise. Note that the adjacency matrix is symmetric.

\begin{proposition}\label{p21}
The rank of the adjacency matrix considered $\mod~2$
is a 4-invariant.
\end{proposition}

\noindent
{\bf Proof.} We are going to prove a more strong statement,
namely that the rank of the adjacency matrix
considered modulo 2 is invariant under the mapping
$\G\mapsto\tG_{AB}$ for any graph $\G$ and any pair
of vertices $A,B\in V(\G)$. In other words, the rank
satisfies the {\it 2-term relation}.

Indeed, let the vertex $A$ have the index 1 and the vertex $B$ have the index 2.
Then the mapping $\G\mapsto\tG_{AB}$ results, on the level of
adjacency matrices, in the conjugation
$A(\tG_{AB})\equiv C^TA(\G)C~\mod~2$,
where $C$ is the matrix
$$
C=\left(\begin{array}{cccc}
1&1&0&\dots\\
0&1&0&\dots\\
0&0&1&\dots\\
\dots&\dots&\dots&\dots
\end{array}\right)
$$
and $C^T$ is the transpose matrix.
In particular, this transformation does not change the rank
of $A(\G)$. Note, however, that this 4-invariant
is not very strong.



\subsection{Primitive elements}\label{s24}


\begin{definition}\rm
An element $p$ of a bialgebra is called {\it primitive}
if its coproduct is
$$
\mu(p)=1\otimes p+p\otimes1.
$$
\end{definition}

Primitive elements are, in a sense, the ``simplest''
elements of a bialgebra. For example, in a polynomial
bialgebra $\C[x_1,x_2,\dots]$ an element is primitive
iff it is a linear combination of generators,
$c_1x_1+c_2x_2+\dots+c_kx_k$. This subsection is
devoted to a description of primitive elements in
the 4-bialgebra of graphs. Primitive elements form
the linear space $\cP\subset\cF$, which is also graded,
$$
\cP=\cP_1\oplus\cP_2\oplus\cP_3\oplus\dots.
$$
Note that the unit is not a primitive element since
$\mu(1)=1\otimes1\ne1\otimes1+1\otimes1$.

Let $P_k$ be the dimension of the space $\cP_k$.
After picking up a basis $s_{k,1}$, $s_{k,2}$,
$\dots$, $s_{k,P_k}$
in each $\cP_k$ we make the 4-bialgebra into the polynomial
bialgebra in variables $s_{ij}$. Therefore, the crucial
point in the description of the structure of the 4-bialgebra
is the study of its primitive elements, especially, it
is most important to find the sequence $P_1,P_2,P_3,\dots$.

Let us present some examples of primitive elements in the 4-bialgebra.
The space $\cF_1$ is spanned by the unique graph
with one vertex. We denote this graph by $s_{11}$.
This graph obviously is primitive,
whence $P_1=1$.

The space $\cF_2$ is spanned by the two two-vertex graphs:
the segment and the graph consisting of
two disjoint vertices. The 4-term
relations for two-vertex graphs are empty,
whence $\dim\cF_2=2$. There is a unique (up to
a multiplicative constant) primitive element
in $\cF_2$ (see Fig.~\ref{f22a} a)).

\begin{figure}[t]
\begin{center}
\begin{picture}(300,60)(-50,-10)
%\begin{center}
\put(-60,20){\circle*{4}}
\put(-60,20){\line(1,0){25}}
\put(-35,20){\circle*{4}}
\put(-25,17){$-$}
\put(-10,20){\circle*{4}}
\put(15,20){\circle*{4}}
\put(-25,0){a)}

\put(60,20){\circle*{4}}
\put(60,20){\line(1,0){25}}
\put(85,20){\circle*{4}}
\put(85,20){\line(1,0){25}}
\put(110,20){\circle*{4}}
\put(120,17){$-\ \ 2$}
\put(150,20){\circle*{4}}
\put(165,20){\circle*{4}}
\put(165,20){\line(1,0){25}}
\put(190,20){\circle*{4}}
\put(200,17){$+$}
\put(215,20){\circle*{4}}
\put(230,20){\circle*{4}}
\put(245,20){\circle*{4}}
\put(150,0){b)}
\end{picture}

\caption{Basic primitive elements a) in $\cP_2$ and b) in $\cP_3$}\label{f22a}
\end{center}
\end{figure}

We denote this element by $s_{21}$.
Its primitiveness can be verified directly from the
definition. Therefore, $P_2=1$ as well. The space
$\cF_2$ is spanned by two elements $s_{21}$ and $s_{11}^2$.

In order 3 we meet the first non-trivial example
of the 4-term relation. There are 4 distinct graphs with
three vertices, and the only essential 4-term relation is shown
in Fig.~\ref{f23}.

\begin{figure}[t]
\begin{center}
\begin{picture}(300,60)(-50,60)
%The first row
\put(42,100){\circle*{4}}
\put(42,100){\line(1,-2){12}}
\put(30,75){\circle*{4}}
\put(30,75){\line(1,0){25}}
\put(42,100){\line(-1,-2){12}}
\put(55,75){\circle*{4}}

\put(22,70){${\scriptstyle A}$}
\put(57,70){${\scriptstyle B}$}

\put(63,85){$-$}

\put(92,100){\circle*{4}}
\put(92,100){\line(1,-2){12}}
\put(80,75){\circle*{4}}
\put(92,100){\line(-1,-2){12}}
\put(105,75){\circle*{4}}


\put(72,70){${\scriptstyle A}$}
\put(107,70){${\scriptstyle B}$}

\put(113,85){$=$}

\put(142,100){\circle*{4}}
\put(142,100){\line(1,-2){12}}
\put(130,75){\circle*{4}}
\put(130,75){\line(1,0){25}}
\put(155,75){\circle*{4}}

\put(122,70){${\scriptstyle A}$}
\put(157,70){${\scriptstyle B}$}

\put(163,85){$-$}

\put(192,100){\circle*{4}}
\put(192,100){\line(1,-2){12}}
\put(180,75){\circle*{4}}
\put(205,75){\circle*{4}}

\put(172,70){${\scriptstyle A}$}
\put(207,70){${\scriptstyle B}$}



%The second row

\end{picture}
\caption{4-term relation for graphs with 3 vertices}\label{f23}
\end{center}
\end{figure}

Hence, $\dim\cF_3=3$. Note that, in contrast to the case
of Tutte invariants, the graph $K_3$, the triangle,
can be expressed as a linear combination of forests.
The subspace $\cP_3$ of primitive elements is spanned
by the linear combination shown in Fig.~\ref{f22a} b).

We denote this element by $s_{31}$. Hence, $P_3=1$.
The space $\cF_3$ is thus spanned by the elements
$s_{11}^3,s_{21}s_{11},s_{31}$.

Similar computations in higher orders~\cite{S}
give the following values of the dimensions:
$P_4=2$, $P_5=3$, $P_6=5$. Computer computations
elaborated by A.~Kaishev show that $P_7=7$.
Note that the computational complexity grows very quickly
because of increasing both of the number of graphs and
of the number of 4-term relations. It is not easy even
to identify the same four terms in relations obtained
from different edges of different graphs.

Now we are going to describe a projection
$\pi_n:\cF_n\to\cP_n$ of
the space of $n$-vertex graphs onto the subspace of
primitive elements.

\begin{theorem}
For any graph $\G\in\cF_n$ the element
\begin{equation}\label{e25}
\pi_n(\G)=\G-1!\sum_{V_1\sqcup V_2=V(\G)} G(V_1)G(V_2)+
2!\sum_{V_1\sqcup V_2\sqcup V_3=V(\G)}G(V_1)G(V_2)G(V_3)-\dots,
\end{equation}
where the $k$th sum is taken over all partitions of the
set $V(\G)$ of vertices of $\G$ into a disjoint union of
nonempty subsets $V_1,\dots,V_k$, is primitive. The mapping
$\pi_n$ descends to a projection $\pi_n:\cF_n\to\cP_n$,
i.e., it is onto and $\pi_n\circ\pi_n=\pi_n$.
\end{theorem}

The proof can be found in~\cite{L2}.

As an application of the previous theorem let us
construct the primitive element $\pi_4(C_4)$, where $C_4$
is the cycle on four vertices. The construction is shown
in Fig.~\ref{f24}. Let us clarify how the coefficient $-3$
at the edgeless graph in the right hand side of Fig.~\ref{f24}
can be obtained from Eq.~(\ref{e25}). There is a unique way to
split the vertices $V(C_4)$ into two nonempty subsets $V_1,V_2$
such that both graphs $G(V_1),G(V_2)$ are edgeless: each of
the sets $V_i$ must consist of opposite vertices of the square.
There are two ways to split $V(C_4)$ into three non-empty subsets
so that all the three induced graphs are edgeless:
the two vertices contained in one subset must
be opposite vertices of the square.
Finally, the unique way to split $V(C_4)$ into four non-empty
subsets leads to an edgeless graph. Hence, the coefficient
at the edgeless graph in the projection must be
$$
-1!\cdot1+2!\cdot2-3!\cdot1=-3.
$$
Other coefficients are obtained in a similar way.

\begin{figure}[t]
\begin{center}
\begin{picture}(300,60)(-20,60)
%The first row
\put(13,85){$\pi_4($}
\put(30,100){\circle*{4}}
\put(30,100){\line(1,0){25}}
\put(30,75){\circle*{4}}
\put(30,75){\line(1,0){25}}
\put(30,100){\line(0,-1){25}}
\put(55,100){\line(0,-1){25}}
\put(55,100){\circle*{4}}
\put(55,75){\circle*{4}}
\put(58,85){$)\ =$}


\put(80,100){\circle*{4}}
\put(80,100){\line(1,0){25}}
\put(80,75){\circle*{4}}
\put(80,75){\line(1,0){25}}
\put(80,100){\line(0,-1){25}}
\put(105,100){\line(0,-1){25}}
\put(105,100){\circle*{4}}
\put(105,75){\circle*{4}}


\put(115,85){$-\ 4$}

\put(140,87){\circle*{4}}
\put(150,87){\circle*{4}}
\put(150,87){\line(1,0){25}}
\put(175,87){\circle*{4}}
\put(175,87){\line(1,0){25}}
\put(200,87){\circle*{4}}

\put(210,85){$-\ 2$}

\put(235,87){\circle*{4}}
\put(235,87){\line(1,0){25}}
\put(260,87){\circle*{4}}
\put(270,87){\circle*{4}}
\put(270,87){\line(1,0){25}}
\put(295,87){\circle*{4}}

%The second row

\put(80,55){$+\ 8$}

\put(105,57){\circle*{4}}
\put(115,57){\circle*{4}}
\put(125,57){\circle*{4}}
\put(125,57){\line(1,0){25}}
\put(150,57){\circle*{4}}

\put(160,55){$-\ 3$}

\put(185,57){\circle*{4}}
\put(195,57){\circle*{4}}
\put(205,57){\circle*{4}}
\put(215,57){\circle*{4}}



\end{picture}

\caption{Projecting the 4-cycle to the space of primitive elements}\label{f24}
\end{center}
\end{figure}

\begin{remark}\rm
We can consider the 4-bialgebra over $\Z$, not over
a field of characteristic zero. In this case the
structure theorem cannot be applied. However,
since all the coefficients in~(\ref{e25}) are integers,
primitive elements of the 4-bialgebra generate it
over $\Z$ as well. What we do not know, is whether
there is torsion in the submodule of primitive elements.
Up to now calculations show no torsion, but it can
appear in higher orders.
\end{remark}

\section{Bialgebra of chord diagrams}\label{s3}
This section is devoted to a brief description
of the bialgebra of chord diagrams and its
connection with the 4-bialgebra of graphs.
Details of the description can be found
in~\cite{B,BL,CDL1,K}. We also pose some
problems related to the connection between the
two bialgebras.

\subsection{4-term relation for chord diagrams}\label{s31}

A {\it chord diagram of order} $n$ is an
oriented circle equipped with $n$ pairs of
distinct points considered
up to orientation preserving diffeomorphisms
of the circle. Points belonging to the same pair
are usually connected by a chord in order
to visualize the pairing (see Fig.~\ref{f31}~a)).
On the pictures, the circle is always oriented
counterclockwise.

%\begin{verbatim}
%
% defs for fig
%
\def\celvn
{  \bezier{40}(-1,0)(-1,0.577)(-0.5,0.866)
   \bezier{40}(-0.5,0.866)(0,1.155)(0.5,0.866)
   \bezier{40}(0.5,0.866)(1,0.577)(1,0)
   \bezier{40}(1,0)(1,-0.577)(0.5,-0.866)
   \bezier{40}(0.5,-0.866)(0,-1.155)(-0.5,-0.866)
   \bezier{40}(-0.5,-0.866)(-1,-0.577)(-1,0)
}
\def\vert
{   \put(0,1){\circle*{0.15}}
    \put(0,-1){\circle*{0.15}}
    \put(0,1){\line(0,-1){2}}
}
%
%   fig
%   Tree line diagrams
%
%
\begin{figure}[t]
\begin{center}
\begin{picture}(180,60)(-20,-30)
  \setlength{\unitlength}{20pt}
  \put(0,0){
     \begin{picture}(0,0)
     \celvn%\vert
      \put(0,1){\circle*{0.15}}
      \put(0,-1){\circle*{0.15}}
      \put(1,0){\circle*{0.15}}
      \put(-1,0){\circle*{0.15}}
      \put(0.705,0.705){\circle*{0.15}}
      \put(-0.705,0.705){\circle*{0.15}}
      \put(0.705,-0.705){\circle*{0.15}}
      \put(-0.705,-0.705){\circle*{0.15}}
     \bezier{50}(0.705,-0.705)(0.1,0.1)(0,1)
     \bezier{50}(-0.705,0.705)(0.1,0.1)(1,0)
     \put(-0.705,-0.705){\line(1,1){1.4}}
     \bezier{50}(-1,0)(-0.1,-0.1)(0,-1)
     \end{picture}
           }
  \setlength{\unitlength}{1pt}
\put(100,-15){\circle*{4}}
\put(125,-15){\circle*{4}}
\put(150,-15){\circle*{4}}
\put(112,10){\circle*{4}}
\put(100,-15){\line(1,0){25}}
\put(125,-15){\line(1,0){25}}
\put(100,-15){\line(1,2){12}}
\put(125,-15){\line(-1,2){12}}

\put(-2,-30){$a)$}
\put(121,-30){$b)$}


\end{picture}
\caption{A chord diagram a) and its intersection graph b)}\label{f31}
\end{center}
\end{figure}
%\end{verbatim}

V.~A.~Vassiliev invented chord diagrams for presenting
{\it singular knots} in $\R^3$, i.e., knots admitting
double points. Figure~\ref{f32} demonstrates
the 4-term relation for chord diagrams.
Here the dotted parts of the circles may contain
arbitrary sets of chords that are, however, the same for all four diagrams.

% definitions for fig 3
%
\def\bcirc
{    \bezier{40}(-1,0)(-1,0.577)(-0.5,0.866)
     \bezier{8}(-0.5,0.866)(0,1.155)(0.5,0.866)
     \bezier{40}(0.5,0.866)(1,0.577)(1,0)
     \bezier{8}(0.5,-0.866)(1,-0.577)(1,0)
     \bezier{40}(-0.5,-0.866)(0,-1.155)(0.5,-0.866)
     \bezier{8}(-1,0)(-1,-0.577)(-0.5,-0.866)
}
\def\pone{\put(-0.866,0.5){\circle*{0.15}}}
\def\ptwo{\put(0.866,0.5){\circle*{0.15}}}
\def\pthree{\put(0,-1){\circle*{0.15}}}
\def\pfour{\put(-0.25,-0.966){\circle*{0.15}}}
\def\pfive{\put(0.25,-0.966){\circle*{0.15}}}
\def\psix{\put(0.707,0.707){\circle*{0.15}}}
\def\pseven{\put(0.966,0.25){\circle*{0.15}}}
%
\begin{figure}[t]
% a chord diagram and its intersection graph
%
\begin{center}
\begin{picture}(300,60)(-20,-30)
  \setlength{\unitlength}{20pt}
  \put(0,0){
  \begin{picture}(0,0)
     \bcirc
     \pone\ptwo\pfour\pfive
     \bezier{60}(-0.866,0.5)(0,0)(0.25,-0.966)
     \bezier{60}(0.866,0.5)(0,0)(-0.25,-0.966)
  \end{picture}
  }
  \put(-1.1,.7){A}
  \put(1,.7){B}
  \put(2,0){\makebox(0,0){$-$}}
  \put(3.7,0){
  \begin{picture}(0,0)
     \bcirc
     \pone\ptwo\pfour\pfive
     \bezier{60}(-0.866,0.5)(-0.28,-0.12)(-0.25,-0.966)
     \bezier{60}(0.866,0.5)(0.28,-0.12)(0.25,-0.966)
  \end{picture}
  }
  \put(2.6,.7){A}
  \put(4.7,.7){B}
  \put(5.7,0){\makebox(0,0){$+$}}
  \put(7.4,0){
  \begin{picture}(0,0)
     \bcirc
     \pone\pthree\psix\pseven
     \bezier{60}(-0.866,0.5)(-0.04,0.3)(0.707,0.707)
     \bezier{60}(0,-1)(0.24,-0.19)(0.966,0.25)
  \end{picture}
  }
  \put(6.3,.7){A}
  \put(8.6,.25){B}
  \put(9.4,0){\makebox(0,0){$-$}}
  \put(11.1,0){
  \begin{picture}(0,0)
     \bcirc
     \pone\pthree\psix\pseven
     \bezier{60}(-0.866,0.5)(0,0)(0.966,0.25)
     \bezier{60}(0,-1)(0,0)(0.707,0.707)
  \end{picture}
  }
  \put(10,.7){A}
  \put(12.1,.7){B}
  \put(13.1,0){\makebox(0,0){$=$}}
  \put(14.1,0){\makebox(0,0){$0$}}
\end{picture}
\caption{4-term relation for chord diagrams}\label{f32}
\end{center}
\end{figure}

Let $\cD_n$ denote the space over $\C$ spanned by all
chord diagrams of order $n$ modulo the 4-term relations.
Elements of the dual space $\cD_n^*$ are usually called
{\it weight systems} (or {\it preinvariants},
as in~\cite{CDL1}) of order $n$.
Define the product of two chord diagrams of order $n_1$,
$n_2$ as a chord diagram of order $n=n_1+n_2$
that can be obtained by gluing together the two circles
broken at arbitrary points distinct from the ends of
the chords. The gluing must respect the orientation
of the circles. It can be shown that, modulo the 4-term
relations, the resulting chord diagram does not depend on
the choice of the breaking points.

Denote the set of chords of a chord diagram $D$
by $V(D)$. Each subset $V_1\subset V(D)$ of chords
determines a chord diagram $D(V_1)$, which contains
only chords belonging to $V_1$.
The coproduct of a chord diagram $D\in\cD_n$ looks like
$$
\mu(D)=\sum_{V_1\subset V(D)} D(V_1)\otimes D(V(D)\setminus V_1).
$$

The following theorem belongs to Bar-Natan and Kontsevich~\cite{B}.

\begin{theorem} The multiplication and the comultiplication
defined above make the space $\cD$ into a
commutative cocommutative bialgebra.
\end{theorem}


The structure theorem applied to this bialgebra states
that it is also a polynomial bialgebra. Calculations
started by Vassiliev and continued by Bar-Natan~\cite{B} and
then by Kneissler~\cite{Kn} give the following values for the
sequence $p_1,p_2,\dots$ of dimensions of primitive
elements subspaces.

\begin{center}
\begin{tabular}{l|c|c|c|c|c|c|c|c|c|c|c|c}
$n$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\
\hline
$p_n$ & 1 & 1 & 1 & 2 & 3 & 5 & 8 & 12 & 18 & 27 & 39 & 55
\end{tabular}
\end{center}

\subsection{Intersection graphs of chord diagrams}\label{s32}

Let $v_1,v_2\in V(D)$ be two distinct chords of a chord
diagram $D$. We say that the chords $v_1,v_2$ {\it intersect}
if their ends follow the circle in the alternating order.

\begin{definition}\rm
The {\it intersection graph} $\g(D)$ of a chord diagram $D$
is specified by the following data:
\begin{itemize}
\item the vertices of $\g(D)$ are in one-to-one correspondence
with the chords of the diagram $D$;
\item two vertices $v_1,v_2$ are joined by an edge iff
the chords $v_1,v_2$ intersect.
\end{itemize}
\end{definition}

The intersection graph for the chord diagram
from Fig.~\ref{f31}~a) is shown on Fig.~\ref{f31}~b).


Note that not each graph can be obtained as the intersection graph
of a chord diagram. The simplest counter-example is the 5-wheel,
a graph with 6 vertices. Graphs that can be realized in
this way are called {\it circle}, or {\it alternance}
graphs, see~\cite{Bo,G}, where algorithmic problems
related to these graphs are studied.
On the other hand, distinct
chord diagrams can lead to the same intersection graph (see
Fig.~\ref{f33}).

\begin{figure}[t]
%
% defs for fig
%
\def\celvn
{  \bezier{40}(-1,0)(-1,0.577)(-0.5,0.866)
   \bezier{40}(-0.5,0.866)(0,1.155)(0.5,0.866)
   \bezier{40}(0.5,0.866)(1,0.577)(1,0)
   \bezier{40}(1,0)(1,-0.577)(0.5,-0.866)
   \bezier{40}(0.5,-0.866)(0,-1.155)(-0.5,-0.866)
   \bezier{40}(-0.5,-0.866)(-1,-0.577)(-1,0)
}
\def\vert
{   \put(0,1){\circle*{0.15}}
    \put(0,-1){\circle*{0.15}}
    \put(0,1){\line(0,-1){2}}
}
%
%   fig
%   Tree line diagrams
%
\begin{center}
\begin{picture}(180,60)(-20,-30)
  \setlength{\unitlength}{20pt}
  \put(0,0){
     \begin{picture}(0,0)
     \celvn\vert
     \put(0.866,0.5){\circle*{0.15}}
     \put(-0.5,0.866){\circle*{0.15}}
     \bezier{40}(-0.5,0.866)(0.086,0.322)(0.866,0.5)
     \put(0.5,-0.866){\circle*{0.15}}
     \put(-0.866,-0.5){\circle*{0.15}}
     \bezier{40}(-0.866,-0.5)(-0.086,-0.322)(0.5,-0.866)
     \put(0.5,0.866){\circle*{0.15}}
     \put(1,0){\circle*{0.15}}
     \bezier{40}(1,0)(0.433,0.25)(0.5,0.866)
     \put(-0.5,-0.866){\circle*{0.15}}
     \put(-1,0){\circle*{0.15}}
     \bezier{40}(-1,0)(-0.433,-0.25)(-0.5,-0.866)
     \end{picture}
           }
  \put(4,0){
     \begin{picture}(0,0)
     \celvn
     \put(-0.5,0.866){\circle*{0.15}}
     \put(-0.5,-0.866){\circle*{0.15}}
     \put(-0.5,-0.866){\line(0,1){1.732}}
     \put(-0.866,0.5){\circle*{0.15}}
     \put(0.5,0.866){\circle*{0.15}}
     \bezier{40}(-0.866,0.5)(-0.086,0.322)(0.5,0.866)
     \put(0,1){\circle*{0.15}}
     \put(0.866,0.5){\circle*{0.15}}
     \bezier{40}(0.866,0.5)(0.25,0.433)(0,1)
     \put(-0.866,-0.5){\circle*{0.15}}
     \put(0.5,-0.866){\circle*{0.15}}
     \bezier{40}(-0.866,-0.5)(-0.086,-0.322)(0.5,-0.866)
     \put(0,-1){\circle*{0.15}}
     \put(0.866,-0.5){\circle*{0.15}}
     \bezier{40}(0.866,-0.5)(0.25,-0.433)(0,-1)
     \end{picture}
           }
  \put(8,0){
     \begin{picture}(0,0)
     \celvn\vert
     \put(-0.866,0.5){\circle*{0.15}}
     \put(0.5,0.866){\circle*{0.15}}
     \bezier{40}(0.5,0.866)(-0.086,0.322)(-0.866,0.5)
     \put(-0.5,-0.866){\circle*{0.15}}
     \put(0.866,-0.5){\circle*{0.15}}
     \bezier{40}(0.866,-0.5)(0.086,-0.322)(-0.5,-0.866)
     \put(-0.5,0.866){\circle*{0.15}}
     \put(-1,0){\circle*{0.15}}
     \bezier{40}(-1,0)(-0.433,0.25)(-0.5,0.866)
     \put(0.5,-0.866){\circle*{0.15}}
     \put(1,0){\circle*{0.15}}
     \bezier{40}(1,0)(0.433,-0.25)(0.5,-0.866)
     \end{picture}
           }
\end{picture}
\caption{Three distinct chord diagrams with
the same intersection graph}\label{f33}
\end{center}
\end{figure}

The 4-term relation for chord diagrams makes their
connection with intersection graphs even more complicated.
Namely, explicit calculations show that up to order 8
the equivalence class of a chord diagram modulo the 4-term relation
is totally determined by its intersection graph.
This evidence led to our conjecture~\cite{CDL1}
that this is the case for diagrams of all orders.
However, this conjecture proved to be false
(T.~Le, unpublished, see~\cite{CD}).

The 4-bialgebra of graphs from Sec.~\ref{s2} is invented
to isolate properties of chord diagrams that are
determined by their intersection graphs.

\begin{theorem}
The mapping $\g:D\mapsto\g(D)$ associating to each
chord diagram $D$ its intersection graph $\g(D)$
descends to a homomorphism $\g:\cD\to\cF$.
\end{theorem}

Note that the mapping $\g$ preserves the grading
and, therefore, it is the direct sum of linear mappings
$\g_n:\cD_n\to\cF_n$.

As an immediate consequence of the theorem
we obtain the following
statement.

\begin{corollary}
Any 4-invariant $f:\cF_n\to A$ determines
a weight system $\g_n^*f:\cD_n\to A$.
\end{corollary}

Here $A$ is an arbitrary Abelian group and
$\g_n^*f=f\circ\g_n$ as usual.

The proof of the theorem is obvious. The only thing
we need to verify is that the mapping $\g$ respects
the 4-term relation. But the rule for the 4-term
relation for graphs~(\ref{e23}) is precisely what happens
with the intersection of chords in all 4 diagrams
from Fig.~\ref{f32}.

In conclusion, let us state a conjecture about the properties
of the mapping $\g:\cD\to\cF$. The statement of Le cited above shows
that $\g$ cannot be a monomorphism. We also know that not each
graph can be obtained as the intersection graph of a chord diagram.
Nevertheless, for all $n$ the image of $\g_n$ contains the $n$-clique
(the graph with $n$ vertices with each pair of vertices
joined by an edge). The $n$-clique is, in a sense,
``the most complicated'' graph, all other graphs are
``simpler''. Therefore, one can expect that each graph
is equivalent, modulo the 4-term relation, to a linear
combination of intersection graphs.

\begin{conjecture}
The mapping $\g_n:\cD_n\to\cF_n$ is an epimorphism for all $n$.
\end{conjecture}

Calculations up to order 6~\cite{S} confirm
this conjecture. Besides, one would expect that
the kernel of $\g_n$ is ``thin'' in $\cD_n$.
Indeed, up to order~6 it is just empty,
and in order~7 its dimension is one. However,
up to now the evidence is too small to make a precise
conjecture. Note that the study of this kernel is,
probably, the most interesting part of the work.
For example, only elements of this kernel (if any) may
say a chord diagram from its mirror image.


\subsection{Weighted invariants of graphs}\label{s33}
Here we explain the results from~\cite{CDL3},
where the first construction of Vassiliev invariants
through the intersection graphs of chord diagrams was
given. For proofs and details see~\cite{CDL3}.
A description of a bialgebra of graphs with
weighted both vertices and edges, which generalizes the
construction from~\cite{CDL3}, can be found in~\cite{L1}.

Consider graphs (without loops and multiple edges)
with weighted vertices, where
the weight can take arbitrary positive integer values.
The weight of a graph is the sum of the weights of all
its vertices.

The {\it weighted Tutte relation} for weighted graphs
coincides with the Tutte relation~(\ref{e11}),
where, however, the contraction $\G\mapsto\G_e''$
is understood differently.
Namely, after contraction possible multiple
edges are eliminated, and the weight of the resulting
new vertex is set to be equal to the sum of
the weights of the ends of the contracted edge $e$.
All the three terms in the weighted Tutte relation~(\ref{e11})
have the same weight. Therefore, the linear space
$\cW$ generated by weighted graphs modulo the weighted
Tutte relation is graded,
$$
\cW=\cW_0\oplus\cW_1\oplus\cW_2\oplus\dots
$$
with respect to the weight.
The space $\cW$ is endowed with a bialgebra structure
in the same manner as it was done in Sec.~\ref{s2} for the
4-bialgebra of graphs.

\begin{theorem}[\cite{CDL3}]
The bialgebra $\cW$ is isomorphic to the polynomial
bialgebra $\C[s_1,s_2,\dots]$ through the mapping taking
the one-vertex graph of weight $k$ to the variable $s_k$.
The mapping $\G_n:\cD_n\to\cW_n$ taking a chord diagram
to its intersection graph with weights of all vertices set to 1
is a bialgebra epimorphism.
\end{theorem}

Thus, the bialgebra of weighted graphs is very small
in comparison with both the bialgebra of chord diagrams
and the 4-bialgebra of graphs:
it contains precisely one primitive element of each order.
It is a quotient bialgebra for both these bialgebras:

\begin{proposition}
Associate to a graph a weighted graph by assigning
weight 1 to each of the vertices. Then this mapping descends
to an epimorphism of the 4-bialgebra onto the bialgebra
of weighted graphs.
\end{proposition}

The proof consists in showing that the contraction of
the edge $AB$ in both sides of~(\ref{e23}) lead to
the same weighted graph (with the weight of the new
vertex equal to 2).



Further developments in the study of the weighted bialgebra
and a discussion of complexity problems arising there
can be found in~\cite{NW}.


\section{Problems}\label{s34}

The number of open questions in the study of the 4-bialgebra
exceeds the number of the solved ones dramatically.
We formulate in the present section few of them,
including those that were stated above.

\begin{problem}
Describe the behavior of the sequence $1,1,1,2,3,5,7,\dots$
of dimensions of the spaces $\cP_1,\cP_2,\dots$ of
primitive elements in the 4-bialgebra. In particular,
find a reasonable algorithm generating this sequence.
\end{problem}

\begin{problem}
Which of the known graph invariants are 4-invariants?
\end{problem}

Examples of such graph invariants would lead to new
knot invariants.

\begin{problem}
Describe the kernel of the homomorphism $\g:\cD\to\cF$.
\end{problem}

As we have seen above, this kernel is nontrivial
already for $n=7$.

\begin{problem} If considered over $\Z$, whether the 4-bialgebra
has a torsion?
\end{problem}

There is a construction of chord diagrams invariants
through Lie algebras due to Bar-Natan~\cite{B}
and Kontsevich~\cite{K}. The vertex quadrangle 4-invariant $Q^v$
from Sec.~\ref{s23} arose in the analysis of this construction
for the Lie algebra $\sl_2$ in~\cite{CV}.
E.~Soboleva showed in~\cite{S} that the 4-invariant
determined by the rank of the adjacency matrix
(Proposition~\ref{p21}) coincides, essentially,
with the one determined by the standard representation
of the Lie algebra $\sl_n$.
It is known,
however, that not all weight systems coming from Lie
algebras determine 4-invariants (the fact that was used by Le
in his disproof of the graph conjecture).

\begin{problem}
What Lie algebras determine 4-invariants of graphs?
What are these 4-invariants?
\end{problem}

\begin{thebibliography}{99}
\bibitem{B} {\sc D.~Bar-Natan},  On the Vassiliev knot invariants,
{\it Topology} {\bf 34}, 423--472 (1995)

\bibitem{BG} {\sc D.~Bar-Natan and S.~Garoufalidis},
On the Melvin--Morton--Rozansky conjecture,
{\it Inv. Math.} {\bf 125}, 103--133 (1996)

\bibitem{BL} {\sc J.~Birman and X.-S.Lin}, Knot polynomials and
Vassiliev invariants, {\it Invent. Math.} {\bf 111}, 225--270 (1993)

\bibitem{Bo} {\sc A.~Bouchet}, Reducing prime graphs
and recognizing circle graphs, {\it Combinatorica} {\bf 7},
243--254 (1987)

\bibitem{CD} {\sc S.~V.~Chmutov, S.~V.~Duzhin}, The Kontsevich
integral (1997), preprint available from anonymous ftp\\
{\bf ftp.botik.ru/pub/local/zmr/ki.ps.gz}.

\bibitem{CDL1} {\sc S.~V.~Chmutov, S.~V.~Duzhin and S.~K.~Lando},
Vassiliev knot invariants I. Introduction,
{\it in}: ``Adv. in Soviet Math.,'' {\bf 21}, AMS, 117--126 (1994)

\bibitem{CDL3} {\sc S.~V.~Chmutov, S.~V.~Duzhin and S.~K.~Lando},
Vassiliev knot invariants III. Forest algebra and weighted graphs,
{\it in}� ``Adv. in Soviet Math.,'' {\bf 21}, AMS, 135--146 (1994)

\bibitem{CV} {\sc S.~V.~Chmutov and A.~N.~Varchenko},
Remarks on the Vassiliev knot invariants
coming from $\sl_2$, {\it Topology} {\bf 36}, 153--178 (1997)

\bibitem{G} {\sc M.~C.~Golumbic}, ``Algorithmic graph theory
and perfect graphs,'' Academic Press, New York (1980)

\bibitem{JR} {\sc S.~A.~Joni and G.-C.~Rota},
Coalgebras and bialgebras in combinatorics,
{\it in}: Umbral calculus and Hopf algebras,
`Contemporary Math., {\bf 6},
AMS, Providence RI, 1--47 (1982)

\bibitem{Kn} {\sc J.~A.~Kneissler}, The number of
primitive Vassiliev invariants up to degree twelve,
preprint (1997).

\bibitem{K} {\sc M.~Kontsevich}, Vassiliev's knot invariants,
{\it in} ``Adv. in Soviet Math.'' {\bf 16}, Part 2, AMS, (1993)

\bibitem{L1} {\sc S.~K.~Lando}, Tutte decomposition for graphs,
weighted graphs and symmetric matrices,
{\it in}: ``Amer. Math. Soc. Transl.'' {\bf 185}, AMS, 137--146 (1998)

\bibitem{L2} {\sc S.~K.~Lando}, On primitive elements in the bialgebra
of chord diagrams, {\it in}
``Amer. Math. Soc. Transl. (2),'' {\bf 180}, AMS, 167--174 (1997)

\bibitem{MM} {\sc J.~Milnor, J.~Moore}, On the structure of Hopf
algebras, {\it Ann. Math.} {\bf 81}, 211--264 (1965)

\bibitem{NW} {\sc S.~D.~Noble and D.~J.~A.~Welsh}
Weighted graphs and Vassiliev invariants,
preprint (October 16 1997).

\bibitem{S} {\sc E.~S.~Soboleva}, Vassiliev knot invariants
coming from Lie algebras and 4-invariants, preprint (2000)

\bibitem{Sw} {\sc M.~E.~Sweedler}, ``Hopf Algebras,''
Benjamin, New York (1969)

\bibitem{T} {\sc W.~T.~Tutte}, A ring in graph theory,
{\it Proc. Cambridge Phil. Soc.} {\bf 43} (1947),
26--40. Reprinted {\it in} ``Selected Papers of W.~T.~Tutte,''
Vol.~1, The Charles Babbage Research Center,
Manitoba, Canada (1979).

\bibitem{V} {\sc V.~A.~Vassiliev}, Cohomology of knot spaces,
{\it in} ``Advances in Soviet Math.,'' {\bf 1}, AMS (1990)


\end{thebibliography}

\end{document}
