Abstract: We consider analogs to the following three basic properties of planar graphs, for bipartite planar graphs and for higher dimensional simplicial complexes:
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