Meetings: Mondays and Fridays 4:00pm-5:30pm Math. Sci. Building 3106.

Instructor: Jesús A. De Loera.
email: deloera@math.ucdavis.edu
phone: (530)-554-9702
office: 3228 Mathematical Science building.
office hours: Mondays and Fridays by appointment. A sure way to contact me is via email.

Text: I will use my own notes, which will be freely available (updated weekly below). There is no single textbook that covers all these topics yet, but some excellent references exist for a big chunk of the course. WARNING, my emphasis is much more combinatorial than the third book and much more applied and computational than the first and second books.

-Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry by Matousek, Jiri, Springer, Universitext 2003.

- A Course in Topological Combinatorics by de Longueville, Mark, Springer Universitext, 2013

- Optima and Equilibria: An Introduction to Nonlinear Analysis by Aubin, Jean-Pierre, Springer Graduate Texts in Mathematics.

Course Description: This course is an introduction to techniques from combinatorial geometry and topology that have proved useful to solve problems arising in game theory, mathematical economics, combinatorial optimization, fair-division problems, data analysis and statistics, and voting theory. We will see that the fundamental notions of Optima and Equilibria are inherently combinatorial in nature.

The target audience is meant to be beginning graduate students or very mature and diligent senior undergraduates.

Examples of themes we will discuss include the use of Borsuk-Ulam theorem to prove the Kneser graph coloring conjecture, Lov\'asz Evasiveness of graph properties, or the powerful use of Fixed point theorems to solve problems about dividing fairly a cake or designing a voting schemes. My plan is to cover the following 3 topics. I will develop more or less from scratch the necessary background. After each topic there will be a midterm exam.

Syllabus: Topics will be covered in roughly the following order:

-Part I (weeks 1-3): Combinatorial topology tools: lemmas of Sperner and Fan-Tucker and their consequences: new manifold and polytopal Sperner theorems (three versions), Brouwer Fixed point theorems, Kakutani's Theorem, Borsuk-Ulam, Van Kampen-Flores, Lusternik-Schnirelmann-Borsuk, Markov-Kakutani fixed point theorems.

-Part II (weeks 4-7): Combinatorial Geometry tools: Helly-type results, Carath\'eodory-style theorems, Radon-Tverberg theorems. Weyl-Minkowski's theorem. Separation (e.g, Hahn-Banach, Farkas, KKT), Covering (KKM-Lebesgue covering theorems and their meaning).

-Part III (weeks 8-10) Applications: in Game Theory-Economics (Minmax theorems, Nash-Equilibria, Fair-Division problems, voting theory, HEX), Data analysis (Tucker's depth, center points, Ham-sandwich theorem, e-nets), Optimization (optimality conditions and duality, discrete optimization, chance-constrained optimization, etc), Combinatorics/Hypergraphs (submodular functions, coloring problems, cores, embeddability of graphs).

Grading and Work: The final grades will be based on two things:

-Three Midterms, one after each topic covered. Based on homeworks, each 40 points, dropping the lowest score.

The midterms will be 5 problems each and mostly based in the homework I assigned each class. So while homework is not collected regularly, it is crucial you work on it regularly!

-Notes-scribe work 20 points for two of the lectures. Note-scribe work means that students will be responsible to render a nice latex presentation of a topic discussed in class. The student is responsible for filling some details I skipped in class (with my help).

Here is the LaTeX template you must use to write the lectures.

A free version of the current lecture notes version of February 16th 2016 is available here

Slides I used in lecture 2 first set and second set