Ramsey Numbers of Books and Quasirandomness View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2022-03-10

AUTHORS

David Conlon, Jacob Fox, Yuval Wigderson

ABSTRACT

The book graphBn(k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$B_n^{(k)}$$\end{document} consists of n copies of Kk+1 joined along a common Kk. The Ramsey numbers of Bn(k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$B_n^{(k)}$$\end{document} are known to have strong connections to the classical Ramsey numbers of cliques. Recently, the first author determined the asymptotic order of these Ramsey numbers for fixed k, thus answering an old question of Erdős, Faudree, Rousseau, and Schelp. In this paper, we first provide a simpler proof of this theorem. Next, answering a question of the first author, we present a different proof that avoids the use of Szemerédi’s regularity lemma, thus providing much tighter control on the error term. Finally, we prove a conjecture of Nikiforov, Rousseau, and Schelp by showing that all extremal colorings for this Ramsey problem are quasirandom. More... »

PAGES

1-55

References to SciGraph publications

  • 1999-02. Quick Approximation to Matrices and Applications in COMBINATORICA
  • 2012-08-25. Bounds for graph regularity and removal lemmas in GEOMETRIC AND FUNCTIONAL ANALYSIS
  • 1978-03. The size Ramsey number in PERIODICA MATHEMATICA HUNGARICA
  • 2002-02-21. The Regularity Lemma and Its Applications in Graph Theory in THEORETICAL ASPECTS OF COMPUTER SCIENCE
  • 1989-12. Quasi-random graphs in COMBINATORICA
  • 1972-03. On a Ramsey type theorem in PERIODICA MATHEMATICA HUNGARICA
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00493-021-4409-9

    DOI

    http://dx.doi.org/10.1007/s00493-021-4409-9

    DIMENSIONS

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


    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/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Department of Mathematics, California Institute of Technology, 91125, Pasadena, CA, USA", 
              "id": "http://www.grid.ac/institutes/grid.20861.3d", 
              "name": [
                "Department of Mathematics, California Institute of Technology, 91125, Pasadena, CA, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Conlon", 
            "givenName": "David", 
            "id": "sg:person.011012737335.45", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011012737335.45"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Mathematics, Stanford University, 94305, Stanford, CA, USA", 
              "id": "http://www.grid.ac/institutes/grid.168010.e", 
              "name": [
                "Department of Mathematics, Stanford University, 94305, Stanford, CA, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Fox", 
            "givenName": "Jacob", 
            "id": "sg:person.016621164705.35", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016621164705.35"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Mathematics, California Institute of Technology, 91125, Pasadena, CA, USA", 
              "id": "http://www.grid.ac/institutes/grid.20861.3d", 
              "name": [
                "Department of Mathematics, California Institute of Technology, 91125, Pasadena, CA, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Wigderson", 
            "givenName": "Yuval", 
            "id": "sg:person.016024142515.17", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016024142515.17"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bf02018669", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050773656", 
              "https://doi.org/10.1007/bf02018669"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s004930050052", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051678555", 
              "https://doi.org/10.1007/s004930050052"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-45878-6_3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035413384", 
              "https://doi.org/10.1007/3-540-45878-6_3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02018930", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017252364", 
              "https://doi.org/10.1007/bf02018930"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00039-012-0171-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026325040", 
              "https://doi.org/10.1007/s00039-012-0171-x"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02125347", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028946467", 
              "https://doi.org/10.1007/bf02125347"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2022-03-10", 
        "datePublishedReg": "2022-03-10", 
        "description": "The book graphBn(k)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$B_n^{(k)}$$\\end{document} consists of n copies of Kk+1 joined along a common Kk. The Ramsey numbers of Bn(k)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$B_n^{(k)}$$\\end{document} are known to have strong connections to the classical Ramsey numbers of cliques. Recently, the first author determined the asymptotic order of these Ramsey numbers for fixed k, thus answering an old question of Erd\u0151s, Faudree, Rousseau, and Schelp. In this paper, we first provide a simpler proof of this theorem. Next, answering a question of the first author, we present a different proof that avoids the use of Szemer\u00e9di\u2019s regularity lemma, thus providing much tighter control on the error term. Finally, we prove a conjecture of Nikiforov, Rousseau, and Schelp by showing that all extremal colorings for this Ramsey problem are quasirandom.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00493-021-4409-9", 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1136493", 
            "issn": [
              "0209-9683", 
              "1439-6912"
            ], 
            "name": "Combinatorica", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }
        ], 
        "keywords": [
          "Ramsey number", 
          "regularity lemma", 
          "Szemer\u00e9di's regularity lemma", 
          "classical Ramsey numbers", 
          "asymptotic order", 
          "n copies", 
          "simple proof", 
          "extremal coloring", 
          "Ramsey problem", 
          "different proof", 
          "error term", 
          "first author", 
          "book", 
          "Rousseau", 
          "Schelp", 
          "strong connection", 
          "old question", 
          "theorem", 
          "quasirandomness", 
          "proof", 
          "lemma", 
          "conjecture", 
          "cliques", 
          "authors", 
          "questions", 
          "Erd\u0151s", 
          "Faudree", 
          "Nikiforov", 
          "coloring", 
          "number", 
          "problem", 
          "KK", 
          "connection", 
          "terms", 
          "order", 
          "copies", 
          "use", 
          "control", 
          "paper", 
          "tight control"
        ], 
        "name": "Ramsey Numbers of Books and Quasirandomness", 
        "pagination": "1-55", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1146183546"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00493-021-4409-9"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00493-021-4409-9", 
          "https://app.dimensions.ai/details/publication/pub.1146183546"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-09-02T16:08", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20220902/entities/gbq_results/article/article_949.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00493-021-4409-9"
      }
    ]
     

    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.1007/s00493-021-4409-9'

    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.1007/s00493-021-4409-9'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00493-021-4409-9'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00493-021-4409-9'


     

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

    132 TRIPLES      21 PREDICATES      68 URIs      54 LITERALS      4 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00493-021-4409-9 schema:about anzsrc-for:01
    2 anzsrc-for:08
    3 schema:author N4bdecc85d437432a9c5e314783b3e574
    4 schema:citation sg:pub.10.1007/3-540-45878-6_3
    5 sg:pub.10.1007/bf02018669
    6 sg:pub.10.1007/bf02018930
    7 sg:pub.10.1007/bf02125347
    8 sg:pub.10.1007/s00039-012-0171-x
    9 sg:pub.10.1007/s004930050052
    10 schema:datePublished 2022-03-10
    11 schema:datePublishedReg 2022-03-10
    12 schema:description The book graphBn(k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$B_n^{(k)}$$\end{document} consists of n copies of Kk+1 joined along a common Kk. The Ramsey numbers of Bn(k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$B_n^{(k)}$$\end{document} are known to have strong connections to the classical Ramsey numbers of cliques. Recently, the first author determined the asymptotic order of these Ramsey numbers for fixed k, thus answering an old question of Erdős, Faudree, Rousseau, and Schelp. In this paper, we first provide a simpler proof of this theorem. Next, answering a question of the first author, we present a different proof that avoids the use of Szemerédi’s regularity lemma, thus providing much tighter control on the error term. Finally, we prove a conjecture of Nikiforov, Rousseau, and Schelp by showing that all extremal colorings for this Ramsey problem are quasirandom.
    13 schema:genre article
    14 schema:isAccessibleForFree true
    15 schema:isPartOf sg:journal.1136493
    16 schema:keywords Erdős
    17 Faudree
    18 KK
    19 Nikiforov
    20 Ramsey number
    21 Ramsey problem
    22 Rousseau
    23 Schelp
    24 Szemerédi's regularity lemma
    25 asymptotic order
    26 authors
    27 book
    28 classical Ramsey numbers
    29 cliques
    30 coloring
    31 conjecture
    32 connection
    33 control
    34 copies
    35 different proof
    36 error term
    37 extremal coloring
    38 first author
    39 lemma
    40 n copies
    41 number
    42 old question
    43 order
    44 paper
    45 problem
    46 proof
    47 quasirandomness
    48 questions
    49 regularity lemma
    50 simple proof
    51 strong connection
    52 terms
    53 theorem
    54 tight control
    55 use
    56 schema:name Ramsey Numbers of Books and Quasirandomness
    57 schema:pagination 1-55
    58 schema:productId N32907d7a1e514e6fab351f489681f97a
    59 N78dc0a1a85144e7b8c6a6e00c0e6ea27
    60 schema:sameAs https://app.dimensions.ai/details/publication/pub.1146183546
    61 https://doi.org/10.1007/s00493-021-4409-9
    62 schema:sdDatePublished 2022-09-02T16:08
    63 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    64 schema:sdPublisher N1330047e3562452f95312eb040801beb
    65 schema:url https://doi.org/10.1007/s00493-021-4409-9
    66 sgo:license sg:explorer/license/
    67 sgo:sdDataset articles
    68 rdf:type schema:ScholarlyArticle
    69 N1330047e3562452f95312eb040801beb schema:name Springer Nature - SN SciGraph project
    70 rdf:type schema:Organization
    71 N32907d7a1e514e6fab351f489681f97a schema:name doi
    72 schema:value 10.1007/s00493-021-4409-9
    73 rdf:type schema:PropertyValue
    74 N4bdecc85d437432a9c5e314783b3e574 rdf:first sg:person.011012737335.45
    75 rdf:rest Nb152f771cc8e430eb7e3bea7885e7801
    76 N78dc0a1a85144e7b8c6a6e00c0e6ea27 schema:name dimensions_id
    77 schema:value pub.1146183546
    78 rdf:type schema:PropertyValue
    79 N9fab4a716401476e894ca8e1d81e039d rdf:first sg:person.016024142515.17
    80 rdf:rest rdf:nil
    81 Nb152f771cc8e430eb7e3bea7885e7801 rdf:first sg:person.016621164705.35
    82 rdf:rest N9fab4a716401476e894ca8e1d81e039d
    83 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    84 schema:name Mathematical Sciences
    85 rdf:type schema:DefinedTerm
    86 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    87 schema:name Information and Computing Sciences
    88 rdf:type schema:DefinedTerm
    89 sg:journal.1136493 schema:issn 0209-9683
    90 1439-6912
    91 schema:name Combinatorica
    92 schema:publisher Springer Nature
    93 rdf:type schema:Periodical
    94 sg:person.011012737335.45 schema:affiliation grid-institutes:grid.20861.3d
    95 schema:familyName Conlon
    96 schema:givenName David
    97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011012737335.45
    98 rdf:type schema:Person
    99 sg:person.016024142515.17 schema:affiliation grid-institutes:grid.20861.3d
    100 schema:familyName Wigderson
    101 schema:givenName Yuval
    102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016024142515.17
    103 rdf:type schema:Person
    104 sg:person.016621164705.35 schema:affiliation grid-institutes:grid.168010.e
    105 schema:familyName Fox
    106 schema:givenName Jacob
    107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016621164705.35
    108 rdf:type schema:Person
    109 sg:pub.10.1007/3-540-45878-6_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035413384
    110 https://doi.org/10.1007/3-540-45878-6_3
    111 rdf:type schema:CreativeWork
    112 sg:pub.10.1007/bf02018669 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050773656
    113 https://doi.org/10.1007/bf02018669
    114 rdf:type schema:CreativeWork
    115 sg:pub.10.1007/bf02018930 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017252364
    116 https://doi.org/10.1007/bf02018930
    117 rdf:type schema:CreativeWork
    118 sg:pub.10.1007/bf02125347 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028946467
    119 https://doi.org/10.1007/bf02125347
    120 rdf:type schema:CreativeWork
    121 sg:pub.10.1007/s00039-012-0171-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1026325040
    122 https://doi.org/10.1007/s00039-012-0171-x
    123 rdf:type schema:CreativeWork
    124 sg:pub.10.1007/s004930050052 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051678555
    125 https://doi.org/10.1007/s004930050052
    126 rdf:type schema:CreativeWork
    127 grid-institutes:grid.168010.e schema:alternateName Department of Mathematics, Stanford University, 94305, Stanford, CA, USA
    128 schema:name Department of Mathematics, Stanford University, 94305, Stanford, CA, USA
    129 rdf:type schema:Organization
    130 grid-institutes:grid.20861.3d schema:alternateName Department of Mathematics, California Institute of Technology, 91125, Pasadena, CA, USA
    131 schema:name Department of Mathematics, California Institute of Technology, 91125, Pasadena, CA, USA
    132 rdf:type schema:Organization
     




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


    ...