A Fractional Helly theorem for convex lattice sets

Imre Bárány^{∗}

Rényi Institute of Mathematics Hungarian Academy of Sciences POBox 127, 1364 Budapest, Hungary and Department of Mathematics University College London Gower Street, London WC1E 6BT England

Jiří Matoušek^{∗∗}

Department of Applied Mathematics and Institute of Theoretical Computer Science (ITI) Charles University Malostranské nám. 25, 118 00 Praha 1 Czech Republic

Abstract

A set of the form C ∩ Z^{d}, where C ⊆ R^{d} is convex and Z^{d} denotes the integer lattice, is called a convex lattice set. It is known that the Helly number of d-dimensional convex lattice sets is 2^{d}. We prove that the fractional Helly number is only d + 1: For every d and every α ∈ (0, 1] there exists β > 0 such that whenever F_{1}, …, F_{n} are convex lattice sets in Z^{d} such that ⋂_{i∈I} F_{i} ≠ ∅ for at least α\binom{n}{d+1} index sets I ⊆ \{1, 2, …, n\} of size d + 1, then there exists a (lattice) point common to at least βn of the F_{i}. This implies a (p, d + 1)-theorem for every p ≥ d + 1; that is, if F is a finite family of convex lattice sets in Z^{d} such that among every p sets of F, some d + 1 intersect, then F has a transversal of size bounded by a function of d and p.

1 Introduction

Let Z^{d} denote the integer lattice in the d-dimensional Euclidean space R^{d}. A subset F ⊆ Z^{d} is called a convex lattice set if there is a convex set C ⊆ R^{d} with F = C ∩ Z^{d}. In this paper we investigate Helly-type (and Gallai-type) properties of convex lattice sets.

The well-known theorem of Helly states that if C is a finite family of convex sets in R^{d} such that any d + 1 or fewer of the sets of F intersect, then ⋂ C ≠ ∅; we say that the d-dimensional convex sets have Helly number d+1. It is known that the Helly number of convex lattice sets in Z^{d} is much larger, namely 2^{d} [4] (for the lower bound, consider the family of all the (2^{d} − 1)-point subsets of {0, 1}^{d}). Our results show that this large Helly number can be regarded as a “local anomaly” and that the relevant number for other, more global Helly-type properties is only d + 1.

∗Supported by Hungarian National Foundation Grant T 032542 ∗∗Supported by Project LN00A056 of the Ministry of Education of the Czech Republic and by Charles University grants No. 158/99 and 159/99. Part of this research was done during a visit to University College London and supported by an EPSRC research fellowship.

The behavior of integer points in convex bodies is a central topic in integer programming. The Helly number of convex lattice sets, and the Radon number of the corresponding convexity space, have been studied in connection with integer programming, geometry of numbers, crystallographic lattices, computational complexity in lattices, and indivisibilities in economy (see [4], [10], [11]).

Technically, our main result is a fractional Helly theorem. For convex sets in R^{d}, the fractional Helly theorem proved by Katchalski and Liu [8] asserts the following (here and in the sequel, we use the notation [n] = {1, 2, …, n}): For every d ≥ 1 and every α ∈ (0, 1] there exists a β = β(d, α) > 0 with the following property. Let C_{1}, …, C_{n} be convex sets in R^{d} such that ⋂_{i∈I} C_{i} ≠ ∅ for at least α\binom{n}{d+1} index sets I ⊆ [n] of size (d + 1). Then there exists a point contained in at least βn of the C_{i}. The best possible value of β(d, α) is 1 − (1 − α)^{1/(d+1)} (Kalai [7]) and, in particular, β → 1 as α → 1.

Alon et al. [1] observed that the method of Katchalski and Liu [8] and the fact that the Helly number for convex lattice sets is 2^{d} immediately imply a fractional Helly theorem for convex lattice sets with 2^{d}-tuples instead of (d + 1)-tuples. (For the reader’s convenience, we sketch the proof at the end of Section 2.) It is conjectured in Alon et al. [1] that a fractional Helly theorem with d + 1 actually holds. Here we confirm this conjecture:

