When does the zero-one k-law fail? View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2016-03

AUTHORS

M. E. Zhukovskii, A. E. Medvedeva

ABSTRACT

The limit probabilities of the first-order properties of a random graph in the Erdős–Rényi model G(n, n−α), α ∈ (0, 1), are studied. A random graph G(n, n−α) is said to obey the zero-one k-law if, given any property expressed by a formula of quantifier depth at most k, the probability of this property tends to either 0 or 1. As is known, for α = 1− 1/(2k−1 + a/b), where a > 2k−1, the zero-one k-law holds. Moreover, this law does not hold for b = 1 and a ≤ 2k−1 − 2. It is proved that the k-law also fails for b > 1 and a ≤ 2k−1 − (b + 1)2. More... »

PAGES

362-367

Identifiers

URI

http://scigraph.springernature.com/pub.10.1134/s0001434616030032

DOI

http://dx.doi.org/10.1134/s0001434616030032

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1001226749


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Moscow Institute of Physics and Technology, Dolgoprudnyi, Russia", 
          "id": "http://www.grid.ac/institutes/grid.18763.3b", 
          "name": [
            "Moscow Institute of Physics and Technology, Dolgoprudnyi, Russia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Zhukovskii", 
        "givenName": "M. E.", 
        "id": "sg:person.011152672013.96", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011152672013.96"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Derzhavin Tambov State University, Tambov, Russia", 
          "id": "http://www.grid.ac/institutes/grid.446191.f", 
          "name": [
            "Derzhavin Tambov State University, Tambov, Russia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Medvedeva", 
        "givenName": "A. E.", 
        "type": "Person"
      }
    ], 
    "datePublished": "2016-03", 
    "datePublishedReg": "2016-03-01", 
    "description": "The limit probabilities of the first-order properties of a random graph in the Erd\u0151s\u2013R\u00e9nyi model G(n, n\u2212\u03b1), \u03b1 \u2208 (0, 1), are studied. A random graph G(n, n\u2212\u03b1) is said to obey the zero-one k-law if, given any property expressed by a formula of quantifier depth at most k, the probability of this property tends to either 0 or 1. As is known, for \u03b1 = 1\u2212 1/(2k\u22121 + a/b), where a > 2k\u22121, the zero-one k-law holds. Moreover, this law does not hold for b = 1 and a \u2264 2k\u22121 \u2212 2. It is proved that the k-law also fails for b > 1 and a \u2264 2k\u22121 \u2212 (b + 1)2.", 
    "genre": "article", 
    "id": "sg:pub.10.1134/s0001434616030032", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1136530", 
        "issn": [
          "1757-7489", 
          "2305-2880"
        ], 
        "name": "Mathematical Notes", 
        "publisher": "Pleiades Publishing", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "3-4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "99"
      }
    ], 
    "keywords": [
      "Erd\u0151s\u2013R\u00e9nyi model", 
      "Law Fail", 
      "first-order properties", 
      "quantifier depth", 
      "limit probability", 
      "law", 
      "random graphs", 
      "fail", 
      "properties", 
      "probability", 
      "model", 
      "formula", 
      "depth", 
      "graph"
    ], 
    "name": "When does the zero-one k-law fail?", 
    "pagination": "362-367", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1001226749"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1134/s0001434616030032"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1134/s0001434616030032", 
      "https://app.dimensions.ai/details/publication/pub.1001226749"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2021-11-01T18:27", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/article/article_703.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1134/s0001434616030032"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1134/s0001434616030032'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1134/s0001434616030032'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1134/s0001434616030032'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1134/s0001434616030032'


 

This table displays all metadata directly associated to this object as RDF triples.

