Eckhoff's Problem on Convex Sets in the Plane

  • Adam S. Jobson
  • André E. Kézdy
  • Jenő Lehel

Abstract

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.

Published
2021-08-27
Article Number
P3.43