Graph Theory has proved to be an extremely useful tool for solving combinatorial problems in such diverse areas as Geometry, Algebra, Number Theory, Topology, Operations Research and Optimization. It is natural to attempt to generalise the concept of a graph, in order to attack additional combinatorial problems. The idea of looking at a family of sets from this standpoint took shape around 1960. In regarding each set as a ``generalised edge'' and in calling the family itself a ``hypergraph'', the initial idea was to try to extend certain classical results of Graph Theory such as the theorems of Turán and König. It was noticed that this generalisation often led to simplification; moreover, one single statement, sometimes remarkably simple, could unify several theorems on graphs. This book presents what seems to be the most significant work on hypergraphs.
Author(s): C. Berge
Series: NHML045
Edition: 1
Publisher: North Holland
Year: 1989
Language: English
Pages: 265
Cover......Page 1
Series......Page 2
Title page......Page 3
Copyright page......Page 4
Foreword......Page 5
TABLE OF CONTENTS......Page 6
INDEX OF DEFINITIONS......Page 8
List of standard symbols......Page 10
1. Dual hypergraphs......Page 11
2. Degrees......Page 13
3. Intersecting families......Page 20
4. The coloured edge property and Chvatal's conjecture......Page 25
5. The Helly property......Page 31
6. Section of a hypergraph and the Kruskal-Katona Theorem......Page 36
7. Conformal hypergraphs......Page 40
8. Representative graphs......Page 41
Exercises......Page 49
1. Transversal hypergraphs......Page 53
2. The coefficients $\tau$ and $\tau'$......Page 63
3. $\tau$-critical hypergraphs......Page 69
4. The Koenig property......Page 74
Exercises......Page 82
1. Fractional transversal number......Page 84
2. Fractional matching of a graph......Page 93
3. Fractional transversal number of a regularisable hypergraph......Page 103
4. Greedy transversal number......Page 109
5. Ryser's conjecture......Page 113
6. Transversal number of product hypergraphs......Page 115
Exercises......Page 123
1. Chromatic number......Page 125
2. Particular kinds of colourings......Page 130
3. Uniform colourings......Page 132
4. Extremal problems related to the chromatic number......Page 140
5. Good edge-colourings of a complete hypergraph......Page 147
6. An application to an extremal problem......Page 156
7. Kneser's problem......Page 158
Exercises......Page 160
1. Hypergraphs without odd cycles......Page 165
2. Unimodular hypergraphs......Page 172
3. Balanced hypergraphs......Page 181
4. Arboreal hypergraphs......Page 196
5. Normal hypergraphs......Page 203
6. Mengerian hypergraphs......Page 208
7. Paranormal hypergraphs......Page 218
Exercises......Page 223
Appendix: Matchings and colourings in matroids......Page 227
References......Page 247
