graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, a -interval hypergraph is a kind of a

hypergraph In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices. Formally, an undirected hypergraph H is a pair H = (X,E) ...

constructed using

intervals Interval may refer to: Mathematics and physics * Interval (mathematics), a range of numbers ** Partially ordered set#Intervals, its generalization from numbers to arbitrary partially ordered sets * A statistical level of measurement * Interval est ...

real line In elementary mathematics, a number line is a picture of a graduated straight line that serves as visual representation of the real numbers. Every point of a number line is assumed to correspond to a real number, and every real number to a po ...

s. The parameter is a

positive integer In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called '' cardinal ...

. The '' vertices'' of a -interval hypergraph are the points of disjoint

lines Line most often refers to: * Line (geometry), object with zero thickness and curvature that stretches to infinity * Telephone line, a single-user circuit on a telephone communication system Line, lines, The Line, or LINE may also refer to: Arts ...

(thus there are

uncountably many In mathematics, an uncountable set (or uncountably infinite set) is an infinite set that contains too many elements to be countable. The uncountability of a set is closely related to its cardinal number: a set is uncountable if its cardinal numb ...

vertices). The ''edges'' of the graph are -

tuple In mathematics, a tuple is a finite ordered list (sequence) of elements. An -tuple is a sequence (or ordered list) of elements, where is a non-negative integer. There is only one 0-tuple, referred to as ''the empty tuple''. An -tuple is defi ...

s of intervals, one interval in every real line. 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 graph theory, an interval graph is an undirected graph formed from a set of intervals on the real line, with a vertex for each interval and an edge between vertices whose intervals intersect. It is the intersection graph of the intervals. ...

: in an interval graph, the vertices are the intervals (a

finite set In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example, :\ is a finite set with five elements. ...

); in a 1-interval hypergraph, the vertices are all points in the real line (an

uncountable set In mathematics, an uncountable set (or uncountably infinite set) is an infinite set that contains too many elements to be countable. The uncountability of a set is closely related to its cardinal number: a set is uncountable if its cardinal num ...

). As another example, in a 2-interval hypergraph, the vertex set is the

disjoint union In mathematics, a disjoint union (or discriminated union) of a family of sets (A_i : i\in I) is a set A, often denoted by \bigsqcup_ A_i, with an injection of each A_i into A, such that the images of these injections form a partition of A ...

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: * A ''matching'' is a set of non-intersecting edges, i.e., a set of non-intersecting -intervals. For example, in the 1-interval hypergraph the set is a matching of size 2, but the set is not a matching since its elements intersect. The largest matching size in is denoted by . * A ''covering'' or a ''transversal'' is a set of vertices that intersects every edge, i.e., a set of points that intersects every -interval. For example, in the 1-interval hypergraph the set is a covering of size 2, but the set is not a covering since it does not intersect the edge . The smallest transversal size in is denoted by . is true for any hypergraph .

Tibor Gallai Tibor Gallai (born Tibor Grünwald, 15 July 1912 – 2 January 1992) was a Hungarian mathematician. He worked in combinatorics, especially in graph theory, and was a lifelong friend and collaborator of Paul Erdős. He was a student of Dénes K ...

proved that, in a 1-interval hypergraph, they are equal: . This is analogous to Kőnig's theorem for

bipartite graph In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V ar ...

s. 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 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 proved a colorful ("

rainbow A rainbow is a meteorological phenomenon that is caused by reflection, refraction and dispersion of light in water droplets resulting in a spectrum of light appearing in the sky. It takes the form of a multicoloured circular arc. Rainbows ...

") version of this theorem.

References

{{Reflist Hypergraphs