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	pdf
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ⁿ 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	pdf
Simple containers for simple hypergraphs	Saxton and Thomason	arXiv
Independent sets in hypergraphs	Balogh, Morris, and Samotij	pdf
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ⁿ	Quilodrán	arXiv
Slice rank method
On large subsets of F_qⁿ 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

Boris Bukh

Teaching