School of Mathematical Sciences

Department Colloquium

Schreiber 006, 12:15

Ben-Gurion University

We consider analogs to the following three basic properties of planar graphs, for bipartite planar graphs and for higher dimensional simplicial complexes:

Abstract:

1. Descartes showed that a planar graph with n>2 vertices has at most 3n-6 edges; this follows easily from Euler's formula. What is the analog for d-dimensional complexes embedded in the 2d-sphere?

2. Kuratowski-Wagner theorem characterizes planar graphs as those with neither K_5 nor K_{3,3} as minors. What is the analog for bipartite graphs?

3. Gluck proved that a generic geometric embedding of a planar graph in R^3 is stress-free, namely, the only assignment of weights to the edges (thought as springs) that leaves all vertices in equilibrium is the zero-weights assignment.

Our discussion will include a variation of graph rigidity theory (where rigid edges in Euclidean space are connected by flexible hinges), tailored for bipartite graphs, and higher dimensional balanced complexes, .

Based on joint works with Maria Chudnovsky, Gil Kalai, Isabella Novik and Paul Seymour.

Coffee will be served at 12:00 before the lecture

at Schreiber building 006