Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler

Publication date: 20 May 2003

Published in: Universitext (Search for Journal in Brave)

fixed points simplicial complexes Borsuk-Ulam theorem Tverberg's theorem colored Tverberg theorem deleted joins Kneser conjecture existence of equivariant maps nonembeddability test set paradigm Van Kampen-Flores theorem

Mathematics Subject Classification ID

Lyusternik-Shnirel'man category of a space, topological complexity à la Farber, topological robotics (topological aspects) (55M30) Planar graphs; geometric and topological aspects of graph theory (05C10) Discriminantal varieties and configuration spaces in algebraic topology (55R80) Coloring of graphs and hypergraphs (05C15) Fixed points and coincidences in algebraic topology (55M20) Helly-type theorems and geometric transversal theory (52A35) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to combinatorics (05-01) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to algebraic topology (55-01) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to convex and discrete geometry (52-01)

Related Items

Algorithmic solvability of the lifting-extension problem ⋮ On well-connected sets of strings ⋮ Strengthening topological colorful results for graphs ⋮ Localization for hyperbolic measures on infinite-dimensional spaces ⋮ Bisecting envelopes of convex polygons ⋮ Equipartitions and Mahler volumes of symmetric convex bodies ⋮ On chromatic numbers of close-to-Kneser distance graphs ⋮ Generalized chessboard complexes and discrete Morse theory ⋮ Measure partitions using hyperplanes with fixed directions ⋮ Existence of continuous maps from $d$-spheres $(d \geq 1)$ to its various triangulations having the disjoint support property ⋮ Unnamed Item ⋮ Envy-free division of multi-layered cakes ⋮ Sections and projections of nested convex bodies ⋮ Exotic elliptic algebras ⋮ The Borsuk-Ulam theorem for planar polygon spaces ⋮ Discrete geometry on colored point sets in the plane -- a survey ⋮ Near equipartitions of colored point sets ⋮ The Borsuk-Ulam type theorems for finite-dimensional compact group actions ⋮ Sharp bounds for the chromatic number of random Kneser graphs ⋮ Bipartite complements of circle graphs ⋮ Rectilinear crossings in complete balanced $d$-partite $d$-uniform hypergraphs ⋮ Edge-critical subgraphs of Schrijver graphs. II: The general case ⋮ Bourgin-Yang versions of the Borsuk-Ulam theorem for $p$-toral groups ⋮ Topology of the Grünbaum–Hadwiger–Ramos hyperplane mass partition problem ⋮ Obstacles for splitting multidimensional necklaces ⋮ Fair splittings by independent sets in sparse graphs ⋮ Amalgamation and Ramsey properties of $L_p$ spaces ⋮ COLORING CURVES ON SURFACES ⋮ Unnamed Item ⋮ $G$-index, topological dynamics and the marker property ⋮ Extendability of simplicial maps is undecidable ⋮ Non-existence of certain type of convex functions on a Riemannian manifold with a pole ⋮ A generalization of Kneser graphs ⋮ Forbidden lifts (NP and CSP for combinatorialists) ⋮ Splitting multidimensional necklaces ⋮ Plus minus analogues for affine Tverberg type results ⋮ Simplex Range Searching and Its Variants: A Review ⋮ Fair Representation by Independent Sets ⋮ On Codimension One Embedding of Simplicial Complexes ⋮ Beyond the Borsuk–Ulam Theorem: The Topological Tverberg Story ⋮ Bounding Helly Numbers via Betti Numbers ⋮ Schrijver Graphs and Projective Quadrangulations ⋮ A glimpse into continuous combinatorics of posets, polytopes, and matroids ⋮ Homomorphism complexes, reconfiguration, and homotopy for directed graphs ⋮ Simplotopal maps and necklace splitting ⋮ Coloring properties of categorical product of general Kneser hypergraphs ⋮ Circular chromatic number of induced subgraphs of Kneser graphs ⋮ Proving Tucker’s Lemma with a volume argument ⋮ Intersection patterns of finite sets and of convex sets ⋮ Helly numbers of acyclic families ⋮ On 4-chromatic Schrijver graphs: their structure, non-3-colorability, and critical edges ⋮ Ham-sandwich cuts and center transversals in subspaces ⋮ Geodesics avoiding subsets in Hadamard manifolds ⋮ Colorful subgraphs in Kneser-like graphs ⋮ Creating semiflows on simplicial complexes from combinatorial vector fields ⋮ An extension of a theorem of Yao and Yao ⋮ Empty monochromatic simplices ⋮ Min-Max payoffs in a two-player location game ⋮ Helly-type theorems for line transversals to disjoint unit balls ⋮ Extensions of Sperner and Tucker's lemma for manifolds ⋮ Analogues of the central point theorem for families with $d$-intersection property in $\mathbb R^d$ ⋮ The Borsuk--Ulam-property, Tucker-property and constructive proofs in combinatorics ⋮ A user's guide to the topological Tverberg conjecture ⋮ On topological minors in random simplicial complexes ⋮ Stable Kneser hypergraphs and ideals in $\mathbb {N}$ with the Nikodým property ⋮ A restriction estimate using polynomial partitioning ⋮ Local chromatic number and distinguishing the strength of topological obstructions ⋮ Computational topology of equivariant maps from spheres to complements of arrangements ⋮ On threshold probability for the stability of independent sets in distance graphs ⋮ A note on interconnecting matchings in graphs ⋮ Realizing RCC8 networks using convex regions ⋮ A point in an $nd$-polytope is the barycenter of $n$ points in its $d$-faces ⋮ Homomorphisms of binary Cayley graphs ⋮ A Tverberg type theorem for matroids ⋮ Free actions on C*-algebra suspensions and joins by finite cyclic groups ⋮ Splitting necklaces and measurable colorings of the real line ⋮ Unavoidable complexes, via an elementary equivariant index theory ⋮ Alexander r-tuples and bier complexes ⋮ Invariants in noncommutative dynamics ⋮ Generalised Mycielski graphs and the Borsuk-Ulam theorem ⋮ Borsuk-Ulam type theorems for manifolds ⋮ WI-posets, graph complexes and $\mathbb{Z}_2$-equivalences ⋮ Crossing patterns of semi-algebraic sets ⋮ Approximation Algorithms for Low-Distortion Embeddings into Low-Dimensional Spaces ⋮ The topological Tverberg theorem and winding numbers ⋮ d-collapsibility is NP-complete for <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:mi>d</mml:mi><mml:mo>⩾</mml:mo><mml:mn>4</mml:mn></mml:math> ⋮ The intermediate value theorem and decision-making in psychology and economics: an expositional consolidation ⋮ A counterexample to a conjecture of Björner and Lovász on the $\chi$-coloring complex ⋮ The Bestvina-Edwards theorem and the Hilbert-Smith conjecture ⋮ Counterexamples to the colorful Tverberg conjecture for hyperplanes ⋮ Topology of geometric joins ⋮ An asymmetric convex body with maximal sections of constant volume ⋮ Characterization of extremal antipodal polygons ⋮ Simplicial shellable spheres via combinatorial blowups ⋮ No-dimensional Tverberg theorems and algorithms ⋮ Envy-free division in the presence of a dragon ⋮ Colouring quadrangulations of projective spaces ⋮ On a topological relaxation of a conjecture of Erdős and Nešetřil ⋮ Borsuk-Ulam type theorems for $G$-spaces with applications to Tucker type lemmas ⋮ Topology of acyclic complexes of tournaments and coloring ⋮ An optimal algorithm for plane matchings in multipartite geometric graphs ⋮ On random subgraphs of Kneser and Schrijver graphs ⋮ Lovász' theorem on the chromatic number of spheres revisited ⋮ Box complexes, neighborhood complexes, and the chromatic number ⋮ Towards a noncommutative Brouwer fixed-point theorem ⋮ A lower bound on the crossing number of uniform hypergraphs ⋮ Dichotomies, structure, and concentration in normed spaces ⋮ Independence numbers of random subgraphs of distance graphs ⋮ A combinatorial proof for the circular chromatic number of Kneser graphs ⋮ On the number of Tverberg partitions in the prime power case ⋮ Topology and combinatorics of partitions of masses by hyperplanes ⋮ Generalizations of Tucker-Fan-Shashkin lemmas ⋮ Generalised Mycielski graphs, signature systems, and bounds on chromatic numbers ⋮ On expansion and topological overlap ⋮ The homology of the cycle matroid of a coned graph ⋮ Bier spheres and barycentric subdivision ⋮ Generalized ham-sandwich cuts ⋮ Hom complexes and hypergraph colorings ⋮ Uniform versions of index for uniform spaces with free involutions ⋮ Nonpolytopal nonsimplicial lattice spheres with nonnegative toric $g$-vector ⋮ On generalized Heawood inequalities for manifolds: a van Kampen-Flores-type nonembeddability result ⋮ Polynomial partitioning for several sets of varieties ⋮ Diameters of random distance graphs ⋮ On the number of colored Birch and Tverberg partitions ⋮ Hardness of embedding simplicial complexes in $\mathbb R^d$ ⋮ A topological central point theorem ⋮ Cutting the same fraction of several measures ⋮ Tverberg-type theorems for intersecting by rays ⋮ The hamburger theorem ⋮ Relative $(p,\varepsilon )$-approximations in geometry ⋮ Optimal bounds for a colorful Tverberg-Vrećica type problem ⋮ New construction of graphs with high chromatic number and small clique number ⋮ Spheres arising from multicomplexes ⋮ A stronger conclusion to the classical ham sandwich theorem ⋮ Altermatic number of categorical product of graphs ⋮ Elementary abelian ${p}$-groups are the only finite groups with the Borsuk-Ulam property ⋮ Polynomial hierarchy, Betti numbers, and a real analogue of Toda's theorem ⋮ A complex analogue of Toda's theorem ⋮ Non-projectability of polytope skeleta ⋮ Realization of subgraphs of random graphs by graphs of diameters in Euclidean spaces ⋮ Isovariant maps from free $C_n$-manifolds to representation spheres ⋮ Countable choice and compactness ⋮ Local topology of the free complex of a two-dimensional generalized convex shelling ⋮ Extreme amenability of $L_0$, a Ramsey theorem, and Lévy groups ⋮ A counterexample to Wegner's conjecture on good covers ⋮ Reconstructing geometric objects from the measures of their intersections with test sets ⋮ A slight improvement to the colored Bárány's theorem ⋮ On the chromatic number of general Kneser hypergraphs ⋮ Random Kneser graphs and hypergraphs ⋮ Average-value Tverberg partitions via finite Fourier analysis ⋮ On the links of vertices in simplicial $d$-complexes embeddable in the Euclidean $2d$-space ⋮ Multiple chessboard complexes and the colored Tverberg problem ⋮ Colorful subhypergraphs in uniform hypergraphs ⋮ On random subgraphs of Kneser graphs and their generalizations ⋮ Tverberg plus minus ⋮ Möbius coinvariants and bipartite edge-rooted forests ⋮ A new lower bound for the chromatic number of general Kneser hypergraphs ⋮ Equal coefficients and tolerance in coloured Tverberg partitions ⋮ Convex geometry and waist inequalities ⋮ Tverberg's theorem with constraints ⋮ Positive-fraction intersection results and variations of weak epsilon-nets ⋮ Computing solutions of the paintshop-necklace problem ⋮ Extreme amenability of abelian $L_0$ groups ⋮ Prodsimplicial-neighborly polytopes ⋮ The chromatic number of almost stable Kneser hypergraphs ⋮ An elementary deduction of the topological Radon theorem from Borsuk-Ulam ⋮ Symmetries of the stable Kneser graphs ⋮ Chessboard complexes indomitable ⋮ Combinatorics of unavoidable complexes ⋮ A combinatorial analog of a theorem of F.J. Dyson ⋮ A tight colored Tverberg theorem for maps to manifolds ⋮ Symmetric multiple chessboard complexes and a new theorem of Tverberg type ⋮ On topological relaxations of chromatic conjectures ⋮ Convex equipartitions via equivariant obstruction theory ⋮ Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique ⋮ On the connectivity of visibility graphs ⋮ Polytopal Bier spheres and Kantorovich-Rubinstein polytopes of weighted cycles ⋮ A Tverberg type theorem for collectively unavoidable complexes ⋮ Rainbow polygons for colored point sets in the plane ⋮ Strong independence and the dimension of a Tverberg set ⋮ Generalization of Kimberling's concept of triangle center for other polygons ⋮ A Turán-type theorem for large-distance graphs in Euclidean spaces, and related isodiametric problems ⋮ Topological obstructions for vertex numbers of Minkowski sums ⋮ Combinatorial Stokes formulas via minimal resolutions ⋮ General Bourgin-Yang theorems ⋮ Orthogonal equipartitions ⋮ On the number of Birch partitions ⋮ Combinatorial groupoids, cubical complexes, and the Lovász Conjecture ⋮ Noncommutative Borsuk-Ulam-type conjectures revisited ⋮ Continuous maps with the disjoint support property ⋮ Covering dimension using toric varieties ⋮ Non-embeddability of geometric lattices and buildings ⋮ A note on the homotopy type of the Alexander dual ⋮ On the realization of subgraphs of a random graph by diameter graphs in Euclidean spaces ⋮ Bounds for Pach's selection theorem and for the minimum solid angle in a simplex ⋮ Graph colorings, spaces of edges and spaces of circuits ⋮ Political structures and the topology of simplicial complexes ⋮ Equilateral polygons in a Euclidean space and on deformed spheres via Fadell-Husseini index ⋮ Kakeya-Brascamp-Lieb inequalities ⋮ Independence numbers and chromatic numbers of some distance graphs ⋮ Topology and Adjunction in Promise Constraint Satisfaction ⋮ A survey of mass partitions ⋮ The Borsuk-Ulam theorem for 3-manifolds ⋮ Envy-free division via configuration spaces ⋮ On the connectivity of the disjointness graph of segments of point sets in general position in the plane ⋮ Some `converses' to intrinsic linking theorems ⋮ ENVY‐FREE DIVISION USING MAPPING DEGREE ⋮ Borsuk-Ulam property and sectional category ⋮ NP-Hardness of Computing PL Geometric Category in Dimension 2 ⋮ Persistent Homology of Semialgebraic Sets ⋮ Interview with Andrei Raigorodskii ⋮ Finite mean dimension and marker property ⋮ Nielsen-Borsuk-Ulam number for maps between tori ⋮ Disjointness graphs of segments in $\mathbb{R}^2$ are almost all Hamiltonian ⋮ Simplifying Inclusion–Exclusion Formulas ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A generalization of Kneser's conjecture ⋮ Obstructions to the realization of distance graphs with large chromatic numbers on spheres of small radii ⋮ Isovariant Borsuk-Ulam results for pseudofree circle actions and their converse ⋮ Unnamed Item ⋮ Topological Bounds for Graph Representations over Any Field ⋮ Unnamed Item ⋮ Spaces of embeddings: Nonsingular bilinear maps, chirality, and their generalizations ⋮ On Spectral Minimal Partitions: the Case of the Sphere ⋮ Recognition of collapsible complexes is NP-complete ⋮ Online unit covering in Euclidean space ⋮ On the Chromatic Number of Matching Kneser Graphs ⋮ Ham-Sandwich Cuts and Center Transversals in Subspaces ⋮ The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg