Английская Википедия:D-interval hypergraph
Шаблон:Short description Шаблон:Distinguish
In graph theory, a Шаблон:Mvar-interval hypergraph is a kind of a hypergraph constructed using intervals of real lines. The parameter Шаблон:Mvar is a positive integer. The vertices of a Шаблон:Mvar-interval hypergraph are the points of Шаблон:Mvar disjoint lines (thus there are uncountably many vertices). The edges of the graph are Шаблон:Mvar-tuples of intervals, one interval in every real line.[1]
The simplest case is Шаблон:Math. 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 Шаблон:Math 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 Шаблон:Mvar-interval hypergraphs just like for finite hypergraphs:
- A matching is a set of non-intersecting edges, i.e., a set of non-intersecting Шаблон:Mvar-intervals. For example, in the 1-interval hypergraph Шаблон:Math the set Шаблон:Math is a matching of size 2, but the set Шаблон:Math is not a matching since its elements intersect. The largest matching size in Шаблон:Mvar is denoted by Шаблон:Math.
- A covering or a transversal is a set of vertices that intersects every edge, i.e., a set of points that intersects every Шаблон:Mvar-interval. For example, in the 1-interval hypergraph Шаблон:Math the set Шаблон:Math is a covering of size 2, but the set Шаблон:Math is not a covering since it does not intersect the edge Шаблон:Math. The smallest transversal size in Шаблон:Mvar is denoted by Шаблон:Math.
Шаблон:Math is true for any hypergraph Шаблон:Mvar.
Tibor Gallai proved that, in a 1-interval hypergraph, they are equal: Шаблон:Math. This is analogous to Kőnig's theorem for bipartite graphs.
Gabor Tardos[1] proved that, in a 2-interval hypergraph, Шаблон:Math, and it is tight (i.e., every 2-interval hypergraph with a matching of size Шаблон:Mvar, can be covered by Шаблон:Math points).
Kaiser[2] proved that, in a Шаблон:Mvar-interval hypergraph, Шаблон:Math, and moreover, every Шаблон:Mvar-interval hypergraph with a matching of size Шаблон:Mvar, can be covered by at Шаблон:Math points, Шаблон:Math points on each line.
Frick and Zerbib[3] proved a colorful ("rainbow") version of this theorem.
References
