D-interval hypergraph

Last updated

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. [1]

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 hypergraphs:

ν(H) ≤ τ(H) is true for any hypergraph H.

Tibor Gallai proved that, in a 1-interval hypergraph, they are equal: τ(H) = ν(H). This is analogous to Kőnig's theorem for bipartite graphs.

Gabor Tardos [1] proved that, in a 2-interval hypergraph, τ(H) ≤ 2ν(H), and it is tight (i.e., every 2-interval hypergraph with a matching of size m, can be covered by 2m points).

Kaiser [2] proved that, in a d-interval hypergraph, τ(H) ≤ d(d – 1)ν(H), and moreover, every d-interval hypergraph with a matching of size m, can be covered by at d(d − 1)m points, (d − 1)m points on each line.

Frick and Zerbib [3] proved a colorful ("rainbow") version of this theorem.

Related Research Articles

Bipartite graph Graph divided into two independent sets

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets and , that is every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.

In combinatorics, a Helly family of order k is a family of sets in which every minimal subfamily with an empty intersection has k or fewer sets in it. Equivalently, every finite subfamily such that every k-fold intersection is non-empty has non-empty total intersection. The k-Helly property is the property of being a Helly family of order k.

Erdős–Faber–Lovász conjecture

In graph theory, the Erdős–Faber–Lovász conjecture is a problem about graph coloring, named after Paul Erdős, Vance Faber, and László Lovász, who formulated it in 1972. It says:

In combinatorics, a Sperner family, or clutter, is a family F of subsets of a finite set E in which none of the sets contains another. Equivalently, a Sperner family is an antichain in the inclusion lattice over the power set of E. A Sperner family is also sometimes called an independent system or irredundant set.

In graph theory, particularly in the theory of hypergraphs, the line graph of a hypergraphH, denoted L(H), is the graph whose vertex set is the set of the hyperedges of H, with two vertices adjacent in L(H) when their corresponding hyperedges have a nonempty intersection in H. In other words, L(H) is the intersection graph of a family of finite sets. It is a generalization of the line graph of a graph.

Clique complex Abstract simplicial complex describing a graphs cliques

Clique complexes, flag complexes, and conformal hypergraphs are closely related mathematical objects in graph theory and geometric topology that each describe the cliques of an undirected graph.

Gábor Tardos Hungarian mathematician

Gábor Tardos is a Hungarian mathematician, currently a professor at Central European University and previously a Canada Research Chair at Simon Fraser University. He works mainly in combinatorics and computer science. He is the younger brother of Éva Tardos.

In geometry, specifically projective geometry, a blocking set is a set of points in a projective plane that every line intersects and that does not contain an entire line. The concept can be generalized in several ways. Instead of talking about points and lines, one could deal with n-dimensional subspaces and m-dimensional subspaces, or even more generally, objects of type 1 and objects of type 2 when some concept of intersection makes sense for these objects. A second way to generalize would be to move into more abstract settings than projective geometry. One can define a blocking set of a hypergraph as a set that meets all edges of the hypergraph.

In the mathematical discipline of graph theory, a rainbow matching in an edge-colored graph is a matching in which all the edges have distinct colors.

In graph theory, a matching in a hypergraph is a set of hyperedges, in which every two hyperedges are disjoint. It is an extension of the notion of matching in a graph.

In graph theory, a vertex cover in a hypergraph is a set of vertices, such that every hyperedge of the hypergraph contains at least one vertex of that set. It is an extension of the notion of vertex cover in a graph.

In the mathematical field of graph theory, Hall-type theorems for hypergraphs are several generalizations of Hall's marriage theorem from graphs to hypergraphs. Such theorems were proved by Ofra Kessler, Ron Aharoni, Penny Haxell, Roy Meshulam, and others.

In graph theory, a fractional matching is a generalization of a matching in which, intuitively, each vertex may be broken into fractions that are matched to different neighbor vertices.

In graph theory, a balanced hypergraph is a hypergraph that has several properties analogous to that of a bipartite graph.

In graph theory, Ryser's conjecture is a conjecture relating the maximum matching size and the minimum transversal size in hypergraphs.

In geometry, a truncated projective plane (TPP), also known as a dual affine plane, is a special kind of a hypergraph or geometric configuration that is constructed in the following way.

In graph theory, perfect matching in high-degree hypergraphs is a research avenue trying to find sufficient conditions for existence of a perfect matching in a hypergraph, based only on the degree of vertices or subsets of them.

In graph theory, a rainbow-independent set (ISR) is an independent set in a graph, in which each vertex has a different color.

In graph theory, there are two related properties of a hypergraph that are called its "width". Given a hypergraph H =, we say that a set K of edges pins another set F of edges if every edge in F intersects some edge in K. Then:

In graph theory, Meshulam's game is a game used to explain a theorem of Roy Meshulam related to the homological connectivity of the independence complex of a graph, which is the smallest index k such that all reduced homological groups up to and including k are trivial. The formulation of this theorem as a game is due to Aharoni, Berger and Ziv.

References

  1. 1 2 Tardos, Gábor (1995-03-01). "Transversals of 2-intervals, a topological approach". Combinatorica . 15 (1): 123–134. doi: 10.1007/bf01294464 . ISSN   0209-9683.
  2. ↑ Kaiser, T. (1997-09-01). "Transversals of d-Intervals". Discrete & Computational Geometry . 18 (2): 195–203. doi: 10.1007/PL00009315 . ISSN   1432-0444.
  3. ↑ Frick, Florian; Zerbib, Shira (2019-06-01). "Colorful Coverings of Polytopes and Piercing Numbers of Colorful d-Intervals". Combinatorica . 39 (3): 627–637. arXiv: 1710.07722 . doi:10.1007/s00493-018-3891-1. ISSN   1439-6912.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.