CONTENTS 14.2 Empty Triangles Determined by Points in the Plane,257 143 n Matrices,259 14.4 61 14.5 Dual Shatter Functions and Discrepancy.260 14.6 Exercises.269 Efficient Packing,270 15 Codes,Games,and Entropy 273 151 Codes 273 15.2 Liar Game,276 53 lenure Game,278 15.4 Balancing Vector Game,279 15.5 Nonadaptive Algorithms,281 15.6 Half Liar Game,282 15.7 Entropy,284 15.8 Exercises,289 An Extremal Graph,291 16 Derandomization 293 16.1 The Method of Conditional Probabilities,293 16.2 d-Wise Independent Random Variables in Small Sample Spaces,297 16.3 Exercises,302 Crossing Numbers,Incidences,Sums and Products,303 17 Graph Property Testing 307 17.1 Property Testing.307 17.2 Testing Colorability,308 17.3 Testing Triangle-Freeness,312 17.4 Characterizing the Testable Graph Properties.314 17.5 Exercises,316 Turdn Numbers and Dependent Random Choice,317 Appendix A Bounding of Large Deviations 321 A.1 Chernoff Bounds,321 A.2 Lower Bounds, 330 A.3 Exercises.334 Triangle-Free Graphs Have Large Independence Numbers,336CONTENTS xi 14.2 Empty Triangles Determined by Points in the Plane, 257 14.3 Geometrical Realizations of Sign Matrices, 259 14.4 𝜖-Nets and VC-Dimensions of Range Spaces, 261 14.5 Dual Shatter Functions and Discrepancy, 266 14.6 Exercises, 269 Efficient Packing, 270 15 Codes, Games, and Entropy 273 15.1 Codes, 273 15.2 Liar Game, 276 15.3 Tenure Game, 278 15.4 Balancing Vector Game, 279 15.5 Nonadaptive Algorithms, 281 15.6 Half Liar Game, 282 15.7 Entropy, 284 15.8 Exercises, 289 An Extremal Graph, 291 16 Derandomization 293 16.1 The Method of Conditional Probabilities, 293 16.2 d-Wise Independent Random Variables in Small Sample Spaces, 297 16.3 Exercises, 302 Crossing Numbers, Incidences, Sums and Products, 303 17 Graph Property Testing 307 17.1 Property Testing, 307 17.2 Testing Colorability, 308 17.3 Testing Triangle-Freeness, 312 17.4 Characterizing the Testable Graph Properties, 314 17.5 Exercises, 316 Turán Numbers and Dependent Random Choice, 317 Appendix A Bounding of Large Deviations 321 A.1 Chernoff Bounds, 321 A.2 Lower Bounds, 330 A.3 Exercises, 334 Triangle-Free Graphs Have Large Independence Numbers, 336