Optimisation and hypergraph theory (Q1813951)

For the past fourty years, graph theory has proved to be an extremely useful tool for solving combinatorial problems, in areas as diverse as geometry, algebra, number theory, topology, operations research and optimisation. 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 (between 1962 and 1982). 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: (1) A bipartite graph \(G\) has no odd cycles. (2) The vertices of the bipartite graph can be colored with only two colors, blue and red, so that the neighbours of a blue vertex are red, and the neighbours of a red vertex are blue (the bicolorability property). (3) The edges of a bipartite graph can be colored with a number of colors equal to the maximum degree so that no two adjacent edges have the same color (the `colored edge property'). (4) The least cardinality of a set of vertices which meet all the edges is equal to the maximum number of pairwise disjoint edges (the `König property'). (5) Every family of pairwise intersecting edges has a non-empty intersection (the `Helly property'). Each of these properties has given rise to several extensions for hypergraphs and for \((0,1)\)-matrices. The complexity aspect of these problems will be discussed at another occasion.