Convex Hulls of Selected Barycenters

Definitions and mathematical statement

Let $n,d,k$ be integers with $n\geq 1$, $d\geq 1$, and $1\leq k\leq n$. These are the conventional nondegenerate parameter ranges; the supplied statement does not explicitly specify them. Let $[n]=\{1,\ldots,n\}$, and let $P=\{p_1,\ldots,p_n\}\subset{\mathbb{R}}^d$ be a set of $n$ distinct points. For each $I\subseteq[n]$ with $|I|=k$, define its $k$-point barycenter by \[ b_I=\frac{1}{k}\sum_{i\in I}p_i, \qquad B_k(P)=\{b_I:I\subseteq[n],\ |I|=k\}. \] Thus each barycenter uses $k$ distinct points; coincident barycenters arising from different index sets represent the same point of $B_k(P)$. No general-position or full-dimensionality assumption is supplied.

For a nonempty subset $S\subseteq B_k(P)$, let $Q_S=\operatorname{conv}(S)$. Write $\operatorname{vert}(Q_S)$ for its set of extreme points, where $x\in Q_S$ is extreme if $x=ty+(1-t)z$, with $y,z\in Q_S$ and $0<t<1$, implies $y=z=x$.

Determine, as a function of $n,d,k$, the extremal quantity \[ M_d(n,k)= \max_{\substack{P\subset{\mathbb{R}}^d\\ |P|=n}} \ \max_{\varnothing\ne S\subseteq B_k(P)} \left|\operatorname{vert}(\operatorname{conv}(S))\right|. \] The selected subset $S$ is arbitrary and need not contain every $k$-point barycenter. Restricting to nonempty selections avoids a convention for the convex hull of the empty set and does not change the maximum if an empty selection is assigned zero vertices.

Source qualifications. The supplied record labels this problem open and reports a corrected, source-verified reconstruction; these are supplied curation claims, not independent verification here. The raw extraction continues into separate questions about dihedral angles and box intersection graphs. Those questions are not included in the extremal quantity above, and their adjacent proposer labels do not establish authorship of the barycenter question.

Short English statement

Choose $n$ distinct points in ${\mathbb{R}}^d$, form the averages of all $k$-element subsets, and select any nonempty collection of these averages. Determine the largest possible number of vertices of the selected collection's convex hull, maximizing over both the original points and the selection. The parameter ranges and extraction boundaries stated above require human review; the supplied open-status label has not been independently verified.

Sources

• Local UnsolvedMath registry, permanent ID $30005822$, title Convex Hulls of Selected Barycenters, exact source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. The supplied record gives proposed year 2024 and no proposer in its proposer field.
• Supplied primary report citation: Discrete Geometry (2024), Oberwolfach Reports, DOI 10.4171/owr/2024/3, pp. 137--202. https://doi.org/10.4171/owr/2024/3. The record states that its reconstructed statement was checked against the official report; that check has not been independently repeated here.
• Supplied literature source: Martinez-Sandoval and Padrol, The convex dimension of hypergraphs. https://arxiv.org/abs/1909.01189.
• Supplied literature source: Oberwolfach Report 3/2024. https://ems.press/content/serial-article-files/48651.
• Literature assessment dated 2026-08-22: supplied dated curation, not independently verified. It labels the problem open and states that results on convex dimension and special barycenter polytopes provide partial bounds, while no general extremal formula is known. The supplied background explicitly requests independent verification of time-sensitive status and cited claims.
• Adjacent extraction material labels Problem 18 with Karim Adiprasito and Problem 19 with Bartosz Walczak. Their placement does not reliably attribute the preceding barycenter question to either person.
• References appearing in the adjacent box-intersection discussion, retained as extraction context rather than evidence for the barycenter problem: [1] E. Asplund and B. Grünbaum, On a coloring problem, Math. Scand. 8, 181--188, 1960; [2] J. P. Burling, On coloring problems of families of polytopes, PhD thesis, University of Colorado, Boulder, 1965; [3] B. Walczak, Triangle-free geometric intersection graphs with no large independent sets, Discrete Comput. Geom. 53. The supplied citation [3] is incomplete.