Hypergraphs and Designs

Book excerpt: Combinatorial designs represent an important area of contemporary discrete mathematics closely related to such fields as finite geometries, regular graphs and multigraphs, factorisations of graphs, linear algebra, number theory, finite fields, group and quasigroup theory, Latin squares, and matroids. It has a history of more than 150 years when it started as a collection of unrelated problems. Nowadays the field is a well-developed theory with deep mathematical results and a wide range of applications in coding theory, cryptography, computer science, and other areas. In the most general setting, a combinatorial design consists of a ground set of elements and a collection of subsets of these elements satisfying some specific restrictions; the latter are often expressed in the language of graphs. On the other side, hypergraph theory is a relatively new field which started in early 60s of the last century as a generalization of graph theory. A hypergraph consists of a ground set of elements and a collection of subsets of these elements without any specific restrictions. In this sense the concept of hypergraph is more general than the concept of combinatorial design. While it started as a generalization of graph theory, hypergraph theory soon became a separate subject because many new properties have been discovered that miss or degenerate in graphs. Compared to graph theory, the language of hypergraphs not only allows us to formulate and solve more general problems, it also helps us to understand and solve several graph theory problems by simplifying and unifying many previously unrelated concepts. The main feature of this book is applying the hypergraph approach to the theory of combinatorial designs. An alternative title of it could be "Combinatorial designs as hypergraphs". There is no analogue to this book on the market. Its primary audience is researchers and graduate students taking courses in design theory, combinatorial geometry, finite geometry, discrete mathematics, graph theory, combinatorics, cryptography, information and coding theory, and similar areas. The aim of this book is to show the connection and mutual benefit between hypergraph theory and design theory. It does not intend to give a survey of all important results or methods in any of these subjects.