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/1801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Law", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/18", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Law and Legal Studies", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Moscow Institute of Physics and Technology", 
          "id": "https://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": "Tambov State University", 
          "id": "https://www.grid.ac/institutes/grid.446191.f", 
          "name": [
            "Derzhavin Tambov State University, Tambov, Russia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Medvedeva", 
        "givenName": "A. E.", 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/j.disc.2012.01.018", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1034255554"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1090/s0894-0347-1988-0924703-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1042008904"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1017/s0305004100058655", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1054065143"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.2307/2272945", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1069855996"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.4213/rm9626", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1072371229"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.4213/sm8368", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1072372885"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "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": "research_article", 
    "id": "sg:pub.10.1134/s0001434616030032", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1136530", 
        "issn": [
          "1757-7489", 
          "1573-8876"
        ], 
        "name": "Mathematical Notes", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "3-4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "99"
      }
    ], 
    "name": "When does the zero-one k-law fail?", 
    "pagination": "362-367", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "05d7f4b834d0e469c6adc3b7789f42038d95e6b69e3fa0c2b3a4ac6a1c3d1bce"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1134/s0001434616030032"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1001226749"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1134/s0001434616030032", 
      "https://app.dimensions.ai/details/publication/pub.1001226749"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-10T17:28", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8672_00000498.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/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.

88 TRIPLES      21 PREDICATES      33 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1134/s0001434616030032 schema:about anzsrc-for:18
2 anzsrc-for:1801
3 schema:author N5d600bf384b14d7fbfa1daf088b25b32
4 schema:citation https://doi.org/10.1016/j.disc.2012.01.018
5 https://doi.org/10.1017/s0305004100058655
6 https://doi.org/10.1090/s0894-0347-1988-0924703-8
7 https://doi.org/10.2307/2272945
8 https://doi.org/10.4213/rm9626
9 https://doi.org/10.4213/sm8368
10 schema:datePublished 2016-03
11 schema:datePublishedReg 2016-03-01
12 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.
13 schema:genre research_article
14 schema:inLanguage en
15 schema:isAccessibleForFree false
16 schema:isPartOf N2743dcaf3ab947f9b356002a859b9413
17 N9a7068d460ab4ba5a96179c9ff8437d3
18 sg:journal.1136530
19 schema:name When does the zero-one k-law fail?
20 schema:pagination 362-367
21 schema:productId N313f2df38b7944a4a8a073bfd8c1331f
22 N5d7dc7b2fc5a4eceb0e1782efc9a8434
23 Ne7c26c2ad7c44709a5076d1f28f2f8a1
24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001226749
25 https://doi.org/10.1134/s0001434616030032
26 schema:sdDatePublished 2019-04-10T17:28
27 schema:sdLicense https://scigraph.springernature.com/explorer/license/
28 schema:sdPublisher Nb5d0d9df094f4607ad80b28941fedb6e
29 schema:url http://link.springer.com/10.1134/S0001434616030032
30 sgo:license sg:explorer/license/
31 sgo:sdDataset articles
32 rdf:type schema:ScholarlyArticle
33 N2743dcaf3ab947f9b356002a859b9413 schema:issueNumber 3-4
34 rdf:type schema:PublicationIssue
35 N313f2df38b7944a4a8a073bfd8c1331f schema:name readcube_id
36 schema:value 05d7f4b834d0e469c6adc3b7789f42038d95e6b69e3fa0c2b3a4ac6a1c3d1bce
37 rdf:type schema:PropertyValue
38 N5d600bf384b14d7fbfa1daf088b25b32 rdf:first sg:person.011152672013.96
39 rdf:rest N768f365079c5455ea14e1dca23ad9450
40 N5d7dc7b2fc5a4eceb0e1782efc9a8434 schema:name dimensions_id
41 schema:value pub.1001226749
42 rdf:type schema:PropertyValue
43 N75c64f512c7a4110af7d2f23d07c52b2 schema:affiliation https://www.grid.ac/institutes/grid.446191.f
44 schema:familyName Medvedeva
45 schema:givenName A. E.
46 rdf:type schema:Person
47 N768f365079c5455ea14e1dca23ad9450 rdf:first N75c64f512c7a4110af7d2f23d07c52b2
48 rdf:rest rdf:nil
49 N9a7068d460ab4ba5a96179c9ff8437d3 schema:volumeNumber 99
50 rdf:type schema:PublicationVolume
51 Nb5d0d9df094f4607ad80b28941fedb6e schema:name Springer Nature - SN SciGraph project
52 rdf:type schema:Organization
53 Ne7c26c2ad7c44709a5076d1f28f2f8a1 schema:name doi
54 schema:value 10.1134/s0001434616030032
55 rdf:type schema:PropertyValue
56 anzsrc-for:18 schema:inDefinedTermSet anzsrc-for:
57 schema:name Law and Legal Studies
58 rdf:type schema:DefinedTerm
59 anzsrc-for:1801 schema:inDefinedTermSet anzsrc-for:
60 schema:name Law
61 rdf:type schema:DefinedTerm
62 sg:journal.1136530 schema:issn 1573-8876
63 1757-7489
64 schema:name Mathematical Notes
65 rdf:type schema:Periodical
66 sg:person.011152672013.96 schema:affiliation https://www.grid.ac/institutes/grid.18763.3b
67 schema:familyName Zhukovskii
68 schema:givenName M. E.
69 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011152672013.96
70 rdf:type schema:Person
71 https://doi.org/10.1016/j.disc.2012.01.018 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034255554
72 rdf:type schema:CreativeWork
73 https://doi.org/10.1017/s0305004100058655 schema:sameAs https://app.dimensions.ai/details/publication/pub.1054065143
74 rdf:type schema:CreativeWork
75 https://doi.org/10.1090/s0894-0347-1988-0924703-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042008904
76 rdf:type schema:CreativeWork
77 https://doi.org/10.2307/2272945 schema:sameAs https://app.dimensions.ai/details/publication/pub.1069855996
78 rdf:type schema:CreativeWork
79 https://doi.org/10.4213/rm9626 schema:sameAs https://app.dimensions.ai/details/publication/pub.1072371229
80 rdf:type schema:CreativeWork
81 https://doi.org/10.4213/sm8368 schema:sameAs https://app.dimensions.ai/details/publication/pub.1072372885
82 rdf:type schema:CreativeWork
83 https://www.grid.ac/institutes/grid.18763.3b schema:alternateName Moscow Institute of Physics and Technology
84 schema:name Moscow Institute of Physics and Technology, Dolgoprudnyi, Russia
85 rdf:type schema:Organization
86 https://www.grid.ac/institutes/grid.446191.f schema:alternateName Tambov State University
87 schema:name Derzhavin Tambov State University, Tambov, Russia
88 rdf:type schema:Organization
 




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


...