Polynomial Methods in Combinatorics

✍ Scribed by Larry Guth

• Publisher: American Mathematical Society
• Year: 2016
• Tongue: English
• Leaves: 287
• Series: University Lecture Series, Volume 64
• Category: Library

✦ Table of Contents

Cover
Title page
Contents
Preface
Chapter 1. Introduction
1.1. Incidence geometry
1.2. Connections with other areas
1.3. Outline of the book
1.4. Other connections between polynomials and combinatorics
1.5. Notation
Chapter 2. Fundamental examples of the polynomial method
2.1. Parameter counting arguments
2.2. The vanishing lemma
2.3. The finite-field Nikodym problem
2.4. The finite field Kakeya problem
2.5. The joints problem
2.6. Comments on the method
2.7. Exercises
Chapter 3. Why polynomials?
3.1. Finite field Kakeya without polynomials
3.2. The Hermitian variety
3.3. Joints without polynomials
3.4. What is special about polynomials?
3.5. An example involving polynomials
3.6. Combinatorial structure and algebraic structure
Chapter 4. The polynomial method in error-correcting codes
4.1. The Berlekamp-Welch algorithm
4.2. Correcting polynomials from overwhelmingly corrupted data
4.3. Locally decodable codes
4.4. Error-correcting codes and finite-field Nikodym
4.5. Conclusion and exercises
Chapter 5. On polynomials and linear algebra in combinatorics
Chapter 6. The Bezout theorem
6.1. Proof of the Bezout theorem
6.2. A Bezout theorem about surfaces and lines
6.3. Hilbert polynomials
Chapter 7. Incidence geometry
7.1. The Szemerédi-Trotter theorem
7.2. Crossing numbers and the Szemerédi-Trotter theorem
7.3. The language of incidences
7.4. Distance problems in incidence geometry
7.5. Open questions
7.6. Crossing numbers and distance problems
Chapter 8. Incidence geometry in three dimensions
8.1. Main results about lines in \RR³
8.2. Higher dimensions
8.3. The Zarankiewicz problem
8.4. Reguli
Chapter 9. Partial symmetries
9.1. Partial symmetries of sets in the plane
9.2. Distinct distances and partial symmetries
9.3. Incidence geometry of curves in the group of rigid motions
9.4. Straightening coordinates on 𝐺
9.5. Applying incidence geometry of lines to partial symmetries
9.6. The lines of \frak𝐿(𝑃) don’t cluster in a low degree surface
9.7. Examples of partial symmetries related to planes and reguli
9.8. Other exercises
Chapter 10. Polynomial partitioning
10.1. The cutting method
10.2. Polynomial partitioning
10.3. Proof of polynomial partitioning
10.4. Using polynomial partitioning
10.5. Exercises
10.6. First estimates for lines in \RR³
10.7. An estimate for 𝑟-rich points
10.8. The main theorem
Chapter 11. Combinatorial structure, algebraic structure, and geometric structure
11.1. Structure for configurations of lines with many 3-rich points
11.2. Algebraic structure and degree reduction
11.3. The contagious vanishing argument
11.4. Planar clustering
11.5. Outline of the proof of planar clustering
11.6. Flat points
11.7. The proof of the planar clustering theorem
11.8. Exercises
Chapter 12. An incidence bound for lines in three dimensions
12.1. Warmup: The Szemerédi-Trotter theorem revisited
12.2. Three-dimensional incidence estimates
Chapter 13. Ruled surfaces and projection theory
13.1. Projection theory
13.2. Flecnodes and double flecnodes
13.3. A definition of almost everywhere
13.4. Constructible conditions are contagious
13.5. From local to global
13.6. The proof of the main theorem
13.7. Remarks on other fields
13.8. Remarks on the bound 𝐿^{3/2}
13.9. Exercises related to projection theory
13.10. Exercises related to differential geometry
Chapter 14. The polynomial method in differential geometry
14.1. The efficiency of complex polynomials
14.2. The efficiency of real polynomials
14.3. The Crofton formula in integral geometry
14.4. Finding functions with large zero sets
14.5. An application of the polynomial method in geometry
Chapter 15. Harmonic analysis and the Kakeya problem
15.1. Geometry of projections and the Sobolev inequality
15.2. 𝐿^{𝑝} estimates for linear operators
15.3. Intersection patterns of balls in Euclidean space
15.4. Intersection patterns of tubes in Euclidean space
15.5. Oscillatory integrals and the Kakeya problem
15.6. Quantitative bounds for the Kakeya problem
15.7. The polynomial method and the Kakeya problem
15.8. A joints theorem for tubes
15.9. Hermitian varieties
Chapter 16. The polynomial method in number theory
16.1. Naive guesses about diophantine equations
16.2. Parabolas, hyperbolas, and high degree curves
16.3. Diophantine approximation
16.4. Outline of Thue’s proof
16.5. Step 1: Parameter counting
16.6. Step 2: Taylor approximation
16.7. Step 3: Gauss’s lemma
16.8. Conclusion
Bibliography
Back Cover