Name
Abstract | ||
|---|---|---|
AbstractA d-interval hypergraph has d disjoint copies of the unit interval as its vertex set, and each edge is the union of d subintervals, one on each copy. Extending a classical result of Gallai on the case $$d=1$$d=1, Tardos and Kaiser used topological tools to bound the ratio between the transversal number and the matching number in such hypergraphs. We take a dual point of view, and bound the edge-covering number (namely the minimal number of edges covering the entire vertex set) in terms of a parameter expressing independence of systems of partitions of the d unit intervals. The main tool we use is an extension of the KKM theorem to products of simplices, due to Peleg. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1007/s00454-017-9923-6 | Periodicals |
Keywords | Field | DocType |
Hypergraphs,Intervals,Independent sets,Edge-covers,Topological methods | Discrete mathematics,Combinatorics,Disjoint sets,Vertex (geometry),Constraint graph,Hypergraph,Transversal (geometry),Unit interval,Entire vertex,Mathematics | Journal |
Volume | Issue | ISSN |
58 | 3 | 0179-5376 |
Citations | PageRank | References |
0 | 0.34 | 4 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ron Aharoni I | 1 | 13 | 8.92 |
| Ron Holzman | 2 | 287 | 43.78 |
| Shira Zerbib | 3 | 3 | 3.47 |