Existential Polytime and Polyhedral Combinatorics

Two minicourses by Jack Edmonds in London, June 2015

For thousands of years the beautiful symmetries of a handful of polyhedra with few dimensions and facets have been at the center of elite mathematics. Since the advent of Turing's computers and modern management, the beauty of higher math has been found in polyhedra regardless of symmetry, with dimensions and facets numerous as the stars. The theory of linear algebra is being nudged by great systems of linear inequalities as inputs. ‘Polyhedra’ means their solution sets. ‘Existential polytime’, i.e. NP, means reasonable to prove when true.

Two courses of about 8 hours each, on NP and Polyhedral Combinatorics, will explore some of the polyhedra which have edged aside the dodecahedron.

The two courses will be independent. The first is not a prerequisite for the second.

The first course

Combinatorial structure of paths, marriage, routes for Chinese postmen, traveling salesmen, and itinerant preachers, optimum systems of trees and branchings.

Queen Mary University of London, in room Maths 103. Tues 16th – Fri 19th June, 10:00–12:00.

Please indicate your interest in attending to Alex Fink.

The second course

Combinatorial structure of submodularity, matroids, learning, transferable & other n-person games, bimatrix games and beautiful-mind Nash equilibria.

An Intensive at the London Taught Course Centre. Room 505, Dept. of Mathematics, 25 Gordon Street, UCL. Mon 22nd June, 13:00–17:00, and Tues 23rd June, 9:00–13:00.

Contact: Nisha Jones.

Jack Edmonds, 34, the teacher, is the Dumbledore, Gandalf, Merlin, Obi-Wan Kenobi of the subject. Muggles are welcome.
Alex Fink will contribute segments on matroid polytope subdivisions. Alex's notes are available here.

Related resources include books on Combinatorial Optimization, Game Theory, and Computing Theory, such as Schrijver, Combinatorial Optimization: Polyhedra and Efficiency; Grötschel (ed.), Optimization Stories. See also a recent interview with Jack by Optima, the Mathematical Optimization Society.