Theorem 1.1 (Fractional Helly theorem for convex lattice sets) For every d ≥ 1 and every α ∈ (0, 1] there exists a β = β(d, α) > 0 with the following property. Let F_{1}, …, F_{n} be convex lattice sets in Z^{d} such that ⋂_{i∈I} F_{i} ≠ ∅ for at least α\binom{n}{d+1} index sets I ⊆ [n] of size (d + 1). Then there exists a point contained in at least βn sets among the F_{i}.

Here we cannot expect β tending to 1 with α → 1, since the Helly number is larger than d + 1.

The method of the proof combines Ramsey-theoretic arguments with results in convexity.

By an ingenious method, Alon and Kleitman [2] established a conjecture of Hadwiger and Debrunner from 1957, the so-called (p, q)-theorem: Let p, q, d be integers with p ≥ q ≥ d + 1 ≥ 2. Then there exists a number HD(p, q, d) such that the following holds: Let C be a finite family of convex sets in R^{d} satisfying the (p, q)-condition; that is, among any p sets of C, there are q sets with a nonempty intersection. Then τ(C) ≤ HD(p, q, d) points. Here τ(F) denotes the transversal number of a set system F, i.e. the smallest cardinality of a set X ⊆ ⋃ F such that F ∩ X ≠ ∅ for every F ∈ F.

The Alon–Kleitman proof uses many tools from combinatorial convexity, but as was observed in [1], the crucial ingredient in the proof is the fractional Helly theorem, and all the other tools can be derived from it on a quite general abstract level. In particular, the results of [1] show that Theorem 1.1 implies a (p, q)-theorem for convex lattice sets for every p ≥ q ≥ d + 1. Since we do not try to optimize the constants, it is sufficient to state the theorem for q = d + 1.

Theorem 1.2 ((p, q)-theorem for convex lattice sets) Let p and d be integers with p ≥ d + 1 ≥ 2. Then there exists a number IHD(p, d) such that any finite family F of convex lattice sets in Z^{d} satisfying the (p, d+1)-condition has τ(F) ≤ IHD(p, d).

This result has been known for d = 2 [1]. It was derived from a Gallai-type result of Hausel [6]: If F is a finite family of convex lattice sets in Z^{2} such that every 3 sets of F intersect, then τ(F) ≤ 2. For p = q = d + 1, Theorem 1.2 yields an analogous statement for Z^{d}, with the transversal number being at most IHD(d + 1, d). The bound for this number obtained from our proof is enormous (although primitively recursive). It would be interesting to find a proof with significantly better bounds (Hausel’s proof seems neither to generalize to higher dimensions nor to provide a fractional Helly theorem).

Further generalizations of the Alon–Kleitman (p, q)-theorem and of Theorem 1.2, somewhat complicated-looking but perhaps useful, are proved in Section 4.

2 Tools

Intermixed sets. The main property of convex lattice sets used in the proof of Theorem 1.1 is captured in the following definition and lemma. Let r ≥ 1 be an integer, let ε > 0 be a real number, let Z_{1}, Z_{2}, …, Z_{r} ⊂ R^{d} be finite sets or multisets, and let Z denote their disjoint union. Call Z_{1}, Z_{2}, …, Z_{r} ε-intermixed if every halfspace γ with |γ ∩ Z| ≥ ε|Z| intersects each of Z_{1}, …, Z_{r}.

Lemma 2.1 (Intermixing lemma) If Z_{1}, Z_{2}, …, Z_{r} ⊂ Z^{d} are finite sets of lattice points that are \frac{1}{h}-intermixed, where h = 2^{d}, then (⋂_{j=1}^{r} conv(Z_{j}))∩Z^{d} ≠ ∅.

Proof. This is like an argument for bounding the Radon number for lattice convex sets (Sierksma [12]; also see Onn [10]) using the already mentioned fact that the Helly number of convex lattice sets is h = 2^{d}.

Let n = |Z| and set k = ⌊\frac{n−1}{h}⌋. Let F = \{conv(Y) : Y ⊆ Z, |Y | ≥ n − k\}. Every h subsets of Z of cardinality n − k have a common point, because their complements together cannot cover all of Z. By the Helly theorem for convex lattice sets, there is an integer point z ∈ ⋂ F.

