Colourful and Fractional (p,q)-theorems
Por:
Bárány I., Fodor F., Montejano L., Oliveros D., Pór A.
Publicada:
1 abr 2014
Resumen:
Let p=q=d+1 be positive integers and let F be a finite family of convex sets in Rd. Assume that the elements of F are coloured with p colours. A p-element subset of F is heterochromatic if it contains exactly one element of each colour. The family 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 a fraction of the p-tuples in F. We show that, in the case that d=1, all but a ß fraction of the elements of F can be pierced by p-q+1 points. Here ß depends on a and p,q, and ß?0 as a goes to zero. © 2013 Springer Science+Business Media New York.
|