Transversal ratio approaching one for simplicial four-polytopes
For a simplicial convex polytope $P$ with vertex set $V(P)$, let $\tau(P)$ be the smallest size of a set of vertices meeting the vertex set of every facet of $P$, and call $\tau(P)/|V(P)|$ the transversal ratio of $P$. Briggs, Dobbins and Lee showed that the supremum of the transversal ratio over simplicial $3$-polytopes is $1/2$, and Novik and Zheng constructed simplicial $3$-spheres whose transversal ratios converge to $4/7$. Dobbins and Lee proved that for every $d \ge 5$ and every $r < 1$ there is a simplicial $d$-polytope with transversal ratio at least $r$. A coloring of $V(P)$ with $k$ colors and no monochromatic facet gives $\tau(P) \le (1 - 1/k)|V(P)|$, so a positive answer would also give simplicial $4$-polytopes whose facets need arbitrarily many colors. Lee and Nevo asked for the largest number of colors that the facets of a $d$-polytope can need, $d \ge 4$, and proved that the facets of triangulations of the $3$-sphere can need arbitrarily many colors.
Problem. Is it true that for every $\varepsilon > 0$ there is a full-dimensional simplicial convex polytope $P \subset \mathbb{R}^4$ with $$\tau(P) \ge (1 - \varepsilon)|V(P)|?$$ Equivalently, for every $\varepsilon > 0$ there should be such a $P$ in which every set of more than $\varepsilon |V(P)|$ vertices contains all four vertices of some facet.
Source: Dobbins and Lee (2026), Conjecture 1.4, who conjecture a positive answer; the question of the largest transversal ratio of simplicial polytopes is Holmsen's (see Dobbins and Lee, Question 1.3).
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Secondary
- MG
- Keywords
- AIM Open Applied Problems, hypergraph transversals, simplicial polytopes, weak colorings
References
@misc{dobbins2026,
author = {Dobbins, Michael Gene and Lee, Seunghun},
title = {Polytopes with large transversal ratio},
year = {2026},
eprint = {2603.16298},
archivePrefix = {arXiv},
}
@article{lee2026,
author = {Lee, Seunghun and Nevo, Eran},
title = {On colorings of hypergraphs embeddable in {$\mathbb{R}^d$}},
journal = {Discrete Comput. Geom.},
volume = {76},
number = {3},
year = {2026},
pages = {1942--1959},
doi = {10.1007/s00454-026-00856-4},
eprint = {2307.14195},
archivePrefix = {arXiv},
}
@article{briggs2024,
author = {Briggs, Joseph and Dobbins, Michael Gene and Lee, Seunghun},
title = {Transversals and colorings of simplicial spheres},
journal = {Discrete Comput. Geom.},
volume = {71},
number = {2},
year = {2024},
pages = {738--763},
doi = {10.1007/s00454-023-00520-1},
eprint = {2111.06560},
archivePrefix = {arXiv},
}
@article{novik2026,
author = {Novik, Isabella and Zheng, Hailun},
title = {Transversal numbers of simplicial polytopes, spheres, and pure complexes},
journal = {SIAM J. Discrete Math.},
volume = {40},
number = {1},
year = {2026},
pages = {192--213},
doi = {10.1137/24M1682361},
eprint = {2407.19693},
archivePrefix = {arXiv},
}
@misc{aim-four-polytope-transversal-ratio,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Transversal ratio approaching one for simplicial four-polytopes}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/24edaadc6bb272737d8da0745c662c992db07b22/problems/614-four-polytope-transversal-ratio.md},
note = {Entry 614 at commit 24edaad, 2026-10-15},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00868, "Transversal ratio approaching one for simplicial four-polytopes", clopen.solutions.