Suppose that z ∉ conv(Z_{j}). Then there is a halfspace γ containing z but no point of Z_{j}. At the same time, we have |γ ∩Z| > k, for otherwise |Z \γ| ≥ n−k, and so conv(Z \ γ) ∈ F. So γ contains at least k + 1 points of Z but no point of Z_{j}, and it follows that Z_{1}, …, Z_{r} are not \frac{1}{h}-intermixed. □

We are actually going to use the following consequence of the intermixing lemma:

Corollary 2.2 Let Z_{1}, Z_{2}, …, Z_{r} ⊂ Z^{d} be finite sets or multisets. Assume, moreover, that they are indexed by the same index set I; that is, Z_{j} = {z_{ji} : i ∈ I}. Then at least one of the following are true:

(i) all the convex hulls have a common integer point; i.e. ⋂_{j=1}^{r} conv(Z_{j}) ∩ Z^{d} ≠ ∅, or

(ii) there are a subset I′ ⊆ I with |I′| ≥ 2^{−d}|I| and two indices j_{1}, j_{2} ∈ [r] such that conv(Z′_{j_{1}}) ∩ conv(Z′_{j_{2}}) = ∅, where Z′_{j} = {z_{ji} : i ∈ I′} (and the convex hulls are in R^{d}).

Proof. If the Z_{j} are 2^{−d}-intermixed, then the intermixing lemma implies (i). If they are not 2^{−d}-intermixed, there is a halfspace γ containing at least 2^{−d}r|I| points of ⋃ Z_{j} and disjoint from some Z_{j_{1}}. Choose a j_{2} with |γ ∩ Z_{j_{2}}| ≥ \frac{r}{r−1}2^{−d}|I| ≥ 2^{−d}|I|. Letting I′ = \{i ∈ I : z_{j_{2},i} ∈ γ\}, we obtain the situation as in (ii). □

Hypergraphs. It is convenient to formulate some of the subsequent arguments in terms of k-partite hypergraphs. A k-uniform hypergraph is a pair H = (V, E), where V = V (H) is the vertex set, and the edge set E = E(H) ⊆ \binom{V}{k} is a system of k-element subsets of V. A k-uniform hypergraph is k-partite if V can be partitioned into disjoint sets (classes) V_{1}, V_{2}, …, V_{k} such that each edge contains exactly one point from each class.

A k-uniform k-partite hypergraph H as above is called complete if all the possible edges are present; i.e. E(H) = {{v_{1}, …, v_{k}} : v_{1} ∈ V_{1}, …, v_{k} ∈ V_{k}}. Let K^{k}(t_{1}, t_{2}, …, t_{k}) denote a complete k-uniform k-partite hypergraph with classes of sizes t_{1}, t_{2}, …, t_{k}, respectively, and let K^{k}(t) = K^{k}(t, t, …, t). We need the following theorem of Erdős and Simonovits [5] about super-saturated hypergraphs.

Theorem 2.3 For any positive integers k and t and any ε > 0 there exists δ > 0 with the following property. Let H be a k-uniform hypergraph on n vertices and with at least ε\binom{n}{k} edges. Then H contains at least

⌊δn^{kt}⌋

copies (not necessarily induced) of K^{k}(t). In particular, if ε is fixed and n is sufficiently large, then H contains at least one K^{k}(t).

Lovász’s colored Helly theorem. Another key ingredient in our proof is the following result of Lovász [9] (see [3] for a proof). We formulate it using the hypergraph language.

Theorem 2.4 Let H = (V, E) be a complete (d + 1)-partite (d + 1)-uniform hypergraph with classes V_{1}, …, V_{d+1}. Let (C_{v} : v ∈ V) be a family of convex sets indexed by the vertices of H, and such that ⋂_{v∈e} C_{v} ≠ ∅ for every edge e ∈ E. Then there is an i ∈ [d + 1] with ⋂_{v∈V_{i}} C_{v} ≠ ∅.

We will only need a special case of this result, namely when each |V_{i}| = 2, for which we give a simple proof right now: Write u(i), v(i) for the two elements of V_{i} (i = 1, …, d + 1). We have to show that C_{u(i)} ∩ C_{v(i)} is non-void for some i. Assume the contrary; then C_{u(i)} and C_{v(i)} are separated by a hyperplane L_{i}, i = 1 …, d + 1. For each of the 2^{d+1} edges of E let x_{e} be a point in ⋂_{v∈e} C_{v}. These points have to lie in distinct cells determined by the hyperplanes L_{i}, because x_{e} is on the same side of L_{i} as the corresponding set C_{u(i)} or C_{v(i)} is. However, d + 1 hyperplanes subdivide R^{d} into at most 2^{d+1} − 1 cells—a contradiction.

