On the König-Hall-Egerváry theorem for multidimensional matrices and multipartite hypergraphs

Abstract

One of possible interpretations of the well-known König--Hall--Egerváry theorem is a full characterization of all bipartite graphs extremal for fractional matchings of a given weight (or, equivalently, a characterization of $(0,1)$-matrices extremal for partial fractional diagonals of a given length). In this paper we initiate the study of $d$-partite $d$-uniform hypergraphs that are extremal for fractional perfect matchings (or, equivalently, $d$-dimensional $(0,1)$-matrices that are extremal for polydiagonals). For this purpose, we analyze similarities and differences between $2$-dimensional and multidimensional cases and put forward a series of questions and conjectures on properties of multidimensional extremal matrices (extremal hypergraphs). We also prove these conjectures for several parameters and provide a number of supporting constructions and examples.

many minor changes