D-interval hypergraph

Not to be confused with interval graph.

In graph theory, a d-interval hypergraph is a kind of a hypergraph constructed using intervals of real lines. The parameter d is a positive integer. The vertices of a d-interval hypergraph are the points of d disjoint lines (thus there are uncountably many vertices). The edges of the graph are d-tuples of intervals, one interval in every real line.

The simplest case is d = 1. 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 { [-2, -1], [0, 5], [3, 7] } 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 d-interval hypergraphs just like for finite hypergraps:

• A matching is a set of non-intersecting edges, i.e., a set of non-intersecting d-intervals. For example, in the 1-interval hypergraph { [-2, -1], [0, 5], [3, 7] }, the set { [-2, -1], [0, 5] } is a matching of size 2, but the set { [0,5], [3,7] } is not a matching since its elements intersect.
• A covering or a transversal is a set of vertices that intersects every edge, i.e., a set of points that intersects every d-interval. For example, in the 1-interval hypergraph { [-2, -1], [0, 5], [3, 7] }, the set {-1.5, 4 } is a covering of size 2, but the set {-1.5, 1} is not a covering since it does not intersect the edge [3,7].

Tibor Gallai proved that, in a 1-interval, the size of the largest matching equals the size of the smallest covering; this is analogous to Konig's theorem for bipartite graphs.