Universal zero-one k-law View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2016-03

AUTHORS

M. E. Zhukovskii, A. D. Matushkin

ABSTRACT

The limit probabilities of first-order properties of a random graph in the Erdős–Rényi model G(n, n−α), α ∈ (0, 1), are studied. For any positive integer k ≥ 4 and any rational number t/s ∈ (0, 1), an interval with right endpoint t/s is found in which the zero-one k-law holds (the zero-one k-law describes the behavior of the probabilities of first-order properties expressed by formulas of quantifier depth at most k).Moreover, it is proved that, for rational numbers t/s with numerator not exceeding 2, the logarithm of the length of this interval is of the same order of smallness (as n→∞) as that of the length of the maximal interval with right endpoint t/s in which the zero-one k-law holds. More... »

PAGES

511-523

References to SciGraph publications

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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": "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": "Matushkin", 
        "givenName": "A. D.", 
        "id": "sg:person.015207162751.47", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015207162751.47"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/bf02122699", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004686170", 
          "https://doi.org/10.1007/bf02122699"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-662-04538-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1020409190", 
          "https://doi.org/10.1007/978-3-662-04538-1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1134/s1064562411010054", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1020949900", 
          "https://doi.org/10.1134/s1064562411010054"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2016-03", 
    "datePublishedReg": "2016-03-01", 
    "description": "The limit probabilities of 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. For any positive integer k \u2265 4 and any rational number t/s \u2208 (0, 1), an interval with right endpoint t/s is found in which the zero-one k-law holds (the zero-one k-law describes the behavior of the probabilities of first-order properties expressed by formulas of quantifier depth at most k).Moreover, it is proved that, for rational numbers t/s with numerator not exceeding 2, the logarithm of the length of this interval is of the same order of smallness (as n\u2192\u221e) as that of the length of the maximal interval with right endpoint t/s in which the zero-one k-law holds.", 
    "genre": "article", 
    "id": "sg:pub.10.1134/s000143461603024x", 
    "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", 
      "first-order properties", 
      "limit probability", 
      "law", 
      "maximal interval", 
      "order", 
      "random graphs", 
      "positive integer k", 
      "logarithm", 
      "properties", 
      "model", 
      "probability", 
      "integer k", 
      "numerator", 
      "zeros", 
      "smallness", 
      "length", 
      "graph", 
      "same order", 
      "intervals", 
      "rational number t/s", 
      "number t/s", 
      "t/s", 
      "right endpoint t/s", 
      "endpoint t/s", 
      "Universal zero"
    ], 
    "name": "Universal zero-one k-law", 
    "pagination": "511-523", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1032230770"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1134/s000143461603024x"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1134/s000143461603024x", 
      "https://app.dimensions.ai/details/publication/pub.1032230770"
    ], 
    "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_699.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1134/s000143461603024x"
  }
]
 

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/s000143461603024x'

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/s000143461603024x'

Turtle is a human-readable linked data format.

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

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

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


 

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

