Eckhoff proposed a combinatorial version of the classical Hadwiger–Debrunner $(p,q)$-problems as follows. Let ${\cal F}$ be a finite family of convex sets in the plane and let $m\geqslant 1$ be an integer. If among every ${m+2\choose 2}$ members of ${\cal F}$ all but at most $m-1$ members have a common point, then there is a common point for all but at most $m-1$ members of ${\cal F}$. The claim is an extension of Helly's theorem ($m=1$). The case $m=2$ was verified by Nadler and by Perles. Here we show that Eckhoff 's conjecture follows from an old conjecture due to Szemerédi and Petruska concerning $3$-uniform hypergraphs. This conjecture is still open in general; its solution for a few special cases answers Eckhoff's problem for $m=3,4$. A new proof for the case $m=2$ is also presented.
@article{10_37236_9978,
author = {Adam S. Jobson and Andr\'e E. K\'ezdy and Jen\H{o} Lehel},
title = {Eckhoff's problem on convex sets in the plane},
journal = {The electronic journal of combinatorics},
year = {2021},
volume = {28},
number = {3},
doi = {10.37236/9978},
zbl = {1471.52001},
url = {http://geodesic.mathdoc.fr/articles/10.37236/9978/}
}
TY - JOUR
AU - Adam S. Jobson
AU - André E. Kézdy
AU - Jenő Lehel
TI - Eckhoff's problem on convex sets in the plane
JO - The electronic journal of combinatorics
PY - 2021
VL - 28
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/9978/
DO - 10.37236/9978
ID - 10_37236_9978
ER -
%0 Journal Article
%A Adam S. Jobson
%A André E. Kézdy
%A Jenő Lehel
%T Eckhoff's problem on convex sets in the plane
%J The electronic journal of combinatorics
%D 2021
%V 28
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/9978/
%R 10.37236/9978
%F 10_37236_9978
Adam S. Jobson; André E. Kézdy; Jenő Lehel. Eckhoff's problem on convex sets in the plane. The electronic journal of combinatorics, Tome 28 (2021) no. 3. doi: 10.37236/9978
