User Tools

Site Tools


Konstantin Rybnikov (Cornell)

Gain Graphs and Polyhedral Geometry

Abstract for the Combinatorics and Number Theory Seminar 2001 April 18

A gain graph is a triple (G,h,H) where G is a graph, H is a group, and h is a homomorphism from the free group on the edges of G to H. Gain graphs appear in physics, rigidity theory, geometry of polytopes, graph theory, operations research, etc. An ordered cycle in G is called balanced if it lies in the kernel of h. A gain graph is called balanced if all its cycles are balanced. For some choices of H, I will give necessary and sufficient conditions for a gain graph (G,h,H) to be balanced. For example, if H is free abelian, then (G,h,H) is balanced if and only if all elements of an arbitrary basis of its binary cycle space are balanced. This is also true for any H such that its abelianization is infinite and torsion-free. However, if the abelianization of H is finite, our criterion does not work.

The case of torsion-free abelian H is important to polyhedral geometry and physics. I will describe applications of our criterion to recognizing if a given polyhedral partition of a domain in n-space can be lifted to a convex surface. If time permits, I'll describe applications to computing the dimension of the space of Crr-1-splines over a cell-decomposition of a domain D in n-space with H1(D)=0.

This is a joint ongoing work with Tom Zaslavsky.

seminars/comb/abstract.200104ryb.txt · Last modified: 2020/01/29 14:03 (external edit)