On the zero-one 4-law for the Erdős-Rényi random graphs View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2015-01

AUTHORS

M. E. Zhukovskii

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. Earlier, the author obtained zero-one k-laws for any positive integer k ≥ 3, which describe the behavior of the probabilities of the first-order properties expressed by formulas of quantifier depth bounded by k for α in the interval (0, 1/(k − 2)] and k ≥ 4 in the interval (1 − 1/2k−1, 1). This result is improved for k = 4. Moreover, it is proved that, for any k ≥ 4, the zero-one k-law does not hold at the lower boundary of the interval (1 − 1/2k−1, 1). More... »

PAGES

190-200

References to SciGraph publications

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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, State University, Dolgoprudnyi, Moscow oblast, Russia", 
          "id": "http://www.grid.ac/institutes/grid.18763.3b", 
          "name": [
            "Moscow Institute of Physics and Technology, State University, Dolgoprudnyi, Moscow oblast, 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"
      }
    ], 
    "citation": [
      {
        "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"
      }
    ], 
    "datePublished": "2015-01", 
    "datePublishedReg": "2015-01-01", 
    "description": "The limit probabilities of the first-order properties of a random graph in the Erd\u0151s-R\u00e9nyi model G(n, n\u03b1), \u03b1 \u2208 (0, 1], are studied. Earlier, the author obtained zero-one k-laws for any positive integer k \u2265 3, which describe the behavior of the probabilities of the first-order properties expressed by formulas of quantifier depth bounded by k for \u03b1 in the interval (0, 1/(k \u2212 2)] and k \u2265 4 in the interval (1 \u2212 1/2k\u22121, 1). This result is improved for k = 4. Moreover, it is proved that, for any k \u2265 4, the zero-one k-law does not hold at the lower boundary of the interval (1 \u2212 1/2k\u22121, 1).", 
    "genre": "article", 
    "id": "sg:pub.10.1134/s0001434615010216", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1136530", 
        "issn": [
          "1757-7489", 
          "2305-2880"
        ], 
        "name": "Mathematical Notes", 
        "publisher": "Pleiades Publishing", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1-2", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "97"
      }
    ], 
    "keywords": [
      "first-order properties", 
      "Erd\u0151s\u2013R\u00e9nyi model", 
      "quantifier depth", 
      "limit probability", 
      "law", 
      "Erd\u0151s\u2013R\u00e9nyi random graph", 
      "authors", 
      "random graphs", 
      "boundaries", 
      "positive integer k", 
      "properties", 
      "behavior", 
      "probability", 
      "model", 
      "formula", 
      "integer k", 
      "results", 
      "depth", 
      "lower boundary", 
      "graph", 
      "intervals"
    ], 
    "name": "On the zero-one 4-law for the Erd\u0151s-R\u00e9nyi random graphs", 
    "pagination": "190-200", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1010811818"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1134/s0001434615010216"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1134/s0001434615010216", 
      "https://app.dimensions.ai/details/publication/pub.1010811818"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2021-12-01T19:34", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/article/article_678.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1134/s0001434615010216"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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

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


 

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

83 TRIPLES      22 PREDICATES      48 URIs      39 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1134/s0001434615010216 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N94a3d3ad71854ab2b861f4bbd9e3f635
4 schema:citation sg:pub.10.1007/978-3-662-04538-1
5 schema:datePublished 2015-01
6 schema:datePublishedReg 2015-01-01
7 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. Earlier, the author obtained zero-one k-laws for any positive integer k ≥ 3, which describe the behavior of the probabilities of the first-order properties expressed by formulas of quantifier depth bounded by k for α in the interval (0, 1/(k − 2)] and k ≥ 4 in the interval (1 − 1/2k−1, 1). This result is improved for k = 4. Moreover, it is proved that, for any k ≥ 4, the zero-one k-law does not hold at the lower boundary of the interval (1 − 1/2k−1, 1).
8 schema:genre article
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N03622afd30904626abe1d430a65626dc
12 N170a49c1dea74b71bd1df336da76b0ab
13 sg:journal.1136530
14 schema:keywords Erdős–Rényi model
15 Erdős–Rényi random graph
16 authors
17 behavior
18 boundaries
19 depth
20 first-order properties
21 formula
22 graph
23 integer k
24 intervals
25 law
26 limit probability
27 lower boundary
28 model
29 positive integer k
30 probability
31 properties
32 quantifier depth
33 random graphs
34 results
35 schema:name On the zero-one 4-law for the Erdős-Rényi random graphs
36 schema:pagination 190-200
37 schema:productId Nc959644dff7b4a1fb16e23acc970aa31
38 Nf1b218410b764d569096537ea5ea134b
39 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010811818
40 https://doi.org/10.1134/s0001434615010216
41 schema:sdDatePublished 2021-12-01T19:34
42 schema:sdLicense https://scigraph.springernature.com/explorer/license/
43 schema:sdPublisher N7905156272ac4ca7b4fd5a24849b9787
44 schema:url https://doi.org/10.1134/s0001434615010216
45 sgo:license sg:explorer/license/
46 sgo:sdDataset articles
47 rdf:type schema:ScholarlyArticle
48 N03622afd30904626abe1d430a65626dc schema:volumeNumber 97
49 rdf:type schema:PublicationVolume
50 N170a49c1dea74b71bd1df336da76b0ab schema:issueNumber 1-2
51 rdf:type schema:PublicationIssue
52 N7905156272ac4ca7b4fd5a24849b9787 schema:name Springer Nature - SN SciGraph project
53 rdf:type schema:Organization
54 N94a3d3ad71854ab2b861f4bbd9e3f635 rdf:first sg:person.011152672013.96
55 rdf:rest rdf:nil
56 Nc959644dff7b4a1fb16e23acc970aa31 schema:name doi
57 schema:value 10.1134/s0001434615010216
58 rdf:type schema:PropertyValue
59 Nf1b218410b764d569096537ea5ea134b schema:name dimensions_id
60 schema:value pub.1010811818
61 rdf:type schema:PropertyValue
62 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
63 schema:name Mathematical Sciences
64 rdf:type schema:DefinedTerm
65 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
66 schema:name Pure Mathematics
67 rdf:type schema:DefinedTerm
68 sg:journal.1136530 schema:issn 1757-7489
69 2305-2880
70 schema:name Mathematical Notes
71 schema:publisher Pleiades Publishing
72 rdf:type schema:Periodical
73 sg:person.011152672013.96 schema:affiliation grid-institutes:grid.18763.3b
74 schema:familyName Zhukovskii
75 schema:givenName M. E.
76 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011152672013.96
77 rdf:type schema:Person
78 sg:pub.10.1007/978-3-662-04538-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020409190
79 https://doi.org/10.1007/978-3-662-04538-1
80 rdf:type schema:CreativeWork
81 grid-institutes:grid.18763.3b schema:alternateName Moscow Institute of Physics and Technology, State University, Dolgoprudnyi, Moscow oblast, Russia
82 schema:name Moscow Institute of Physics and Technology, State University, Dolgoprudnyi, Moscow oblast, Russia
83 rdf:type schema:Organization
 




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


...