**関連資料**

**アナウンスメント**

**「挑戦的研究賞」の受賞者紹介10**

### "Polynomial invariants of bipartite graphs"

Dr.KALMAN TAMAS, Associate Professor

Graduate School of Science and Engineering Mathematics

Graduate School of Science and Engineering Mathematics

My background as a mathematician is in Topology, that is the study of space, with an emphasis on the phenomenon of “knottedness” in space. This is a fascinating area that guides most of my work, including the results that I summarize below. The results themselves however belong to a different field called Algebraic Combinatorics. While I am not aware of their practical uses yet, I anticipate that such will eventually be found.

A *graph* (that is, a system of edges that connect nodes) is a mathematical abstraction of a real-life “network”
- of people, of computers, of transportation routes etc. I found three new ways of measuring the complexity
of a particular kind of graph called bipartite. These are graphs with two kinds of nodes forming so-called
color classes so that edges only exist between nodes of opposite color.

The three new quantities are not just numbers, rather finite sequences of positive integers which are arranged
to be the coefficients of polynomials. Each bipartite graph has one ‘interior’ and two ‘exterior’ polynomials.
This is because in the construction of the invariants, the symmetry between the color classes is broken: one is
viewed as the set of vertices and the other as the set of hyperedges (which are just some collections of vertices)
in a structure called *hypergraph*. Thus there are two hypergraphs, and both have an interior and an exterior
polynomial. In the case of the latter, they are typically different. On the other hand, in joint work with A.
Postnikov we have proved that the interior polynomials of the two hypergraphs coincide.

I sketch the definition below. (This can be of interest because the same ideas extend to the case of so-called
*polymatroids*. Those are important objects in the field of Combinatorial Optimization, which is concerned with
practical problems such as effective algorithm design.) Let* H* be a hypergraph with vertex set *V* and hyperedge
set *E*. We consider spanning trees (connected and cycle-free subgraphs) of the corresponding bipartite graph
and their degree distributions at nodes belonging to E, so that we obtain vectors in the space R* ^{E}*. Let us call
these vectors the hypertrees of

*H*. (The set of hypertrees is in fact the set of so-called integer bases in a certain polymatroid.)

Next, we choose an arbitrary order on the set *E* and use it to define two statistics on the set of hypertrees.
Namely, we call a hyperedge *e* internally active with respect to a hypertree *f* if it is not possible to find a new
hypertree by decreasing the *e*-ccordinate of *f* by 1 and adding 1 to another coordinate that comes before *e* in
the order. Similarly, we call e externally active with respect to f if it is not possible to increase the e-ccordinate
of *f* and simultaneously decrease a coordinate of smaller index so that another hypertree results.

For each hypertree (integer base) we count the number of internally and externally active hyperedges
(ground set elements). For both of these statistics, it is true that if we group hypertrees (bases) according
to their value then the sizes of the resulting groups do not depend on the order of *E* that we used. It is these
sizes that become the coefficients of the interior and exterior polynomials.

**Left**: a polymatroid (on a three-element ground set).

**Middle**: A hypertree (base) polytope (with four hyperedges), indicating the distribution of interior activity.

**Right**: a planar hypergraph and its dual.

These quantitities have remarkable properties beyond order-independence and the ‘abstract duality’ theorem
mentioned above. They are related to the so-called Homfly polynomial of alternating knots (which we showed
with H. Murakami), as well as to Floer homology groups of some associated three-dimensional manifolds (this
was established in joint work with A. Juhasz and J. Rasmussen), which is exciting from the point of view of
finding a natural, geometric description of the Homfly polynomial. But in order to remain within the realm
of discrete mathematics, I end this summary with a ‘planar duality’ formula for hypergraphs whose associated
bipartite graph can be drawn on the plane without the edges crossing. In that situation, we may keep the same
set of hyperedges but replace the set of vertices with the set of regions of the diagram. See the Figure for an
example. For the resulting pair *H*, *H ^{*}* of hypergraphs, we obtain the relations

*I*=

_{H*}*X*and

_{H}*X*=

_{H*}*I*between their interior and exterior polynomials

_{H}*I*and

*X*.

Both this property and the definition mimic a classical graph (and matroid) invariant named *Tutte polynomial*.
The fact that the latter appears in Statistical Mechanics as the so-called partition function of the Potts
model may hint at another avenue for fruitful application. In closing, let me reiterate my hope that the ideas
outlined here, abstract as they may be, will find concrete connections to everyday problems in the near future.