This HTML5 document contains 43 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n8https://global.dbpedia.org/id/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
wikipedia-enhttp://en.wikipedia.org/wiki/
dbchttp://dbpedia.org/resource/Category:
dbphttp://dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:D-interval_hypergraph
rdf:type
owl:Thing
rdfs:label
D-interval hypergraph
rdfs:comment
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. 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. ν(H) ≤ τ(H) is true for any hypergraph H.
owl:differentFrom
dbr:Interval_graph
dcterms:subject
dbc:Hypergraphs
dbo:wikiPageID
65615982
dbo:wikiPageRevisionID
1096036121
dbo:wikiPageWikiLink
dbr:Vertex_(graph_theory) dbr:Tuple dbr:Uncountable_set dbr:Interval_(mathematics) dbr:Matching_in_hypergraphs dbr:Disjoint_union dbr:Real_line dbc:Hypergraphs dbr:Line_(geometry) dbr:Set_(mathematics) dbr:Gábor_Tardos dbr:Uncountably_many dbr:Kőnig's_theorem_(graph_theory) dbr:Positive_integer dbr:Interval_graph dbr:Tibor_Gallai dbr:Graph_theory dbr:Rainbow_matching dbr:Vertex_cover_in_hypergraphs dbr:Finite_set dbr:Hypergraph dbr:Bipartite_graph
owl:sameAs
n8:FMAab wikidata:Q104864580
dbp:wikiPageUsesTemplate
dbt:Math dbt:Short_description dbt:Reflist dbt:Distinguish dbt:Mvar
dbo:abstract
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 hypergraphs: * 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. The largest matching size in H is denoted by ν(H). * 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]. The smallest transversal size in H is denoted by τ(H). ν(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 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 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 proved a colorful ("rainbow") version of this theorem.
prov:wasDerivedFrom
wikipedia-en:D-interval_hypergraph?oldid=1096036121&ns=0
dbo:wikiPageLength
4306
foaf:isPrimaryTopicOf
wikipedia-en:D-interval_hypergraph
Subject Item
dbr:Matching_in_hypergraphs
dbo:wikiPageWikiLink
dbr:D-interval_hypergraph
Subject Item
dbr:Interval_graph
owl:differentFrom
dbr:D-interval_hypergraph
Subject Item
wikipedia-en:D-interval_hypergraph
foaf:primaryTopic
dbr:D-interval_hypergraph