About: NERVES OF GOOD COVERS ARE ALGORITHMICALLY UNRECOGNIZABLE

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: NERVES OF GOOD COVERS ARE ALGORITHMICALLY UNRECOGNIZABLE Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
rdfs:seeAlso	http://dx.doi.org/10.1137/120891204
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. (en)
Title	NERVES OF GOOD COVERS ARE ALGORITHMICALLY UNRECOGNIZABLE NERVES OF GOOD COVERS ARE ALGORITHMICALLY UNRECOGNIZABLE (en)
skos:prefLabel	NERVES OF GOOD COVERS ARE ALGORITHMICALLY UNRECOGNIZABLE NERVES OF GOOD COVERS ARE ALGORITHMICALLY UNRECOGNIZABLE (en)
skos:notation	RIV/00216208:11320/13:10190000!RIV14-GA0-11320___
http://linked.open...avai/riv/aktivita	P
http://linked.open...avai/riv/aktivity	P(GBP202/12/G061)
http://linked.open...iv/cisloPeriodika	4
http://linked.open...vai/riv/dodaniDat	2014
http://linked.open...aciTvurceVysledku	Tancer, Martin
http://linked.open.../riv/druhVysledku	J - Článek v odborném periodiku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Univerzita Karlova v Praze / Matematicko-fyzikální fakulta
http://linked.open...dnocenehoVysledku	91380
http://linked.open...ai/riv/idVysledku	RIV/00216208:11320/13:10190000
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	piecewise-linear embedding; nerve; intersection pattern; algorithmic undecidability; good cover (en)
http://linked.open.../riv/klicoveSlovo	algorithmic undecidability good cover intersection pattern piecewise-linear embedding nerve
http://linked.open...odStatuVydavatele	US - Spojené státy americké
http://linked.open...ontrolniKodProRIV	[28C8BA0ADF2D]
http://linked.open...i/riv/nazevZdroje	SIAM JOURNAL ON COMPUTING
http://linked.open...in/vavai/riv/obor	BA
http://linked.open...ichTvurcuVysledku	1 (xsd:int)
http://linked.open...cetTvurcuVysledku	2 (xsd:int)
http://linked.open...vavai/riv/projekt	Center of excellence - Institute for theoretical computer science (CE-ITI)
http://linked.open...UplatneniVysledku	2013
http://linked.open...v/svazekPeriodika	42
http://linked.open...iv/tvurceVysledku	Tancer, Martin Tonkonog, Dmitry
http://linked.open...ain/vavai/riv/wos	000323889100011
issn	0097-5397
number of pages	23 (xsd:int)
http://bibframe.org/vocab/doi	10.1137/120891204
http://localhost/t...ganizacniJednotka	11320

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 47 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software