On the gap between representability and collapsibility
| dc.creator | Matousek, Jiri | |
| dc.creator | Tancer, Martin | |
| dc.date | 2008-03-25 | |
| dc.date.accessioned | 2026-07-07T09:28:17Z | |
| dc.date.available | 2026-07-07T09:28:17Z | |
| dc.description | A simplicial complex K is called d-representable if it is the nerve of a collection of convex sets in R^d; K is d-collapsible if it can be reduced to an empty complex by repeatedly removing a face of dimension at most d-1 that is contained in a unique maximal face; and K is d-Leray if every induced subcomplex of K has vanishing homology of dimension d and larger. It is known that d-representable implies d-collapsible implies d-Leray, and no two of these notions coincide for d greater or equal to 2. The famous Helly theorem and other important results in discrete geometry can be regarded as results about d-representable complexes, and in many of these results "d-representable" in the assumption can be replaced by "d-collapsible" or even "d-Leray". We investigate "dimension gaps" among these notions, and we construct, for all positive integers d, a 2d-Leray complex that is not (3d-1)-collapsible and a d-collapsible complex that is not (2d-2)-representable. In the proofs we obtain two results of independent interest: (i) The nerve of every finite family of sets, each of size at most d, is d-collapsible. (ii) If the nerve of a simplicial complex K is d-representable, then K embeds in R^d. | |
| dc.description | 10 pages, 3 figures | |
| dc.identifier | https://arxiv.org/abs/0803.3520 | |
| dc.identifier | http://arxiv.org/abs/0803.3520 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/157398 | |
| dc.subject | Combinatorics | |
| dc.subject | 52A20; 55U10 | |
| dc.title | On the gap between representability and collapsibility | |
| dc.type | text |