We are also going to rely on the weaker fractional Helly theorem for convex lattice sets noted by Alon et al. [1]:

Theorem 2.5 For every d ≥ 1 and every α ∈ (0, 1] there exists β = β(d, α) > 0 with the following property. Let F_{1}, …, F_{n} be convex lattice sets in Z^{d} such that ⋂_{i∈I} F_{i} ≠ ∅ for at least α\binom{n}{2^{d}} index sets I ⊆ [n] of size 2^{d}. Then there exists a point contained in at least βn sets among the F_{i}.

Sketch of proof. We may assume that the F_{i} are finite (by intersecting them with a large box, say). We choose a vector a ∈ R^{d} with no rational dependence among the coordinates and for x, y ∈ Z^{d} we define x ≤ y iff ⟨a, x⟩ ≤ ⟨a, y⟩. Let us write h = 2^{d}. For every h-element I ⊆ [n] with F_{I} = ⋂_{i∈I} F_{i} ≠ ∅, let x_{I} = min F_{I} (the first point under ≤). For every I there is an (h − 1)-element J = J(I) with x_{I} = min F_{J}. Indeed, letting H_{I} = {x ∈ Z^{d} : x < x_{I}}, the family {F_{i} : i ∈ I} ∪ {H_{I}} has empty intersection, and since the Helly number of convex lattice sets is h, some subfamily of h sets has empty intersection. The sets in this subfamily other than H_{I} determine J.

There are at most \binom{n}{h−1} possible J(I) and α\binom{n}{h} different I, and so, for suitable β > 0, some J is assigned to at least βn different I. Each such I has exactly one i ∉ J, and the βn sets F_{i} with these indices all contain min F_{J}. □

3 Proofs

The main part of our proof of Theorem 1.1 is the following result, a (weak) integer analogue of the colored Helly theorem 2.4:

Proposition 3.1 (Colored Helly theorem for convex lattice sets) For any integers d ≥ 1 and r ≥ 2 there exists an integer t with the following property. Let H_{0} = (V_{0}, E_{0}) be a complete (d + 1)-uniform (d + 1)-partite hypergraph K^{d+1}(t) and let (F_{v} : v ∈ V_{0}) be a family of convex lattice sets in Z^{d} indexed by the vertices of H_{0} such that ⋂_{v∈e} F_{v} ≠ ∅ for every edge e ∈ E_{0}. Then there is a set R of r vertices in one of the classes of H_{0} with ⋂_{v∈R} F_{v} ≠ ∅.

Proof of the fractional Helly theorem (Theorem 1.1) from Proposition 3.1. The idea is to use Proposition 3.1 with r = 2^{d} and the Erdős– Simonovits theorem (Theorem 2.3) to verify the assumptions of the weaker fractional Helly theorem 2.5 dealing with 2^{d}-tuples instead of (d + 1)-tuples.

Let F_{1}, F_{2}, …, F_{n} be convex lattice sets as in Theorem 1.1, i.e. with at least α\binom{n}{d+1} intersecting (d + 1)-tuples. We may assume that n is sufficiently large, for otherwise βn ≤ 1, and a point in a single set will do.

Let H be the hypergraph with vertex set [n] and edge set E = \{e ∈ \binom{[n]}{d+1} : ⋂_{i∈e} F_{i} ≠ ∅}. Applying Theorem 2.3 to H, with k = d + 1, ε = α, and t as in Proposition 3.1 (for r = 2^{d}), we see that H contains at least δn^{(d+1)t} copies of K^{d+1}(t) for some δ = δ(d, t, α) > 0. By Proposition 3.1, each such copy contributes at least one intersecting r-tuple of the sets F_{i}. On the other hand, any given intersecting r-tuple is contributed by at most n^{(d+1)t−r} copies (this is the number of choices for the vertices not belonging to the considered r-tuple). It follows that the family F_{1}, F_{2}, …, F_{n} has at least δ\binom{n}{r} intersecting r-tuples. By the fractional Helly theorem 2.5 with r-tuples, at least βn among the F_{i} have a common point. □

