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

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

Namespace Prefixes

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

Statements

Subject Item
n2:RIV%2F00216208%3A11320%2F13%3A10190365%21RIV14-GA0-11320___
rdf:type
skos:Concept n15:Vysledek
rdfs:seeAlso
http://link.springer.com/chapter/10.1007%2F978-88-7642-475-5_90
dcterms:description
An ultrahomogeneous structure is a (finite or countable) relational structure for which every partial isomorphism between finite substructures can be extended to a global isomorphism. This very strong symmetry condition implies that there are just a few ultrahomogeneous structures. For example, by [14], there are just countably many ultrahomogeneous undirected graphs. The classification program is one of the celebrated lines of research in the model theory, see [4, 15]. Various measures were introduced in order to modify a structure to an ultrahomogeneous one. A particularly interesting measure is the minimal arity of added relations (i.e. the minimal arity of an extension or lift) which suffice to produce an ultrahomogeneous structure. If these added relations are not changing the automorphism group then the problem is called the relational complexity and this is the subject of this paper. In the context of permutation groups, the relational complexity was defined in [5] and was recently popularized by Cherlin [2,3]. We determine the relational complexity of one of the most natural class of structures (the class of structures defined by forbidden homomorphisms). This class has a (countably) universal structure [6]. As a consequence of our main result (Theorem 3.1) we strengthen this by determining its relational complexity. Although formulated in the context of model theory this result has a combinatorial character. Full details will appear in [9] An ultrahomogeneous structure is a (finite or countable) relational structure for which every partial isomorphism between finite substructures can be extended to a global isomorphism. This very strong symmetry condition implies that there are just a few ultrahomogeneous structures. For example, by [14], there are just countably many ultrahomogeneous undirected graphs. The classification program is one of the celebrated lines of research in the model theory, see [4, 15]. Various measures were introduced in order to modify a structure to an ultrahomogeneous one. A particularly interesting measure is the minimal arity of added relations (i.e. the minimal arity of an extension or lift) which suffice to produce an ultrahomogeneous structure. If these added relations are not changing the automorphism group then the problem is called the relational complexity and this is the subject of this paper. In the context of permutation groups, the relational complexity was defined in [5] and was recently popularized by Cherlin [2,3]. We determine the relational complexity of one of the most natural class of structures (the class of structures defined by forbidden homomorphisms). This class has a (countably) universal structure [6]. As a consequence of our main result (Theorem 3.1) we strengthen this by determining its relational complexity. Although formulated in the context of model theory this result has a combinatorial character. Full details will appear in [9]
dcterms:title
Combinatorial bounds on relational complexity Combinatorial bounds on relational complexity
skos:prefLabel
Combinatorial bounds on relational complexity Combinatorial bounds on relational complexity
skos:notation
RIV/00216208:11320/13:10190365!RIV14-GA0-11320___
n15:predkladatel
n16:orjk%3A11320
n4:aktivita
n14:P
n4:aktivity
P(GBP202/12/G061), P(LL1201)
n4:dodaniDat
n12:2014
n4:domaciTvurceVysledku
n8:8653976 n8:1111116 n8:8072639
n4:druhVysledku
n5:D
n4:duvernostUdaju
n21:S
n4:entitaPredkladatele
n10:predkladatel
n4:idSjednocenehoVysledku
65964
n4:idVysledku
RIV/00216208:11320/13:10190365
n4:jazykVysledku
n24:eng
n4:klicovaSlova
automorphism; relational structure; homogeneous; graphs; relational complexity
n4:klicoveSlovo
n9:relational%20complexity n9:homogeneous n9:automorphism n9:graphs n9:relational%20structure
n4:kontrolniKodProRIV
[4D30067BA5C3]
n4:mistoKonaniAkce
Itálie
n4:mistoVydani
Itálie
n4:nazevZdroje
CRM Series
n4:obor
n11:BA
n4:pocetDomacichTvurcuVysledku
3
n4:pocetTvurcuVysledku
3
n4:projekt
n22:LL1201 n22:GBP202%2F12%2FG061
n4:rokUplatneniVysledku
n12:2013
n4:tvurceVysledku
Hubička, Jan Hartman, David Nešetřil, Jaroslav
n4:typAkce
n19:WRD
n4:zahajeniAkce
2013-09-09+02:00
s:numberOfPages
5
n6:doi
10.1007/978-88-7642-475-5_90
n18:hasPublisher
Scuola Normale Superiore
n13:isbn
978-88-7642-474-8
n17:organizacniJednotka
11320