Top > 関連資料 > アナウンスメント > 挑戦的研究賞受賞者10




"Polynomial invariants of bipartite graphs"

Dr.KALMAN TAMAS, Associate Professor 
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 RE. 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 IH* = XH and XH* = IH between their interior and exterior polynomials 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.