Towards the proof of Proposition 3.1. For each edge e ∈ E_{0}, let z_{e} be a lattice point in the intersection ⋂_{v∈e} F_{v}. These z_{e} remain fixed throughout the proof.

For a vertex v ∈ V_{0}, let us put Z_{v} = {z_{e} : e ∈ E_{0}, v ∈ e} and G_{v} = conv(Z_{v}) ∩ Z^{d}. To prove the proposition, it suffices to show that given any system (z_{e} : e ∈ E_{0}) of lattice points, there is an r-tuple R of vertices in one of the classes of H_{0} such that ⋂_{v∈R} G_{v} ≠ ∅. Indeed, if we start with the given convex lattice sets F_{v} as in the proposition, choose the points z_{e} in the appropriate intersections, and construct the G_{v}, then we have G_{v} ⊆ F_{v}.

In the proof, we are going to construct successively smaller and smaller subhypergraphs of our initial H_{0} (they are all going to be complete (d + 1)- partite hypergraphs). If H = (V, E) is one of these subhypergraphs, we extend the notation introduced above and write Z_{v}(H) = {z_{e} : e ∈ E, v ∈ e} and G_{v}(H) = conv(Z_{v}(H)) ∩ Z^{d}.

Further, let us say that the ith class of H is (r, 2)-disjoint if among any r of the sets conv(Z_{v}(H)), where v are vertices from the ith class of H, there are two that are disjoint. Note that this condition is about the convex hulls in R^{d}, not only about lattice points.

Proposition 3.1 easily follows from the colored Helly theorem (Theorem 2.4) and the following lemma.

Lemma 3.2 For every integers d, r, and s there exists an integer S = S(d, r, s) with the following property. Let i_{0} ∈ [d + 1], let H = K^{d+1}(S), and for each e ∈ E(H), let a lattice point z_{e} ∈ Z^{d} be given. Then at least one of the following two possibilities occur:

(i) there is a set R of r vertices in the i_{0}th class of H such that ⋂_{v∈R} G_{v}(H) ≠ ∅, or

(ii) there is a subhypergraph H′ = K^{d+1}(s) of H such that the i_{0}th class of H′ is (r, 2)-disjoint.

The proof of Proposition 3.1 from this lemma is quite short. We start with our hypergraph H_{0} = K^{d+1}(t) with t enormously large. We apply the lemma with H = H_{0} and i_{0} = 1. This either yields r intersecting sets among the G_{v}(H_{0}) or a smaller complete (d + 1)-partite hypergraph H_{1} with the first class being (r, 2)-disjoint. This H_{1} is still huge and we apply the lemma again with i_{0} = 2, which yields either r intersecting sets among the G_{v}(H_{1}) or a still smaller H_{2} with the second class (r, 2)-disjoint, too. We continue in this manner with i_{0} = 3, 4, …, d + 1. If the t we started with was sufficiently large and if we never encountered case (i) in the lemma, i.e. r intersecting sets, then we would end up with H_{d+1} being a K^{d+1}(r) and with each of the classes (r, 2)-disjoint. Since the classes now have size r, this simply means that each class V_{i} contains two elements, call them u(i) and v(i), such that conv(Z_{u(i)}(H_{d+1})) ∩ conv(Z_{v(i)}(H_{d+1})) = ∅. But this contradicts the special case of Theorem 2.4.

It remains to prove Lemma 3.2. For simpler notation we assume i_{0} = 1. We are given H = K^{d+1}(S) and the lattice points z_{e}, e ∈ E(H). Let us choose (arbitrarily) a subset Ṽ_{1} of s vertices from the first class of H. We form H̃_{0} by restricting the first class of H to Ṽ_{1} (so H̃_{0} is a K^{d+1}(s, S, S, …, S)). Let R_{1}, R_{2}, …, R_{m} be the enumeration of all r-element subsets of Ṽ_{1}, m = \binom{s}{r}. We are going to form subhypergraphs H̃_{1}, …, H̃_{m} of H̃_{0}, where H̃_{k} is a K^{d+1}(s, s_{k}, s_{k}, …, s_{k}) and s_{0} = S > s_{1} > ⋯ > s_{m} = s. So the first class remains unchanged while vertices are being deleted from all the other classes. The final H̃_{m} is the desired H′ as in case (ii) of the lemma, but in each of the steps, we can also possibly encounter case (i) and finish.

