In graph theory, a -interval hypergraph is a kind of a hypergraph constructed using intervals of real lines. The parameter is a positive integer. The vertices of a -interval hypergraph are the points of disjoint lines (thus there are uncountably many vertices). The edges of the graph are -tuples of intervals, one interval in every real line.[1]
The simplest case is . The vertex set of a 1-interval hypergraph is the set of real numbers; each edge in such a hypergraph is an interval of the real line. For example, the set defines a 1-interval hypergraph. Note the difference from an interval graph: in an interval graph, the vertices are the intervals (a finite set); in a 1-interval hypergraph, the vertices are all points in the real line (an uncountable set).
As another example, in a 2-interval hypergraph, the vertex set is the disjoint union of two real lines, and each edge is a union of two intervals: one in line #1 and one in line #2.
The following two concepts are defined for -interval hypergraphs just like for finite hypergraphs:
is true for any hypergraph .
Tibor Gallai proved that, in a 1-interval hypergraph, they are equal: . This is analogous to Kőnig's theorem for bipartite graphs.
Gabor Tardos proved that, in a 2-interval hypergraph,, and it is tight (i.e., every 2-interval hypergraph with a matching of size, can be covered by points).
Kaiser[2] proved that, in a -interval hypergraph,, and moreover, every -interval hypergraph with a matching of size, can be covered by at points, points on each line.
Frick and Zerbib[3] proved a colorful ("rainbow") version of this theorem.