Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Nerves Of Good Covers Are Algorithmically Unrecognizable
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.).
2013 (English)In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 42, no 4, 1697-1719 p.Article in journal (Refereed) Published
Abstract [en]

A good cover in R-d is a collection of open contractible sets in R-d such that the intersection of any subcollection is either contractible or empty. Motivated by an analogy with convex sets, intersection patterns of good covers were studied intensively. Our main result is that intersection patterns of good covers are algorithmically unrecognizable. More precisely, the intersection pattern of a good cover can be stored in a simplicial complex called a nerve which records which subfamilies of the good cover intersect. A simplicial complex is topologically d-representable if it is isomorphic to the nerve of a good cover in R-d. We prove that it is undecidable whether a given simplicial complex is topologically d-representable for any fixed d >= 5. The result remains valid if we replace good covers with acyclic covers or with covers by open d-balls. As an auxiliary result we prove that if a simplicial complex is piecewise-linearly embeddable into R-d, then it is topologically d-representable. We also supply this result with showing that if a "sufficiently fine" subdivision of a k-dimensional complex is d-representable and k <= 2d-3/3, then the complex is piecewise-linearly embeddable into R-d.

Place, publisher, year, edition, pages
2013. Vol. 42, no 4, 1697-1719 p.
Keyword [en]
good cover, algorithmic undecidability, intersection pattern, nerve, piecewise-linear embedding
National Category
Mathematics Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-129140DOI: 10.1137/120891204ISI: 000323889100011Scopus ID: 2-s2.0-84884923782OAI: oai:DiVA.org:kth-129140DiVA: diva2:650094
Funder
EU, European Research Council, 267165
Note

QC 20130919

Available from: 2013-09-19 Created: 2013-09-19 Last updated: 2017-12-06Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Tancer, Martin
By organisation
Mathematics (Dept.)
In the same journal
SIAM journal on computing (Print)
MathematicsComputer Science

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 78 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf