Colourful and Fractional (p,q)-theorems

• DOI: 10.1007/s00454-013-9559-0
• Publication Date: 2013-11-11T15:30:27Z
• Authors: I. Bárány; F. Fodor; L. Montejano; D. Oliveros; A. Pór
• Keywords: Zero (linguistics); Fraction (chemistry)

Let p≥q≥d+1 be positive integers and let ${\mathcal{F}}$ be a finite family of convex sets in ${\mathbb{R}}^{d}$ . Assume that the elements of ${\mathcal{F}}$ are coloured with p colours. A p-element subset of ${\mathcal{F}}$ is heterochromatic if it contains exactly one element of each colour. The family ${\mathcal{F}}$ has the heterochromatic (p,q)-property if in every heterochromatic p-element subset there are at least q elements that have a point in common. We show that, under the heterochromatic (p,q)-condition, some colour class can be pierced by a finite set whose size we estimate from above in terms of d,p, and q. This is a colourful version of the famous (p,q)-theorem. (We prove a colourful variant of the fractional Helly theorem along the way.) A fractional version of the same problem is when the (p,q)-condition holds for all but an α fraction of the p-tuples in ${\mathcal{F}}$ . We show that, in the case that d=1, all but a β fraction of the elements of ${\mathcal{F}}$ can be pierced by p−q+1 points. Here β depends on α and p,q, and β→0 as α goes to zero.