### Seminar on classic results, Spring 2017

Books

1914 Walter Crane

#### When:

Wednesdays 10:30–noon and 5:00–approx. 6:00#### Where:

Wean Hall 6202#### What:

Math is pretty, and much of its beauty lies sleeping on the pages of classic papers. The aim of this course is to have fun reading mathematics, and to explain it to each other. Each week, one of the students presents a topic of their choice to an inquisitive group of peers. Fun ensues.

The seminar takes places in two session of total length of 2.5 hours. This permits detailed examination of arguments, exploration of side arguments, and lots of discussion.

Below is a list of potential topics, combining my suggestions with those of the students. Additions are welcome.

Ramsey theory | |||
---|---|---|---|

Euclidean Ramsey theory | |||

All triangles are Ramsey | Frankl and Rödl | MathSciNet | |

A partition property of simplices in Euclidean space | Frankl and Rödl | ||

Strong Ramsey properties of simplices | Frankl and Rödl | MathSciNet | |

Permutation groups in Euclidean Ramsey theory | Kříž | MathSciNet | |

Hales--Jewett-type approach to Euclidean Ramsey theory: | |||

Transitive Sets in Euclidean Ramsey Theory | Leader, Russell, Walters | arXiv | |

Transitive Sets and Cyclic Quadrilaterals | Leader, Russell, Walters | arXiv | |

Arithmetic combinatorics | |||

Solutions to linear equations | |||

Linear problems in combinatorial number theory | Komlós, Sulyok, Szemerédi | MathSciNet | |

Solving a linear equation in a set of integers. I and II | Ruzsa | MathSciNet MathSciNet | |

Three-term arithmetic progressions | |||

On subsets of finite abelian groups with no 3-term arithmetic progressions. | Meshulam | MathSciNet | |

On large subsets of F_{q}^{n} with no three-term arithmetic progression | Ellenberg and Gijswijt | arXiv | |

A symmetric formulation of the Croot-Lev-Pach-Ellenberg-Gijswijt capset bound | Tao | blog | |

Extremal (hyper)graph theory | |||

Complexity | |||

Undecidability of linear inequalities in graph homomorphism densities | Hatami and Norine | arXiv | |

Probabilistic combinatorics | |||

Algorithmic local lemma | |||

A constructive proof of the general Lovasz Local Lemma | Moser and Tardós | arXiv | |

Entropy compression argument | Tao | blog | |

(Application) A new approach to nonrepetitive sequences | Grytczuk, Kozik, Micek | arXiv | |

Hypergraph containers | |||

Counting independent sets in graphs | Samotij | ||

Simple containers for simple hypergraphs | Saxton and Thomason | arXiv | |

Independent sets in hypergraphs | Balogh, Morris, and Samotij | ||

Removal and regularity lemmas | |||

Graph removal lemmas | Conlon and Fox | arXiv | |

A short proof of Gowers' lower bound for the regularity lemma | Moshkovitz and Shapira | arXiv | |

Algebraic methods | |||

Linear algebra method | |||

Intersection theorems with geometric consequences | Frankl and Wilson | MathSciNet | |

Counterexample to Borsuk's conjecture | Kahn and Kalai | MathSciNet | |

On the number of zero-patterns of a sequence of polynomials | Rónyai, Babai, Ganapathy | MathSciNet | |

Random polynomial constructions | |||

Random algebraic construction of extremal graphs | Bukh | arXiv | |

Rational exponents in extremal graph theory | Bukh and Conlon | arXiv | |

Extrapolation | |||

On the size of Kakeya sets in finite fields | Dvir | arXiv | |

The joints problem in R^{n} | Quilodrán | arXiv | |

Slice rank method | |||

On large subsets of F_{q}^{n} with no three-term arithmetic progression | Ellenberg and Gijswijt | arXiv | |

A symmetric formulation of the Croot-Lev-Pach-Ellenberg-Gijswijt capset bound | Tao | blog | |

Notes on “slice rank” of tensors | Tao and Sawin | blog | |

Extremal combinatorics | |||

Entropy method | |||

An entropy proof of the Kahn-Lovász theorem | Cutler and Radcliffe | MathSciNet | |

An entropy approach to the hard-core model on bipartite graphs | Kahn | MathSciNet | |

The number of independent sets in a regular graph | Zhao | arXiv | |

Discrepancy theory | |||

Combinatorial discrepancy | |||

Six standard deviations suffice | Spencer | MathSciNet | |

Constructive discrepancy minimization by walking on the edges | Lovett and Meka | arXiv | |

Factorization norms and hereditary discrepancy | Matoušek, Nikolov and Talwar | arXiv | |

Algorithms | |||

Semidefinite programming | |||

Approximating cut-norm via Grothendieck's inequality | Alon and Naor | MathSciNet |

#### Schedule

- January 18: Introduction of the topics
- January 25 (Ziye): Algorithmic local lemma
- February 1 (Da Qi): Euclidean Ramsey Theory
- February 8 (Mihir): Linear Algebra Method
- February 15 (Sasha): Hypergraph containers
- February 22 (Ziye): Algorithmic local lemma (random walk/local improvements)
- March 1 (Da Qi): Hales--Jewett-type approach to Euclidean Ramsey theory
- March 8 (Mihir): Random polynomial constructions
- March 15:
*Spring break* - March 22 (Sasha): Slice-rank
- March 29 (Ziye): Entropy method
- April 5:
*No meeting* - April 12:
*No meeting* - April 19 (Da Qi): Discrepancy theory
- April 26 (Mihir): Solutions to linear equations
- May 3:
*No meeting* - May 10 (Sasha): Removal and regularity lemmas