Polynomial Methods in Combinatorics (University Lecture Series) (University Lecture, 64)

This book explains some recent applications of the theory of polynomials and algebraic geometry to combinatorics and other areas of mathematics. One of the first results in this story is a short elegant solution of the Kakeya problem for finite fields, which was considered a deep and difficult problem in combinatorial geometry. The author also discusses in detail various problems in incidence geometry associated to Paul Erdős's famous distinct distances problem in the plane from the 1940s. The proof techniques are also connected to error-correcting codes, Fourier analysis, number theory, and differential geometry. Although the mathematics discussed in the book is deep and far-reaching, it should be accessible to first- and second-year graduate students and advanced undergraduates. The book contains approximately 100 exercises that further the reader's understanding of the main themes of the book. Some of the greatest advances in geometric combinatorics and harmonic analysis in recent years have been accomplished using the polynomial method. Larry Guth gives a readable and timely exposition of this important topic, which is destined to influence a variety of critical developments in combinatorics, harmonic analysis and other areas for many years to come. —Alex Iosevich, University of Rochester, author of “The Erdős Distance Problem” and “A View from the Top” It is extremely challenging to present a current (and still very active) research area in a manner that a good mathematics undergraduate would be able to grasp after a reasonable effort, but the author is quite successful in this task, and this would be a book of value to both undergraduates and graduates. —Terence Tao, University of California, Los Angeles, author of “An Epsilon of Room I, II” and “Hilbert's Fifth Problem and Related Topics” 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 \RR3 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 G 9.5. Applying incidence geometry of lines to partial symmetries 9.6. The lines of \frakL(P) 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 \RR3 10.7. An estimate for r-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 L^{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. L^{p} 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 This book explains some recent applications of the theory of polynomials and algebraic geometry to combinatorics and other areas of mathematics. One of the first results in this story is a short elegant solution of the Kakeya problem for finite fields, which was considered a deep and difficult problem in combinatorial geometry. The author also discusses in detail various problems in incidence geometry associated to Paul Erdos's famous distinct distances problem in the plane from the 1940s. The proof techniques are also connected to error-correcting codes, Fourier analysis, number theory, and differential geometry. Although the mathematics discussed in the book is deep and far-reaching, it should be accessible to first- and second-year graduate students and advanced undergraduates. The book contains approximately 100 exercises that further the reader's understanding of the main themes of the book. Introduction -- Fundamental Examples Of The Polynomial Method -- Why Polynomials? -- Polynomial Method In Error-correcting Codes -- On Polynomials And Linear Algebra In Combinatorics -- Bezout Theorem -- Incidence Geometry -- Incidence Geometry In Three Dimensions -- Partial Symmetrics -- Polynomial Partitioning -- Combinatoral Structure, Algebraic Structure, And Geometric Structure -- An Incidence Bound For Lines In Three Diemnsions -- Ruled Surfaces And Projection Theory -- Polynomial Method In Differential Geometry -- Harmonic Analysis And The Kakeya Problem -- Polynomial Method In Number Theory. Larry Guth. Includes Bibliographical References.