Arnold's seminar
February 9, 1999

Sergei K. Lando
Summary of the talk "On a Hopf algebra in graph theory".

It is possible to associate to a chord diagram its
intersection graph. The vertices of the graph are in
one-to-one correspondence with the chords of the diagram,
and two vertices are connected by an edge iff the
corresponding chords intersect. In 1992 Duzhin noted that
the chromatic polynomial of the intersection graph of
a chord diagram determines a Vassiliev invariant of knots.
He also posed a problem, what part of the information 
about a chord diagram is encoded in its intersection graph.
In a joint paper (Chmutov-Duzhin-Lando, 1994) we constructed
a Hopf algebra of graphs and proved that there is at least
one nontrivial primitive element of each order in the Hopf
algebra of chord diagrams. It was obvious, however, that
the intersection graphs carry much more rich information
than that covered by our algebra. 

I am going to talk about a new Hopf algebra of graphs
(the 4-bialgebra), which incorporates much more powerful
data than the one mentioned above. Calculations have shown
that up to order 6 this Hopf algebra is isomorphic
to the Hopf algebra of chord diagrams (E.Soboleva),
but that the isomorphism fails to be true starting from
order 7 (A.Kaishev, January 1999). A number of conjectures
concerning the interrelation between the two algebras will
be presented.