This HTML5 document contains 44 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
n20http://localhost/temp/predkladatel/
n6http://linked.opendata.cz/resource/domain/vavai/projekt/
n5http://linked.opendata.cz/resource/domain/vavai/riv/tvurce/
n8http://linked.opendata.cz/resource/domain/vavai/subjekt/
n7http://linked.opendata.cz/ontology/domain/vavai/
shttp://schema.org/
skoshttp://www.w3.org/2004/02/skos/core#
rdfshttp://www.w3.org/2000/01/rdf-schema#
n3http://linked.opendata.cz/ontology/domain/vavai/riv/
n16http://bibframe.org/vocab/
n2http://linked.opendata.cz/resource/domain/vavai/vysledek/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n17http://linked.opendata.cz/ontology/domain/vavai/riv/klicoveSlovo/
n21http://linked.opendata.cz/ontology/domain/vavai/riv/duvernostUdaju/
xsdhhttp://www.w3.org/2001/XMLSchema#
n15http://linked.opendata.cz/resource/domain/vavai/vysledek/RIV%2F00216208%3A11320%2F13%3A10190000%21RIV14-GA0-11320___/
n19http://linked.opendata.cz/ontology/domain/vavai/riv/aktivita/
n12http://linked.opendata.cz/ontology/domain/vavai/riv/jazykVysledku/
n18http://linked.opendata.cz/ontology/domain/vavai/riv/obor/
n14http://linked.opendata.cz/ontology/domain/vavai/riv/druhVysledku/
n13http://reference.data.gov.uk/id/gregorian-year/

Statements

Subject Item
n2:RIV%2F00216208%3A11320%2F13%3A10190000%21RIV14-GA0-11320___
rdf:type
skos:Concept n7:Vysledek
rdfs:seeAlso
http://dx.doi.org/10.1137/120891204
dcterms:description
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 %22sufficiently fine%22 subdivision of a k-dimensional complex is d-representable and k {= 2d-3/3, then the complex is piecewise-linearly embeddable into R^d. 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 %22sufficiently fine%22 subdivision of a k-dimensional complex is d-representable and k {= 2d-3/3, then the complex is piecewise-linearly embeddable into R^d.
dcterms:title
NERVES OF GOOD COVERS ARE ALGORITHMICALLY UNRECOGNIZABLE NERVES OF GOOD COVERS ARE ALGORITHMICALLY UNRECOGNIZABLE
skos:prefLabel
NERVES OF GOOD COVERS ARE ALGORITHMICALLY UNRECOGNIZABLE NERVES OF GOOD COVERS ARE ALGORITHMICALLY UNRECOGNIZABLE
skos:notation
RIV/00216208:11320/13:10190000!RIV14-GA0-11320___
n7:predkladatel
n8:orjk%3A11320
n3:aktivita
n19:P
n3:aktivity
P(GBP202/12/G061)
n3:cisloPeriodika
4
n3:dodaniDat
n13:2014
n3:domaciTvurceVysledku
n5:5278880
n3:druhVysledku
n14:J
n3:duvernostUdaju
n21:S
n3:entitaPredkladatele
n15:predkladatel
n3:idSjednocenehoVysledku
91380
n3:idVysledku
RIV/00216208:11320/13:10190000
n3:jazykVysledku
n12:eng
n3:klicovaSlova
piecewise-linear embedding; nerve; intersection pattern; algorithmic undecidability; good cover
n3:klicoveSlovo
n17:nerve n17:intersection%20pattern n17:good%20cover n17:algorithmic%20undecidability n17:piecewise-linear%20embedding
n3:kodStatuVydavatele
US - Spojené státy americké
n3:kontrolniKodProRIV
[28C8BA0ADF2D]
n3:nazevZdroje
SIAM JOURNAL ON COMPUTING
n3:obor
n18:BA
n3:pocetDomacichTvurcuVysledku
1
n3:pocetTvurcuVysledku
2
n3:projekt
n6:GBP202%2F12%2FG061
n3:rokUplatneniVysledku
n13:2013
n3:svazekPeriodika
42
n3:tvurceVysledku
Tonkonog, Dmitry Tancer, Martin
n3:wos
000323889100011
s:issn
0097-5397
s:numberOfPages
23
n16:doi
10.1137/120891204
n20:organizacniJednotka
11320