For passing from H̃_{k} to H̃_{k+1}, we are going to apply Corollary 2.2 to the sets Z_{v} = Z_{v}(H̃_{k}), v ∈ R_{k}. Note that the points of each Z_{v} are indexed by the edges of H̃_{k} that contain v. Since H̃_{k} is a K^{d+1}(s, s_{k}, s_{k}, …, s_{k}), the set I = {e \ {v} : e ∈ E(H̃_{k})} is the same for all v ∈ R_{k} and it is the edge set of a K^{d}(s_{k}). So we can think of each Z_{v} as being indexed by I.

Corollary 2.2 provides either a lattice point in ⋂_{v∈R_{k}} conv(Z_{v}), and then case (i) of Lemma 3.2 holds, or a smaller I′ ⊆ I such that, for some v_{1}, v_{2} ∈ R_{k}, the restrictions Z′_{v} of the Z_{v} to I′ satisfy conv(Z′_{v_{1}}) ∩ conv(Z′_{v_{2}}) = ∅. Since |I′| contains at least a 2^{−d}-fraction of the edges of a K^{d}(s_{k}), by the Erdős– Simonovits theorem 2.3 there is an integer s_{k+1}, much smaller than s_{k} but still large, such that I′ can be further restricted to I′′ ⊂ I′ that is the edge set of a K^{d}(s_{k+1}). The edge set of the next hypergraph H̃_{k+1} now consists of all edges of H̃_{k} whose restriction to the last d classes lies in I′′; equivalently, it is {e′′ ∪ {v} : e′′ ∈ I′′, v ∈ Ṽ_{1}}. This H̃_{k+1} is a K^{d+1}(s, s_{k+1}, s_{k+1}, …, s_{k+1}) and the r-tuple R_{k} now has two sets with disjoint convex hulls. This finishes the proof of Lemma 3.2, and Proposition 3.1 is proved as well. □

Remark. Our proof of the fractional Helly theorem for convex lattice sets does not use much of the geometric properties of Z^{d}, but still it relies on the special case of the colored Helly theorem 2.4 and on the intermixing lemma 2.1. It would be interesting to clarify what axioms are sufficient for the validity of these two statements, say in the context of abstract convexity spaces.

4 Colored (p, q)-theorems

The colored Helly theorem 2.4 and the Alon–Kleitman method for proving (p, q)-theorems can be combined to prove a colored (p, q) theorem for convex sets in R^{d}:

Theorem 4.1 For every integers d ≥ 1 and p ≥ 1, there exists a T = T (d, p) such that the following holds. Let C_{1}, …, C_{d+1} be finite families of convex sets in R^{d}, and suppose that whenever we select, for each i ∈ [d + 1], sets C_{i1}, C_{i2}, …, C_{ip} ∈ C_{i}, there are j_{1}, j_{2}, …, j_{d+1} ∈ [p] with ⋂_{i=1}^{d+1} C_{i,j_{i}} ≠ ∅. Then τ(C_{i}) ≤ T for at least one i ∈ [d + 1].

Sketch of proof. Let ν^{∗}(F) denote the fractional matching number of a set system F: ν^{∗}(F) is the maximum of ∑_{F ∈F} w(F) for w: F → [0, 1] being a function satisfying ∑_{F ∈F: x∈F} w(F) ≤ 1 for every x ∈ ⋃ F. Alon and Kleitman proved that for any system C of convex sets in R^{d}, τ(C) is bounded by a function of d and ν^{∗}(C), and so it suffices to show that, in our situation, ν^{∗}(C_{i}) is bounded for some i ∈ [d + 1].

