A purely combinatorial proof of the Hadwiger Debrunner (p, q) conjecture

N. Alon; D. J. Kleitman

A purely combinatorial proof of the Hadwiger Debrunner (p, q) conjecture

N. Alon, D. J. Kleitman

Research output: Contribution to journal › Article › peer-review

Abstract

A family of sets has the (p, q) property if among any p members of the family some q have a nonempty intersection. The authors have proved that for every p ≥ q ≥ d + 1 there is a c = c(p, q, d) < ∞ such that for every family F of compact, convex sets in R^d which has the (p, q) property there is a set of at most c points in R^d that intersects each member of F, thus settling an old problem of Hadwiger and Debrunner. Here we present a purely combinatorial proof of this result.

Original language	English (US)
Article number	R1
Pages (from-to)	1-8
Number of pages	8
Journal	Electronic Journal of Combinatorics
Volume	4
Issue number	2 R
State	Published - Dec 1 1997
Externally published	Yes

All Science Journal Classification (ASJC) codes

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

Cite this

@article{b18cc968ac4849d0b5e0c11532e7c4b0,

title = "A purely combinatorial proof of the Hadwiger Debrunner (p, q) conjecture",

abstract = "A family of sets has the (p, q) property if among any p members of the family some q have a nonempty intersection. The authors have proved that for every p ≥ q ≥ d + 1 there is a c = c(p, q, d) < ∞ such that for every family F of compact, convex sets in Rd which has the (p, q) property there is a set of at most c points in Rd that intersects each member of F, thus settling an old problem of Hadwiger and Debrunner. Here we present a purely combinatorial proof of this result.",

author = "N. Alon and Kleitman, {D. J.}",

year = "1997",

month = dec,

day = "1",

language = "English (US)",

volume = "4",

pages = "1--8",

journal = "Electronic Journal of Combinatorics",

issn = "1077-8926",

publisher = "Electronic Journal of Combinatorics",

number = "2 R",

}

TY - JOUR

T1 - A purely combinatorial proof of the Hadwiger Debrunner (p, q) conjecture

AU - Alon, N.

AU - Kleitman, D. J.

PY - 1997/12/1

Y1 - 1997/12/1

N2 - A family of sets has the (p, q) property if among any p members of the family some q have a nonempty intersection. The authors have proved that for every p ≥ q ≥ d + 1 there is a c = c(p, q, d) < ∞ such that for every family F of compact, convex sets in Rd which has the (p, q) property there is a set of at most c points in Rd that intersects each member of F, thus settling an old problem of Hadwiger and Debrunner. Here we present a purely combinatorial proof of this result.

AB - A family of sets has the (p, q) property if among any p members of the family some q have a nonempty intersection. The authors have proved that for every p ≥ q ≥ d + 1 there is a c = c(p, q, d) < ∞ such that for every family F of compact, convex sets in Rd which has the (p, q) property there is a set of at most c points in Rd that intersects each member of F, thus settling an old problem of Hadwiger and Debrunner. Here we present a purely combinatorial proof of this result.

UR - http://www.scopus.com/inward/record.url?scp=0007372644&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0007372644&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:0007372644

SN - 1077-8926

VL - 4

SP - 1

EP - 8

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 2 R

M1 - R1

ER -

A purely combinatorial proof of the Hadwiger Debrunner (p, q) conjecture

Abstract

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this