102. Relationships between the geometry of graph polytopes and graph structure
Invited abstract in session WF-2: Combinatorial Optimization II, stream Discrete Optimization.
Wednesday, 16:45 - 18:15Room: C 103
Authors (first author is the speaker)
| 1. | Lilla Tothmeresz
|
| Department of Operations Research, ELTE Eötvös Loránd University | |
| 2. | Tamas Kalman
|
| Tokyo Institute of Technology |
Abstract
The symmetric edge polytope is a lattice polytope associated to a graph, that is actively investigated both because of its beautiful geometry, and also because of its connections to applications. One of these applications is the Kuramoto synchronization model of physics, investigating interacting oscillators, whose interactions are modelled by a graph. By Charney, Chen and Davies, an upper bound on the number of steady states can be obtained from the volume of the symmetric edge polytope.
One can also investigate „non-symmetric” edge polytopes, that are assigned to directed graphs instead of undirected ones. Moreover, one can even generalize them to regular (oriented) matroids. For these more general polytopes, many interesting geometric phenomena uncover themselves that are hidden for symmetric edge polytopes.
We would like to demonstrate that the geometric properties of (graph and matroid) edge polytopes are connected to deep graph/matroid-theoretic properties. In particular, we show that the co-degree of an edge polytope is equal to the minimal cardinality of a dijoin.
Other notions of combinatoral optimization also turn up naturally with respect to edge polytopes. In particular, for an Eulerian directed graph, the complements of arborescences rooted at a given vertex form a triangulation of the edge polytope of the cographic matroid. It would be nice to see if matroid duality has other interesting consequences for these polytopes.
Keywords
- Linear and nonlinear optimization
Status: accepted
Back to the list of papers