81 TRIPLES      21 PREDICATES      40 URIs      32 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1134/s0001434616030032 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N5c11dc225d2747499f87926b6fe022b7
4 schema:datePublished 2016-03
5 schema:datePublishedReg 2016-03-01
6 schema:description The limit probabilities of the first-order properties of a random graph in the Erdős–Rényi model G(n, n−α), α ∈ (0, 1), are studied. A random graph G(n, n−α) is said to obey the zero-one k-law if, given any property expressed by a formula of quantifier depth at most k, the probability of this property tends to either 0 or 1. As is known, for α = 1− 1/(2k−1 + a/b), where a > 2k−1, the zero-one k-law holds. Moreover, this law does not hold for b = 1 and a ≤ 2k−1 − 2. It is proved that the k-law also fails for b > 1 and a ≤ 2k−1 − (b + 1)2.
7 schema:genre article
8 schema:inLanguage en
9 schema:isAccessibleForFree false
10 schema:isPartOf Neffa6d2fa029448ab7baa2e34557f331
11 Nfe85da29f2674431be35b12c0c47157b
12 sg:journal.1136530
13 schema:keywords Erdős–Rényi model
14 Law Fail
15 depth
16 fail
17 first-order properties
18 formula
19 graph
20 law
21 limit probability
22 model
23 probability
24 properties
25 quantifier depth
26 random graphs
27 schema:name When does the zero-one k-law fail?
28 schema:pagination 362-367
29 schema:productId N7e55ffb338974b0d9c0e5c5c19a47a68
30 Nbe611b7136154b378316fe26f6dfd6c4
31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001226749
32 https://doi.org/10.1134/s0001434616030032
33 schema:sdDatePublished 2021-11-01T18:27
34 schema:sdLicense https://scigraph.springernature.com/explorer/license/
35 schema:sdPublisher Nac616573128b401d80d8eecff3f39708
36 schema:url https://doi.org/10.1134/s0001434616030032
37 sgo:license sg:explorer/license/
38 sgo:sdDataset articles
39 rdf:type schema:ScholarlyArticle
40 N058361b9f1a245d584c35d05ca79a5c5 schema:affiliation grid-institutes:grid.446191.f
41 schema:familyName Medvedeva
42 schema:givenName A. E.
43 rdf:type schema:Person
44 N5c11dc225d2747499f87926b6fe022b7 rdf:first sg:person.011152672013.96
45 rdf:rest Nadd468e56f854b9ca34eeb102ec099cf
46 N7e55ffb338974b0d9c0e5c5c19a47a68 schema:name dimensions_id
47 schema:value pub.1001226749
48 rdf:type schema:PropertyValue
49 Nac616573128b401d80d8eecff3f39708 schema:name Springer Nature - SN SciGraph project
50 rdf:type schema:Organization
51 Nadd468e56f854b9ca34eeb102ec099cf rdf:first N058361b9f1a245d584c35d05ca79a5c5
52 rdf:rest rdf:nil
53 Nbe611b7136154b378316fe26f6dfd6c4 schema:name doi
54 schema:value 10.1134/s0001434616030032
55 rdf:type schema:PropertyValue
56 Neffa6d2fa029448ab7baa2e34557f331 schema:issueNumber 3-4
57 rdf:type schema:PublicationIssue
58 Nfe85da29f2674431be35b12c0c47157b schema:volumeNumber 99
59 rdf:type schema:PublicationVolume
60 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
61 schema:name Mathematical Sciences
62 rdf:type schema:DefinedTerm
63 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
64 schema:name Pure Mathematics
65 rdf:type schema:DefinedTerm
66 sg:journal.1136530 schema:issn 1757-7489
67 2305-2880
68 schema:name Mathematical Notes
69 schema:publisher Pleiades Publishing
70 rdf:type schema:Periodical
71 sg:person.011152672013.96 schema:affiliation grid-institutes:grid.18763.3b
72 schema:familyName Zhukovskii
73 schema:givenName M. E.
74 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011152672013.96
75 rdf:type schema:Person
76 grid-institutes:grid.18763.3b schema:alternateName Moscow Institute of Physics and Technology, Dolgoprudnyi, Russia
77 schema:name Moscow Institute of Physics and Technology, Dolgoprudnyi, Russia
78 rdf:type schema:Organization
79 grid-institutes:grid.446191.f schema:alternateName Derzhavin Tambov State University, Tambov, Russia
80 schema:name Derzhavin Tambov State University, Tambov, Russia
81 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...