### Abstract

A (homogeneous) d-interval is a union of d closed intervals in the line. Let H be a finite collection of d-intervals. The transversal number τ (H) of H is the minimum number of points that intersect every member of H. The matching number v(H) of H is the maximum number of pairwise disjoint members of H. Gyárfás and Lehel [3] proved that τ ≤ O(v^{d!}) and Kaiser [4] proved that τ ≤ O(d^{2}v). His proof is topological, applies the Borsuk-Ulam theorem, and extends and simplifies a result of Tardos [5]. Here we give a very short, elementary proof of a similar estimate, using the method of [2].

Original language | English (US) |
---|---|

Pages (from-to) | 333-334 |

Number of pages | 2 |

Journal | Discrete and Computational Geometry |

Volume | 19 |

Issue number | 3 |

DOIs | |

State | Published - Apr 1998 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics

## Fingerprint Dive into the research topics of 'Piercing d-Intervals'. Together they form a unique fingerprint.

## Cite this

Alon, N. (1998). Piercing d-Intervals.

*Discrete and Computational Geometry*,*19*(3), 333-334. https://doi.org/10.1007/PL00009349