McMullen problem

The McMullen problem is an open problem in discrete geometry named after Peter McMullen.

Unsolved problem in mathematics: For how many points is it always possible to projectively transform the points into convex position? (more unsolved problems in mathematics)

Statement

In 1972, McMullen proposed the following problem:[1]

Determine the largest number ${\displaystyle \nu (d)}$ such that for any given ${\displaystyle \nu (d)}$ points in general position in affine d-space R^d there is a projective transformation mapping these points into convex position (so they form the vertices of a convex polytope).

Equivalent formulations

Gale transform

Using the Gale transform, this problem can be reformulated as:

Determine the smallest number ${\displaystyle \mu (d)}$ such that for every set of ${\displaystyle \mu (d)}$ points X = {x₁, x₂, ..., x_μ(d)} in linearly general position on S^{d − 1} it is possible to choose a set Y = {ε₁x₁, ε₂x₂, ..., ε_μ(d)x_μ(d)} where ε_i = ±1 for i = 1, 2, ..., μ(d), such that every open hemisphere of S^{d − 1} contains at least two members of Y.

The number ${\displaystyle \mu (k)}$, ${\displaystyle \nu (d)}$ are connected by the relationships

${\displaystyle \mu (k)=\min\{w\mid w\leq \nu (w-k-1)\}\,}$

${\displaystyle \nu (d)=\max\{w\mid w\geq \mu (w-d-1)\}\,}$

Partition into nearly-disjoint hulls

Also, by simple geometric observation, it can be reformulated as:

Determine the smallest number ${\displaystyle \lambda (d)}$ such that for every set X of ${\displaystyle \lambda (d)}$ points in R^d there exists a partition of X into two sets A and B with

${\displaystyle \operatorname {conv} (A\backslash \{x\})\cap \operatorname {conv} (B\backslash \{x\})\not =\varnothing ,\forall x\in X.\,}$

The relation between ${\displaystyle \mu }$ and ${\displaystyle \lambda }$ is

${\displaystyle \mu (d+1)=\lambda (d),\qquad d\geq 1\,}$

Projective duality

An arrangement of lines dual to the regular pentagon. Every five-line projective arrangement, like this one, has a cell touched by all five lines. However, adding the line at infinity produces a six-line arrangement with six pentagon faces and ten triangle faces; no face is touched by all of the lines. Therefore, the solution to the McMullen problem for d = 2 is ν = 5.

The equivalent projective dual statement to the McMullen problem is to determine the largest number ${\displaystyle \nu (d)}$ such that every set of ${\displaystyle \nu (d)}$ hyperplanes in general position in d-dimensional real projective space form an arrangement of hyperplanes in which one of the cells is bounded by all of the hyperplanes.

Results

This problem is still open. However, the bounds of ${\displaystyle \nu (d)}$ are in the following results:

• David Larman proved that ${\displaystyle 2d+1\leq \nu (d)\leq (d+1)^{2}}$. (1972)[1]
• Michel Las Vergnas proved that ${\displaystyle \nu (d)\leq {\frac {(d+1)(d+2)}{2}}}$. (1986)[2]
• Jorge Luis Ramírez Alfonsín proved that ${\displaystyle \nu (d)\leq 2d+\lceil {\frac {d+1}{2}}\rceil }$. (2001)[3]

The conjecture of this problem is ${\displaystyle \nu (d)=2d+1}$, and it is true for d = 2, 3, 4.[1][4]

References

1. D. G. Larman (1972), "On Sets Projectively Equivalent to the Vertices of a Convex Polytope", Bulletin of the London Mathematical Society 4, pp.6–12
2. M. Las Vergnas (1986), "Hamilton Paths in Tournaments and a Problem McMullen on Projective Transformations in R^d", Bulletin of the London Mathematical Society 18, pp.571–572
3. J. L. Ramírez Alfonsín (2001), "Lawrence Oriented Matroids and a Problem of McMullen on Projective Equivalences of Polytopes", European Journal of Combinatorics 22, pp.723–731
4. D. Forge, M. Las Vergnas and P. Schuchert (2001), "A Set of 10 Points in Dimension 4 not Projectively Equivalent to the Vertices of Any Convex Polytope", European Journal of Combinatorics 22, pp.705–708