A fractional Helly theorem for boxes

摘要

Let F be a family of n axis-parallel boxes in R-d and alpha is an element of(1 - 1/d, 1] a real number. There exists a real number beta(alpha) > 0 such that if there are alpha((n)(2)) intersecting pairs in F, then F contains an intersecting subfamily of size beta n. A simple example shows that the above statement is best possible in the sense that if alpha <= 1 - 1/d, then there may be no point in R-d that belongs to more than d elements of F. (C) 2014 Elsevier B.V. All rights reserved.