103 TRIPLES      22 PREDICATES      55 URIs      44 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1134/s000143461603024x schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N0831eaf4b8ad433a9332a0b5b3aa391d
4 schema:citation sg:pub.10.1007/978-3-662-04538-1
5 sg:pub.10.1007/bf02122699
6 sg:pub.10.1134/s1064562411010054
7 schema:datePublished 2016-03
8 schema:datePublishedReg 2016-03-01
9 schema:description The limit probabilities of first-order properties of a random graph in the Erdős–Rényi model G(n, n−α), α ∈ (0, 1), are studied. For any positive integer k ≥ 4 and any rational number t/s ∈ (0, 1), an interval with right endpoint t/s is found in which the zero-one k-law holds (the zero-one k-law describes the behavior of the probabilities of first-order properties expressed by formulas of quantifier depth at most k).Moreover, it is proved that, for rational numbers t/s with numerator not exceeding 2, the logarithm of the length of this interval is of the same order of smallness (as n→∞) as that of the length of the maximal interval with right endpoint t/s in which the zero-one k-law holds.
10 schema:genre article
11 schema:inLanguage en
12 schema:isAccessibleForFree false
13 schema:isPartOf Nbb33d6784b9a4ced9706112a42cb4d22
14 Ncb8354ec266f4337b1e8ef90051ced5c
15 sg:journal.1136530
16 schema:keywords Erdős–Rényi model
17 Universal zero
18 endpoint t/s
19 first-order properties
20 graph
21 integer k
22 intervals
23 law
24 length
25 limit probability
26 logarithm
27 maximal interval
28 model
29 number t/s
30 numerator
31 order
32 positive integer k
33 probability
34 properties
35 random graphs
36 rational number t/s
37 right endpoint t/s
38 same order
39 smallness
40 t/s
41 zeros
42 schema:name Universal zero-one k-law
43 schema:pagination 511-523
44 schema:productId N321929715b954a41a40fbda3e7c44565
45 N4757cbdd928e42a5a299049165f22010
46 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032230770
47 https://doi.org/10.1134/s000143461603024x
48 schema:sdDatePublished 2021-11-01T18:27
49 schema:sdLicense https://scigraph.springernature.com/explorer/license/
50 schema:sdPublisher N13b010b5b2e54d4d84ae93e29852def3
51 schema:url https://doi.org/10.1134/s000143461603024x
52 sgo:license sg:explorer/license/
53 sgo:sdDataset articles
54 rdf:type schema:ScholarlyArticle
55 N0831eaf4b8ad433a9332a0b5b3aa391d rdf:first sg:person.011152672013.96
56 rdf:rest N907063bb8abf4dda86189a9275633823
57 N13b010b5b2e54d4d84ae93e29852def3 schema:name Springer Nature - SN SciGraph project
58 rdf:type schema:Organization
59 N321929715b954a41a40fbda3e7c44565 schema:name dimensions_id
60 schema:value pub.1032230770
61 rdf:type schema:PropertyValue
62 N4757cbdd928e42a5a299049165f22010 schema:name doi
63 schema:value 10.1134/s000143461603024x
64 rdf:type schema:PropertyValue
65 N907063bb8abf4dda86189a9275633823 rdf:first sg:person.015207162751.47
66 rdf:rest rdf:nil
67 Nbb33d6784b9a4ced9706112a42cb4d22 schema:issueNumber 3-4
68 rdf:type schema:PublicationIssue
69 Ncb8354ec266f4337b1e8ef90051ced5c schema:volumeNumber 99
70 rdf:type schema:PublicationVolume
71 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
72 schema:name Mathematical Sciences
73 rdf:type schema:DefinedTerm
74 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
75 schema:name Pure Mathematics
76 rdf:type schema:DefinedTerm
77 sg:journal.1136530 schema:issn 1757-7489
78 2305-2880
79 schema:name Mathematical Notes
80 schema:publisher Pleiades Publishing
81 rdf:type schema:Periodical
82 sg:person.011152672013.96 schema:affiliation grid-institutes:grid.18763.3b
83 schema:familyName Zhukovskii
84 schema:givenName M. E.
85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011152672013.96
86 rdf:type schema:Person
87 sg:person.015207162751.47 schema:affiliation grid-institutes:grid.18763.3b
88 schema:familyName Matushkin
89 schema:givenName A. D.
90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015207162751.47
91 rdf:type schema:Person
92 sg:pub.10.1007/978-3-662-04538-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020409190
93 https://doi.org/10.1007/978-3-662-04538-1
94 rdf:type schema:CreativeWork
95 sg:pub.10.1007/bf02122699 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004686170
96 https://doi.org/10.1007/bf02122699
97 rdf:type schema:CreativeWork
98 sg:pub.10.1134/s1064562411010054 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020949900
99 https://doi.org/10.1134/s1064562411010054
100 rdf:type schema:CreativeWork
101 grid-institutes:grid.18763.3b schema:alternateName Moscow Institute of Physics and Technology, Dolgoprudnyi, Russia
102 schema:name Moscow Institute of Physics and Technology, Dolgoprudnyi, Russia
103 rdf:type schema:Organization
 




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


...