Math 2.0

Convex and discrete geometry Convex sets: basic notions Theorem

Fractional Helly theorem

Builds on Convex setHelly's theorem

Statement

Let d≥1d \ge 1 be an integer and let α∈(0,1]\alpha \in (0, 1]. There is a number β=β(d,α)>0\beta = \beta(d, \alpha) > 0 with the following property. Let ℱ\mathcal{F} be a finite family of n≥d+1n \ge d + 1 convex sets in ℝd\R^d. Assume that at least α(nd+1)\alpha \binom{n}{d+1} of the subfamilies of ℱ\mathcal{F} with d+1d + 1 members have a common point. Then some point of ℝd\R^d lies in at least βn\beta n members of ℱ\mathcal{F}.

Remarks

The theorem is due to Katchalski and Liu. One can take β=1−(1−α)1/(d+1)\beta = 1 - (1 - \alpha)^{1/(d+1)}, a value found by Kalai, and this value is the best possible. A proof looks at the lexicographically smallest points of the nonempty intersections of dd-element subfamilies and counts how often each such point is caught by the (d+1)(d+1)-subfamilies. For α=1\alpha = 1 every d+1d + 1 members meet, and Helly's theorem gives a point in all nn members. The constant β\beta depends only on dd and α\alpha, not on nn or on the sets.

Going deeper

For a student

The fractional Helly theorem is the key step in the proof of the (p,q)(p, q)-theorem of Alon and Kleitman. It is a basic tool in the theory of geometric transversals. Together with Helly's theorem and the centerpoint theorem, it belongs to the core of combinatorial convexity.

Reading path

To understand this page from the ground up, read these 8 pages in order. The foundations come first.

Show the path as a graph
Compact set, concept, no evidence levelCompact setconceptConvex hull, concept, no evidence levelConvex hullconceptConvex set, concept, no evidence levelConvex setconceptEuclidean space, object, no evidence levelEuclidean spaceobjectPartition of a set, concept, no evidence levelPartition of a setconceptRadon's theorem, statement, no evidence levelRadon's theoremstatementHelly's theorem, statement, no evidence levelHelly's theoremstatementFractional Helly theorem, statement, no evidence levelFractional Helly theo…statement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Compact set concept
  2. Convex hull concept
  3. Convex set concept
  4. Euclidean space object
  5. Partition of a set concept
  6. Radon's theorem statement
  7. Helly's theorem statement
  8. Fractional Helly theorem statement

Further reading

  1. Web https://en.wikipedia.org/wiki/Helly's_theorem
About this page
TagK9JAYYA0WS
URIm2://K9JAYYA0WS
Kindstatement, theorem
WritingW0 stub
MSC52A35
StatusThis copy of the site has no build data. Run m2 status K9JAYYA0WS.
AboutConvex set
UsesConvex set, Helly's theorem

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.