On a problem by Dol’nikovDiscrete Mathematics

About

Authors
Jesús Jerónimo-Castro, Alexander Magazinov, Pablo Soberón
Year
2015
DOI
10.1016/j.disc.2015.04.009
Subject
Discrete Mathematics and Combinatorics / Theoretical Computer Science

Similar

The effect of streptozotocin diabetes on platelet function in rats

Authors:
A. Eldor, S. Merin, H. Bar-On
1978

A generic auction algorithm for the minimum cost network flow problem

Authors:
Dimitri P. Bertsekas, David A. Casta�on
1993

Cross Sectional Observational Study on the Societal Costs of Alzheimers Disease

Authors:
J. Mesterton, A. Wimo, A. By, S. Langworth, B. Winblad, L. Jonsson
2010

Anomalous coronary vessels

Authors:
On Topaz
1999

Text

Discrete Mathematics 338 (2015) 1577–1585

Contents lists available at ScienceDirect

Discrete Mathematics journal homepage: www.elsevier.com/locate/disc

On a problem by Dol’nikov

Jesús Jerónimo-Castro a, Alexander Magazinov b, Pablo Soberón c,∗ a Facultad de Ingeniería, Universidad Autónoma de Querétaro, Cerro de las Campanas s/n, C.P. 76010, Querétaro, Mexico b Russian Academy of Sciences, 8 Gubkina street, Moscow 119991, Russia c Department of Mathematics, University of Michigan, 530 Church Street, Ann Arbor, MI 48109-1043, USA a r t i c l e i n f o

Article history:

Received 10 December 2013

Received in revised form 7 April 2015

Accepted 8 April 2015

Available online 29 April 2015

Keywords:

Discrete geometry

Helly’s theorem

Piercing number

Covering number a b s t r a c t

In 2011 at an Oberwolfach workshop in Discrete Geometry, V. Dol’nikov posed the following problem. Consider three non-empty families of translates of a convex compact set K in the plane. Suppose that every two translates from different families have a point of intersection. Is it always true that one of the families can be pierced by a set of three points?

A result by R.N. Karasev from 2000 gives, in fact, an affirmative answer to the ‘‘monochromatic’’ version of the problem above. That is, if all the three families in the problem coincide. In the present paper we solve Dol’nikov’s problem positively if K is either centrally symmetric or a triangle, and show that the conclusion can be strengthened if K is a Euclidean disk. We also confirm the conjecture if we are given four families satisfying the conditions above. © 2015 Elsevier B.V. All rights reserved. 1. Introduction

Helly’s celebrated theorem [14,7] gives a characterisation of all families of convex sets in Rd that have a point of intersection. Namely, it says that A finite family F of convex sets in Rd has a point of intersection if and only if every d+ 1 sets of F have a point of intersection. This theorem is optimal in the sense that the number d + 1 cannot be improved. The question then becomes whether weakening Helly’s condition can still give results on the global intersection structure of the family of convex sets. This was answered positively by Alon and Kleitman in 1992 [1].

We say that a family F of convex sets in Rd has piercing number k if k is the smallest positive integer such that there is a set of k points in Rd that intersects every element of F . We denote this by π(F ) = k. We say that a family F of convex sets in Rd has the (p, q) property if out of every p sets in F we can always find at least q which are intersecting. Alon and

Kleitman gave a positive answer to the (p, q) conjecture of Hadwiger and Grünbaum, showing that for every p ≥ d ≥ d+ 1 there is a constant c = c(p, q, d) such that for every family F of convex sets in Rd with the (p, q) property, we have π(F ) ≤ c .

However, the current bounds on c are astronomical. This is commonly known as the (p, q) theorem.

Finding precise bounds for c is still an open problem. Even in the first non-trivial case, the conjecture is c(4, 3, 2) = 3 but the best bound so far gives c(4, 3, 2) ≤ 13 [12] (the existence theorem gives a bound of over 200).

The condition q ≥ d + 1 is essential, as a family of n hyperplanes in general position in Rd has the (d, d) property but cannot be pierced by less than nd points. However, if further conditions are imposed on the family, (p, q) conditions with q ≤ d can give bounds on the piercing number of the family. This can bee seen in the following result of Karasev.

Theorem (Karasev, 2000 [8]). Let K be a convex set in the plane. If F is a family of pairwise intersecting translates of K , then π(F) ≤ 3. ∗ Corresponding author.

E-mail addresses: jesusjero@hotmail.com (J. Jerónimo-Castro), magazinov-al@yandex.ru (A. Magazinov), psoberon@umich.edu (P. Soberón). http://dx.doi.org/10.1016/j.disc.2015.04.009 0012-365X/© 2015 Elsevier B.V. All rights reserved. 1578 J. Jerónimo-Castro et al. / Discrete Mathematics 338 (2015) 1577–1585

In general, ifF is a family of translates of a convex bodyK inRd, a (p, 2) property is enough to bound the piercing number.

This was first noted by Kim, Nakprasit, Pelsmajer and Skokan [11] with a bound of π(F ) ≤ 2ddd(p − 1) and recently an improved bound of π(F ) ≤ 2d2dd (d log d+ log log d+5d)(p−1)was obtained by Naszódi and Taschuk [13], also showing that the order of growth of their bound is correct.

More recently, a result by Katchalski and Nashtir [10] extends Karasev’s result to more diverse families of convex sets, rather than just translates of the same body.We say that two polygons P,Q are related if P is the intersection ofm half-planes a1, a2, . . . , ak and Q is the intersection ofm half-planes b1, b2, . . . , bk, so that each bi is a translate of ai.

Theorem (Katchalski and Nashtir, 2011). If F is a family of pairwise intersecting convex sets in the plane each of which is related to a fixed n-gon, then π(F ) ≤ 3(n3).

One should note that, for the case of triangles, the result above gives the precise bound for Karasev’s result. In the case of parallelograms it also shows that a (2, 2) property implies a piercing number of one.

We wish to explore the relation of the results above with what is commonly known as colourful theorems. The classical example of this kind of results is a notable variation of Helly’s theorem, also known as the colourful version of Helly’s theorem.

Theorem (Lovász, 1982 [2]). Let F1,F2, . . . ,Fd+1 be families of convex sets in Rd. If every (d + 1)-tuple K1 ∈ F1, K2 ∈

F2, . . . , Kd+1 ∈ Fd+1 has a point of intersection, then there is an i0 ∈ {1, 2, . . . , d+ 1} such that all the sets in Fi0 have a point of intersection.

Lovász’s proof for the theorem above appeared first in a paper by Bárány where the colourful version of Carathéodory’s theorem is presented. Note that if all Fi are equal, we get the original statement of Helly’s theorem.