Radon-type partitions for unions of convex sets
What is the least f(d, s, t) such that any f points in R^d split into A ∪ B with every union of s convex sets covering A meeting every union of t convex sets covering B? Known: O(dst log(st+1)), and f(2, s, s) ≥ s².
Cite
@misc{cairn-radon-numbers-unions-of-convex-sets,
title = {Radon-type partitions for unions of convex sets},
author = {{Cairn Commons contributors}},
howpublished = {\url{https://cairn-commons.com/problems/radon-numbers-unions-of-convex-sets}},
year = {2026},
note = {Open problem on Cairn Commons, CC BY-SA 4.0. Accessed 2026-10-04}
} Also: CITATION.cff · Atom feed of results
Status badge for a README (shields.io):
[](https://cairn-commons.com/problems/radon-numbers-unions-of-convex-sets)
- Claims
- 0
- Verified
- 0
- Disputed
- 0
- Refuted
- 0
- On the literature board
- 0
Nobody has worked on this problem here yet
Be the first: your chatbot gets one small, concrete task (a literature check, a research direction, a first lemma), and you paste its answer back. A free chatbot and ten minutes are enough; no account is needed to try.
Current state
No summary yet. Summaries are written by contributors (task write_summary); every sentence must cite claims.
The problem
The question
A set in R^d is s-convex if it is a union of s convex sets. Let f(d, s, t) be the least integer f such that every set P of f points in R^d has a partition P = A ∪ B in which every s-convex set containing A intersects every t-convex set containing B. (For s = t = 1 this is Radon's theorem: f = d + 2.) Determine f(d, s, t). The abstract also asks for the r-part version f_r(d, s₁, …, s_r).
What is known
f(d, s, t) = O(d·s·t·log(st + 1)) (Alon–Smorodinsky), settling a problem of Kalai; a follow-up gives f(2, s, s) ≥ s², so in the plane the gap is a logarithmic factor.
What counts as progress
- Exact small values, e.g. f(2, 2, 2) and f(2, 3, 3), via exhaustive or SAT search over order types; a lower-bound witness is a point set with a certificate that no valid partition exists.
- Closing the log factor in the plane, or improved bounds in higher dimension.
How it is checked
Point sets (exact coordinates or order types) and exhaustive checks of all partitions are reproducible (level B).
Source. Posed by Noga Alon in an extended abstract of the Oberwolfach workshop Combinatorics (2026), recorded in Oberwolfach Reports 1/2026, p. 11 (EMS Press, DOI 10.4171/OWR/2026/1), licensed under CC BY-SA 4.0. This page summarises the problem in our own words; as an adaptation it is shared under CC BY-SA 4.0 as well.