Combinatorial convexity

This book is about the combinatorial properties of convex sets, families of convex sets in finite dimensional Euclidean spaces, and finite points sets related to convexity. This area is classic, with theorems of Helly, Carathéodory, and Radon that go back more than a hundred years. At the same time, it is a modern and active field of research with recent results like Tverberg's theorem, the colourful versions of Helly and Carathéodory, and the $(p, q)$ theorem of Alon and Kleitman. As the title indicates, the topic is convexity and geometry, and is close to discrete mathematics. The questions considered are frequently of a combinatorial nature, and the proofs use ideas from geometry and are often combined with graph and hypergraph theory. The book is intended for students (graduate and undergraduate alike), but postdocs and research mathematicians will also find it useful. It can be used as a textbook with short chapters, each suitable for a one- or two-hour lecture. Not much background is needed: basic linear algebra and elements of (hyper)graph theory as well as some mathematical maturity should suffice. This is an elegant, well written, concise treatment of an attractive and active subject, written by an expert who has made important contributions to the area himself. I am sure this will be a successful textbook. —Noga Alon, Princeton University and Tel Aviv University I think this book is a gem. —János Pach, Rényi Institute of Mathematics, Budapest Cover 1 Title page 4 Copyright 5 Contents 6 Preface 8 Basic concepts 10 Carathéodory’s theorem 18 Radon’s theorem 22 Topological Radon 26 Tverberg’s theorem 30 General position 36 Helly’s theorem 38 Applications of Helly’s theorem 42 Fractional Helly 48 Colourful Carathéodory 50 Colourful Carathéodory again 54 Colourful Helly 58 Tverberg’s theorem again 62 Colourful Tverberg theorem 66 Sarkaria and Kirchberger generalized 70 The Erdős-Szekers theorem 72 The same type lemma 76 Better bound for the Erdős-Szekeres number 80 Covering number, planar case 86 The stretched grid 90 Covering number, general case 96 Upper bound on the covering number 100 The point selection theorem 104 Homogeneous selection 108 Missing few simplices 110 Weak ε-nets 114 Lower bound on the size of weak ε-nets 118 The (p,q) theorem 122 The colourful (p,q) theorem 128 d-intervals 132 Halving lines, havling planes 136 Convex lattice sets 140 Fractional Helly for convex lattice sets 146 Bibliography 152 Index 156 Back Cover 159 "This book is about the combinatorial properties of convex sets, families of convex sets in finite dimensional Euclidean spaces, and finite points sets related to convexity. This area is classic, with theorems of Helly, Carathéodory, and Radon that go back more than a hundred years. At the same time, it is a modern and active field of research with recent results like Tverberg's theorem, the colourful versions of Helly and Carathéodory, and the (p, q) theorem of Alon and Kleitman. As the title indicates, the topic is convexity and geometry, and is close to discrete mathematics. The questions considered are frequently of a combinatorial nature, and the proofs use ideas from geometry and are often combined with graph and hypergraph theory"--Provided by publisher Explores the combinatorial properties of convex sets, families of convex sets in finite dimensional Euclidean spaces, and finite points sets related to convexity. This area is classic, with theorems of Helly, Caratheodory, and Radon that go back more than a hundred years. At the same time, it is a modern and active field of research.