6
Extremal combinatorics
CONTENTS
6.1 Extremal graph theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
6.1.1 Bipartite graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
6.1.2 Tur´an’s theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320
6.1.3 Graphs excluding cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324
6.1.3.1 Convex functions and Jensen’s inequality . . . . 326
6.1.3.2 Notation in approximate counting . . . . . . . . . . . 327
6.1.3.3 Refining the results on f
C
4
(n) . . . . . . . . . . . . . . . . 328
6.1.3.4 Avoiding longer cycles . . . . . . . . . . . . . . . . . . . . . . . . 330
6.1.4 Graphs excluding complete bipartite graphs .. . . . . . . . . . . 332
6.2 Hypergraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334
6.2.1 Hypergraphs with pairwise intersecting edges . . . . . . . . . . 335
6.2.1.1 Sunflowers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340
6.2.2 Hypergraphs with pairwise incomparable edges . . . . . . . . 341
6.3 Something is more than nothing: Existence proofs . . . . . . . . . . . . . . 343
6.3.1 Property B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344
6.3.2 Excluding monochromatic arithmetic progressions . . . . . 345
6.3.3 Codes over finite alphabets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346
6.4 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350
6.5 Chapter review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350
6.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351
6.7 Solutions to exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356
6.8 Supplementary exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 368
6.1 Extremal graph theory
Real life is full of optimization problems, that is, we often have to find the
best way to carry out a certain task. This often involves finding the graph
that is best from a specific viewpoint. This is the topic of Extremal Graph
Theory.
315

Get Introduction to Enumerative and Analytic Combinatorics, 2nd Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.