Graph Theory and Additive Combinatorics
Exploring Structure and Randomness

An introductory text covering classical and modern developments in graph theory and additive combinatorics, based on Zhao's MIT course.

Yufei Zhao (Author)

9781009310949, Cambridge University Press

Hardback, published 31 August 2023

338 pages
26 x 18.1 x 2.3 cm, 0.76 kg

'This is a wonderful, well-written account of additive combinatorics from the graph theoretic perspective. Zhao skillfully ties in this approach to the usual statements and gives a thorough development of the subject. This book is indispensable for any serious researcher in this area. Beginners will find a thorough account of the subject with plenty of motivation. The more experienced reader will appreciate the authors' insights and elegant development of some difficult ideas.' Andrew Granville, University of Montréal

Using the dichotomy of structure and pseudorandomness as a central theme, this accessible text provides a modern introduction to extremal graph theory and additive combinatorics. Readers will explore central results in additive combinatorics-notably the cornerstone theorems of Roth, Szemerédi, Freiman, and Green-Tao-and will gain additional insights into these ideas through graph theoretic perspectives. Topics discussed include the Turán problem, Szemerédi's graph regularity method, pseudorandom graphs, graph limits, graph homomorphism inequalities, Fourier analysis in additive combinatorics, the structure of set addition, and the sum-product problem. Important combinatorial, graph theoretic, analytic, Fourier, algebraic, and geometric methods are highlighted. Students will appreciate the chapter summaries, many figures and exercises, and freely available lecture videos on MIT OpenCourseWare. Meant as an introduction for students and researchers studying combinatorics, theoretical computer science, analysis, probability, and number theory, the text assumes only basic familiarity with abstract algebra, analysis, and linear algebra.

Preface
Notation and Conventions
Appetizer: triangles and equations
1. Forbidding a subgraph
2. Graph regularity method
3. Pseudorandom graphs
4. Graph limits
5. Graph homomorphism inequalities
6. Forbidding 3-term arithmetic progressions
7. Structure of set addition
8. Sum-product problem
9. Progressions in sparse pseudorandom sets
References
Index.

Subject Areas: Combinatorics & graph theory [PBV], Probability & statistics [PBT], Number theory [PBH], Discrete mathematics [PBD]