Using Intuitive Geometry

Math 890, Tuesday + Thursday 14:10 - 15:25, Thornton Hall 211, SFSU

Office Hours: Tue 15:30-16:30, Thornton Hall 948

Lecture Outline

• visualizing numbers (Gauss sum formula, lattice points in triangles, staircases, Dedekind sums)
  • Lecture 1
  • Lecture 2
• polytopes (H- and V-description, faces, permutahedron)
  • Lecture 3 + 4 (lecture notes TBD) Slides
• linear programming (Fourier-Motzkin eliminiation, Farkas lemma, LP duality, simplex algorithm, combinatorial optimization)
  • Lecture 5 (lecture notes TBD) Slides
  • Lecture 6 (lecture notes TBD) Slides
  • Lecture 7 (lecture notes TBD) Slides
• game theory (minimax theorem, Nash equilibria, spatial voting)
  • Lecture 8 (lecture notes TBD) Slides
  • Lecture 9 (lecture notes TBD) Slides
• topological combinatorics (Brouwer's fixpoint theorem, Sperner lemma, ham sandwich splitting, fair division)
  • Lecture 10 (lecture notes TBD) Slides
  • Lecture 11+12 (lecture notes TBD) Slides
• Ehrhart theory, lattice points in polyhedra (Ehrhart's theorem, Ehrhart-Macdonald reciprocity, Stanley non-negativity, combinatorial applications)
  • Lecture 13+14 Slides
  • Lecture 15+16 Slides
• formal power series (power series as lattice point sets and vice versa, enumeration of lattice points using formal power series)
  • Lecture 17+18 Slides
  • Lecture 19 Slides
• artificial intelligence (support vector machines, kernel trick, VC dimension)

Exercises

Exercises are handed out on Thursdays and due one week later on Thursdays.

• Exercise 1 (due September 1st)
• Exercise 2 (due September 8th)
  • In problem 1 you can assume that the poset is finite.
• Exercise 3 (due September 15th)
• Exercise 4 (due September 22nd)
• Exercise 5 (due September 29th)
• Exercise 6 (due October 6th)
• Exercise 7 (due October 13th)
• Exercise 8 (due October 25th !!!)
• Exercise 9 (due November 3rd)

Seminar

Schedule

Nov 3rd	Mordell-Pommersheim
Nov 8th	Borsuk-Ulam
Nov 10th	LP Modelling
Nov 15th	Interior Point Methods
Nov 17th	Integer Programming
Nov 29th	Order Polynomials
Dec 1st	P-Partitions

Talks will be given by each student in the last 5 weeks of the semester. Each talk will last 75 minutes, including discussion. There will be 1-2 students presenting each talk.

Generally, there are two different types of talks listes below:

• In-depth talks on one very narrow subject, typically a particular theorem with proof.
• Survey talks covering a wider area. Here you have to make a careful selection what to present, to give a general idea of the topic.

In both cases, the goal is to give an interesting mathematical presentation and it is the student's job to select and prepare the material accordingly. Students are encouraged to review further sources, in addition to the ones listed here.

The following is a list of available seminar talk topics.

Talk 1: The Mordell-Pommersheim Tetrahedron

This talk has been assigned.

As we have seen, already the set of lattice points in rectangular triangles has a rich structure. This talk is about the set of lattice points in rational rectangular tetrahedra. A Theorem of Mordell and Pommersheim gives a description of their Ehrhart function.

Source: Computing the Continuous Discretely. Beck, Robins. 2007. Chapter 8.

Talk 2: Power Indices and Spatial Power Indices

This is a game theory talk, focusing on voting procedures. Power indices are a measure of the "power" voters have in a particular voting system. Spatial power indices are an extension of these ideas to spatial voting. Both of these concepts should be presented in this talk.

Source: Power and Stability in Politics. Straffin. In: Handbook of Game Theory Volume 2. Chapter 32. 1994.

Talk 3: LP and MIP Modelling Tricks

This talk has been assigned.

We have seen that linear programs and mixed integer programs are powerful tools for modelling combinatorial problems. There is a whole bunch of tricks for translating combinatorial problems into the geometric language of linear and integer programs. This talk is about a few of these modelling tricks.

Source: AIMMS Optimization Modelling. Bisschop. 2011. link

Talk 4: Interior Point Methods

This talk has been assigned.

We met the Simplex Algorithm for the solution of linear programming problems during the lecture. This talk is about a different approach to solving these problems, called interior point or barrier methods. These methods can also be applied to more general classes of problems, e.g., quadratic optimization problems.

Sources: The integer-point revolution in optimization: History, recent developments, and lasting consequences. Wright. 2004. link Learning with Kernels. Schölkopf, Smola. 2002. Chapter 6.

Talk 5: The Borsuk-Ulam Theorem and Ham Sandwich Splitting

This talk has been assigned.

We have already met Brouwer's Fixpoint Theorem in the Lecture, seen how it is connected to the Duality Theorem of linear programming and the Minimax theorem of game theory and used it to split ham sandwiches unevenly. This talk is about a more powerful topological tool, the Borsuk-Ulam theorem and several combinatorial applications, including necklace splitting and the Kneser conjecture.

Source: Using the Borsuk-Ulam Theorem. Matousek. 2003. Chapters 2 and 3.

Talk 6: Integer Programming Methods

This talk has been assigned.

We have talked about methods how to solve linear programs. Many combinatorial problems require the use of integer programs, however, which are significantly harder to solve. This talk will give a brief overview of solution methods for integer programs, in particular cutting planes and branch-and-bound.

Source: Theory of Linear and Integer Programming. Schrijver. 1986. Chapters 23 and 24. Lineare und Ganzzahlige Programmierung. Grötschel. 2010. Chapters 15 and 17.

Talk 7: Order Polynomials

This talk has been assigned.

One of the classic combinatorial reciprocity theorems is Stanley's reciprocity theorem for order polynomials. This theorem, its proof and the geometry behind it are the subject of this talk.

Source: Combinatorial Reciprocity Theorems. Beck. 2011. Chapter 6. link Ordered Structures and Partitions. Stanley. 1971. link Computing the Continuous Discretely. Beck, Robins. 2007. Chapter 8.

Talk 8: $P$$P$-Partitions

This talk has been assigned.

This talk builds to some extent on the previous talk about order polynomials. $P$$P$-paritions are integer partitions constrained by a given poset $P$$P$. In this talk a reciprocity theorem for the quasipolynomials counting these objects is derived.

Source: Combinatorial Reciprocity Theorems. Beck. 2011. Chapter 7. link Ordered Structures and Partitions. Stanley. 1971. link Combinatorial Reciprocity Theorems. Stanley. 1974. link Computing the Continuous Discretely. Beck, Robins. 2007. Chapter 8.

Talk 9: Stapledon's $a$$a$ and $b$$b$ vectors

We have already seen and interpreted various coefficient vectors of the Ehrhart polynomial. Stapledon recently proposed a new representation of the Ehrhart polynomial in terms of so-called a and b vectors. This idea led to the discovery of new bounds on the coefficients of the Ehrhart polynomial. These results are the subject of this talk.

Source: Inequalities and Ehrhart $\mathit{\delta }$$\delta$-vectors. Stapledon. 2008. link

Talk 10: Principal Component Analysis

Principal component analysis (PCA) is a classic method for discovering the geometry of (high-dimensional) data. Kernel PCA is an extension of this method, inspired by SVMs, that does away with the implicit assumption of linearity in classic PCA. This talk gives an overview of these two methods.

Source: Learning with Kernels. Schölkopf, Smola. 2002. Chapter 14.