Colourful and Fractional (p,q)-theorems

• Published in: Discrete & computational geometry 2014-04, Vol.51 (3), p.628-642
• Main Authors: Bárány, I., Fodor, F., Montejano, L., Oliveros, D., Pór, A.
• Format: Article
• Language: English
• Subjects: Color; Colour; Combinatorics; Computational geometry; Computational Mathematics and Numerical Analysis; Estimates; Geometry; Integers; Mathematical analysis; Mathematics; Mathematics and Statistics; Texts; Theorems
• ISSN: 0179-5376; 1432-0444
• DOI: 10.1007/s00454-013-9559-0

Let p ≥ q ≥ d +1 be positive integers and let be a finite family of convex sets in . Assume that the elements of are coloured with p colours. A p -element subset of is heterochromatic if it contains exactly one element of each colour. The family 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 . We show that, in the case that d =1, all but a β fraction of the elements of can be pierced by p − q +1 points. Here β depends on α and p , q , and β →0 as α goes to zero.