Optimisation and hypergraph theory

For the past forty years, Graph Theory has proved to be an extremely useful tool for solving combinatorial problems in diverse areas. It was thus natural to try and 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. Next, it was noticed that this generalisation often led to simplification; moreover, one single statement, sometimes remarkably simple, could unify several theorems on graphs. It is with this concern that we investigated systematically the possible extensions of the main graph theoretical theorems. For the specialist of Operations Research and of Combinatorial Optimisation the concepts developed during this first period got practical applications, and some algorithms associated with very specific structures received a particular interest. The purpose of this paper is to survey various mathematical theorems which were found successively to generalize the most usual properties of bipartite graphs.