Covering and labeling generalizations of the Borsuk–Ulam theorem
Florian Frick, Zoe Wellner · 2025
Read Covering and labeling generalizations of the Borsuk–Ulam theorem by Florian Frick, Zoe Wellner (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-07247.txt.
Introduction
Florian Frick and 1 co-author prove broad generalizations in 2025 of the Borsuk-Ulam theorem, a classic result in topology. The theorem says any continuous map from a sphere to lower-dimensional space sends some opposite pair of points to the same place. Their route runs through Fan's combinatorial labeling result for triangulations of spheres, which they extend in several directions.
The extensions do more than bound complexity, the usual use of Borsuk-Ulam: they also reveal the structure of objects that meet the bound. That structure is governed by order types of point sets and by how faces intersect under maps from a simplex. Applications include sphere coverings, Kneser-type colorings, Hall-type matching results, and mass partitions by hyperplanes. A new proof of the topological Hall theorem falls out along the way. The work unifies tools that combinatorial geometers reach for often.
Catalog record
| CREATOR | Florian Frick, Zoe Wellner |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 79 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-07247
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Covering and labeling generalizations of the Borsuk–Ulam theorem Thanks: FF and ZW were supported by NSF CAREER Grant DMS 2042428. Florian Frick, Zoe Wellner Abstract . We prove multiple generalizations of Fan’s combinatorial labeling result for sphere triangulations. This can be seen as a comprehensive extension of the Borsuk–Ulam theorem. In typical applications, the Borsuk–Ulam theorem gives complexity bounds in a suitable sense, whereas our extension additionally provides insight into the structure of objects satisfying the complexity bound. This structure is governed by order types of finite point sets in Euclidean space and more generally by the intersection combinatorics of faces under continuous maps from the simplex. We develop some of those applications for sphere coverings, Kneser-type colorings, Hall-type results for hypergraphs, and hyperplane mass partitions, among other consequences. We provide a new proof of the topological Hall theorem and extend it into a result that simultaneously generalizes hypergraph Hall theorems and topological lower bounds for chromatic numbers. 1. Introduction The Borsuk–Ulam theorem [ 13 ] has found numerous applications across mathematical disciplines from geometric partitioning results in convex geometry [ 58 ] , chromatic numbers in combinatorics [ 45 ] , consensus-halving and fair division [ 63 ] , fixed-point theorems in topology and non-linear analysis [ 69 , 73 ] , as well as the minimax variational inequalities frequently used in game theory derived from these fixed point theorems [ 11 , 23 ] , existence results for solutions of nonlinear PDEs [ 55 ] , dissimilarity [ 1 , 41 ] and distortion [ 8 ] in metric geometry, and inscribability [ 5 ] and incidence [ 9 ] problems in geometric topology, to problems concerning algorithmic complexity of approximate graph coloring [ 6 ] and PAC learning [ 15 , 33 ] in theoretical computer science. See Matoušek’s book for some applications [ 46 ] . The Borsuk–Ulam theorem states that any continuous map f\colon S^{d}\to\mathbb{R}^{d} defined on the d -sphere S^{d} has a zero, provided that f is odd , that is, f(-x)=-f(x) for all x\in S^{d} . In typical applications of this result, the zero of f corresponds to a desired solution of the problem. Fan proved a far-reaching generalization of the Borsuk–Ulam theorem that can be phrased as follows: Theorem 1.1 (Fan [ 22 ] ) . Let m be a positive integer, and let A_{1},\dots,A_{m}\subset S^{d} be closed sets such that A_{i}\cap(-A_{i})=\varnothing for all i\in[m] and \bigcup_{i}A_{i}\cup\bigcup_{i}(-A_{i})=S^{d} . Then there are indices i_{1}<i_{2}<\dots<i_{d+1} such that \bigcap_{j=1}^{d+1}(-1)^{j}A_{i_{j}}\neq\varnothing . For f\colon S^{d}\to\mathbb{R}^{m} an odd map without zeros, let A_{i}=\{x\in S^{d}\,|\,f_{i}(x)\geq\varepsilon\} . By compactness of S^{d} , the A_{i} and their negatives -A_{i} cover the sphere for sufficiently small \varepsilon . Fan’s result thus provides structural insight into odd maps without zeros: They do not exist for m\leq d , and for m>d Fan derives a result about the simultaneous maximization of the absolute value of some d+1 coordinates of f . We explain the utility of this extension of the Borsuk–Ulam theorem in an example: The Borsuk–Ulam theorem yields a lower bound for the chromatic number \chi(G) of a graph G ; Fan’s theorem gives structural results for proper colorings of G with (necessarily) at least \chi(G) colors; see [ 24 , 32 , 64 , 65 ] for various such examples. It is thus of interest to study the general space of results that extend Fan’s theorem, since those results govern the structure of a variety of mathematical problems—those that can be solved through an application of the Borsuk–Ulam theorem. As m-d grows the combinatorial patterns of indices and signs that yield non-empty intersections as in Fan’s theorem become surprisingly rich and are determined by Radon-type (convex hull) intersection results of m points in \mathbb{R}^{d-1} . Concretely we prove: Theorem 1.2 . Let m be a positive integer, and let X=\{x_{1},\dots,x_{m}\}\subset\mathbb{R}^{d-1} be a set of m points. Let A_{1},\dots,A_{m}\subset S^{d} be closed sets such that A_{i}\cap(-A_{i})=\varnothing for all i\in[m] and \bigcup_{i}A_{i}\cup\bigcup_{i}(-A_{i})=S^{d} . Then there are disjoint subsets S,T\subset[m] such that \conv\{x_{i}\,|\,i\in S\}\cap\conv\{x_{i}\,|\,i\in T\}\neq\varnothing\ \text{and}\ \bigcap_{i\in S}A_{i}\cap\bigcap_{i\in T}(-A_{i})\neq\varnothing. Fan’s result follows from placing X in cyclic position [ 29 ] . Thus Fan’s theorem corresponds to a single order type of m points as in Theorem 1.2 , but every such order type, of which there are many [ 31 ] , yields another variant of Fan’s theorem. In fact, Fan proves an equivalent result for labelings of sphere triangulations, and shows moreover that the number of facets that are alternatingly labeled is odd. We also prove a strengthening of the corresponding labeling result; see Theorem 2.2 . We then prove a colorful generalization of Theorem 1.2 , see Theorem 2.6 extending our earlier work [ 27 ] . While we phrase Theorem 1.2 as intersection combinatorics of convex hulls constraining intersections of closed sets in sphere coverings (or in the contrapositive, intersection combinatorics in sphere coverings constraining intersections of convex hulls), our result admits a “continuous generalization,” where convex hulls are replaced with continuous images under a map from the simplex on X ; see Theorem 2.5 . Our proof of Theorem 1.2 is a short and simple reduction to the Borsuk–Ulam theorem. Even for the special case of Fan’s theorem our proof might be the simplest in the literature; compare [ 20 , 53 ] for a simple proof of Fan’s theorem in the case m=d+1 . In particular, our proof of finding an approximate point of intersection in the full generality of Theorems 1.1 and 1.2 is constructive and exhibits the corresponding search problem as lying in PPA [ 4 ] ; see [ 54 ] for a constructive proof of Fan’s theorem and [ 26 ] for a constructive proof of Tucker’s lemma. In Section 2 we present the proofs of the main results. In Sections 3 , 4 , and 5 we collect consequences of these results, that is, for various applications of the Borsuk–Ulam theorem, we develop results about the structure of solutions that go beyond mere non-existence. Section 3 collects topological consequences about sphere coverings, embeddings, odd maps without common zeros, and connections to related fixed point theorems; Section 4 gives combinatorial consequences, and Section 5 generalizations of the ham sandwich theorem in discrete geometry. Concretely, • we deduce results about the intersection combinatorics of sphere coverings such as a colorful generalization of Fan’s theorem, see Corollary 3.1 , a colorful Lusternik–Schnirelman theorem, see Corollary 3.2 , and a colorful generalization of the local Lusternik–Schnirelman theorem of Chase, Chornomaz, Moran, and Yehudayoff [ 15 ] , see Corollary 3.3 . • We exhibit various non-embeddability results for simplicial complexes as special cases of Theorem 2.5 , the continuous extension of Theorem 1.2 , see Subsection 3.2 . • We prove a generalization of Fan’s theorem about the existence of points, where a set of odd real-valued maps is minimized or maximized; see Corollary 3.7 . • Subsection 3.4 briefly surveys fixed-point theorems, such as Komiya’s theorem [ 39 ] , that our main result generalizes to the equivariant setting. • In Subsection 4.1 , we give general results on the existence of rainbow faces (see Corollary 4.6 ) that generalize topological lower bounds for chromatic numbers of