Polynomial Methods in Combinatorics

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