Let w_{i}: C_{i} → [0, 1] be a weight function for which ν^{∗}(C_{i}) is attained. Since the C_{i} are finite, we may assume that the values of w are rational. We write w_{i}(C) = \frac{n_{C}}{m_{i}}, where m_{i} is a common denominator of the w_{i}(C), and we form a new system C′_{i}, by putting n_{C} copies of C into C′_{i} for each C ∈ C_{i}. Let n_{i} = ∑_{C∈C_{i}} n_{C} = |C′_{i}|; it suffices to show that for some i, there exists a point x common to at least βn_{i} sets of C′_{i}, for some β = β(d, p) > 0 (since then 1 ≥ ∑_{C∈C_{i}: x∈C} w_{i}(C) ≥ β \frac{n_{i}}{m_{i}} = βν^{∗}(C_{i}), and so ν^{∗}(C_{i}) ≤ \frac{1}{β}).

It is enough to verify the assumptions of the fractional Helly theorem of Katchalski and Liu for some C′_{i}, i.e. to show that there are at least α\binom{n_{i}}{d+1} intersecting (d + 1)-tuples. We consider the (d + 1)-uniform (d + 1)-partite hypergraph H with the vertices in the ith class corresponding to the sets of C′_{i} and the edges corresponding to intersecting (d + 1)-tuples of sets from distinct classes.

Let s be large compared to d and p but fixed, and consider sets U_{1}, …, U_{d+1}, where U_{i} is an arbitrary subset of s vertices in the ith class. We claim that each such selection contributes a (d + 1)-tuple of vertices in one of the U_{i} whose sets intersect; if we verify this, double counting shows that one of the classes of H has at least α\binom{n_{i}}{d+1} intersecting (d + 1)-tuples as needed.

If some U_{i} contains d+1 copies of the same set of C_{i}, then we have a (rather trivial) intersecting (d + 1)-tuple. Otherwise, we select U′_{i} ⊆ U_{i} consisting of at least \frac{s}{d+1} distinct sets. By the condition of the theorem, for any choice of p-element W_{i} ⊂ U′_{i}, there is an edge in ⋃_{i} W_{i}. Double counting and the Erdős–Simonovits theorem 2.3 show that there is a K^{d+1}(d + 1) in the subhypergraph induced in H by the U′_{i}. The colored Helly theorem 2.4 then yields an intersecting (d + 1)-tuple in one of the U′_{i} as required. □

A similar colored (p, q)-theorem can be proved for convex lattice sets, by the same method. As shown in [1], τ(F) is again bounded by a function of d and ν^{∗}(F) for any finite system F of convex lattice sets in Z^{d}. The final application of the colored Helly theorem 2.4 in the proof is replaced by an application of Proposition 3.1 (and we need a K^{d+1}(t) subhypergraph instead of K^{d+1}(d+1)).

Acknowledgment

We would like to thank Van Ha Vu for inspiring discussions at initial stages of the research. We also thank anonymous referees for constructive comments.

References

[1] N. Alon, G. Kalai, J. Matoušek, and R. Meshulam. Transversal numbers for hypergraphs arising in geometry. Adv. Appl. Math., in press.

[2] N. Alon and D. Kleitman. Piercing convex sets and the Hadwiger Debrunner (p, q)-problem. Adv. Math., 96(1):103–112, 1992.

[3] I. Bárány. A generalization of Carathéodory’s theorem. Discrete Math., 40:141–152, 1982.

[4] J.-P. Doignon. Convexity in cristallographical lattices. J. Geometry, 3:71– 85, 1973.

[5] P. Erdős and M. Simonovits. Supersaturated graphs and hypergraphs. Combinatorica, 3:181–192, 1983.

[6] T. Hausel. On a Gallai-type problem for lattices. Acta Math. Hungar., 66:127–145, 1995.

[7] G. Kalai. Intersection patterns of convex sets. Israel J. Math., 48:161–174, 1984.

[8] M. Katchalski and A. Liu. A problem of geometry in R^{n}. Proc. Amer. Math. Soc., 75:284–288, 1979.

[9] L. Lovász. Problem 206. Matematikai Lapok, 25:181, 1974.

[10] S. Onn. On the geometry and computational complexity of Radon partitions in the integer lattice. SIAM J. Discrete Math., 4(3):436–446, 1991.

[11] H. E. Scarf. An observation on the structure of production sets with indivisibilities. Proc. Nat. Acad. Sciences USA, 74:3637–3641, 1977.

[12] G. Sierksma. Relationships between Carathéodory, Helly, Radon and exchange numbers of convexity spaces. Nieuw Arch. Wisk. (3), 25(2):115–132, 1977.