NERVES OF GOOD COVERS ARE ALGORITHMICALLY UNRECOGNIZABLE

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F13%3A10190000" target="_blank" >RIV/00216208:11320/13:10190000 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1137/120891204" target="_blank" >http://dx.doi.org/10.1137/120891204</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1137/120891204" target="_blank" >10.1137/120891204</a>

Jazyk výsledku

angličtina

Název v původním jazyce

NERVES OF GOOD COVERS ARE ALGORITHMICALLY UNRECOGNIZABLE

Popis výsledku v původním jazyce

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-representa

Název v anglickém jazyce

NERVES OF GOOD COVERS ARE ALGORITHMICALLY UNRECOGNIZABLE

Popis výsledku anglicky

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-representa

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2013

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

SIAM JOURNAL ON COMPUTING

ISSN

0097-5397

e-ISSN

—

Svazek periodika

42

Číslo periodika v rámci svazku

4

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

23

Strana od-do

1697-1719

Kód UT WoS článku

000323889100011

EID výsledku v databázi Scopus

—