Non-Bipartite K-Common Graphs View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2022-02-18

AUTHORS

Daniel Král’, Jonathan A. Noel, Sergey Norin, Jan Volec, Fan Wei

ABSTRACT

A graph H is k-common if the number of monochromatic copies of H in a k-edge-coloring of Kn is asymptotically minimized by a random coloring. For every k, we construct a connected non-bipartite k-common graph. This resolves a problem raised by Jagger, Štovíček and Thomason [20]. We also show that a graph H is k-common for every k if and only if H is Sidorenko and that H is locally k-common for every k if and only if H is locally Sidorenko. More... »

PAGES

87-114

References to SciGraph publications

  • 1999-02. Quick Approximation to Matrices and Applications in COMBINATORICA
  • 2002-07. On Erdős's Conjecture on Multiplicities of Complete Subgraphs Lower Upper Bound for Cliques of Size 6 in COMBINATORICA
  • 2010-01. Graph norms and Sidorenko’s conjecture in ISRAEL JOURNAL OF MATHEMATICS
  • 1996-03. Multiplicities of subgraphs in COMBINATORICA
  • 1993-06. A correlation inequality for bipartite graphs in GRAPHS AND COMBINATORICS
  • 2010-10-20. An Approximate Version of Sidorenko’s Conjecture in GEOMETRIC AND FUNCTIONAL ANALYSIS
  • 1997-03. Graph products and monochromatic multiplicities in COMBINATORICA
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00493-020-4499-9

    DOI

    http://dx.doi.org/10.1007/s00493-020-4499-9

    DIMENSIONS

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


    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": "Mathematics Institute DIMAP and Department of Computer Science, University of Warwick, CV4 7AL, Coventry, UK", 
              "id": "http://www.grid.ac/institutes/grid.7372.1", 
              "name": [
                "Faculty of Informatics, Masaryk University, Botanick\u00e1 68A, 602 00, Brno, Czech Republic", 
                "Mathematics Institute DIMAP and Department of Computer Science, University of Warwick, CV4 7AL, Coventry, UK"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Kr\u00e1l\u2019", 
            "givenName": "Daniel", 
            "id": "sg:person.012161533423.79", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012161533423.79"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Mathematics Institute and DIMAP, University of Warwick, CV4 7AL, Coventry, UK", 
              "id": "http://www.grid.ac/institutes/grid.7372.1", 
              "name": [
                "Department of Mathematics and Statistics, University of Victoria, David Turpin Building A425 3800 Finnerty Road, V8P 5C2, Victoria, Canada", 
                "Mathematics Institute and DIMAP, University of Warwick, CV4 7AL, Coventry, UK"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Noel", 
            "givenName": "Jonathan A.", 
            "id": "sg:person.01304547762.08", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01304547762.08"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Mathematics and Statistics, McGill University, Montreal, Canada", 
              "id": "http://www.grid.ac/institutes/grid.14709.3b", 
              "name": [
                "Department of Mathematics and Statistics, McGill University, Montreal, Canada"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Norin", 
            "givenName": "Sergey", 
            "id": "sg:person.011531161016.65", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011531161016.65"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Faculty of Informatics, Masaryk University, Botanick\u00e1 68A, 602 00, Brno, Czech Republic", 
              "id": "http://www.grid.ac/institutes/grid.10267.32", 
              "name": [
                "Department of Mathematics Faculty of Nuclear Sciences and Physical Engineering, Czech Technical University in Prague, Trojanova 13, 120 00, Prague, Czech Republic", 
                "Faculty of Informatics, Masaryk University, Botanick\u00e1 68A, 602 00, Brno, Czech Republic"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Volec", 
            "givenName": "Jan", 
            "id": "sg:person.010123063515.69", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010123063515.69"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "School of Mathematics, Institute for Advanced Study, Princeton, USA", 
              "id": "http://www.grid.ac/institutes/grid.78989.37", 
              "name": [
                "Department of Mathematics, Princeton University, Princeton, NJ, USA", 
                "School of Mathematics, Institute for Advanced Study, Princeton, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Wei", 
            "givenName": "Fan", 
            "id": "sg:person.014130271043.94", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014130271043.94"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/s00039-010-0097-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044742778", 
              "https://doi.org/10.1007/s00039-010-0097-0"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02988307", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035009926", 
              "https://doi.org/10.1007/bf02988307"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s11856-010-0005-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035779884", 
              "https://doi.org/10.1007/s11856-010-0005-1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01196136", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005322044", 
              "https://doi.org/10.1007/bf01196136"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01300130", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048655559", 
              "https://doi.org/10.1007/bf01300130"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s004930200024", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046329522", 
              "https://doi.org/10.1007/s004930200024"
            ], 
            "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"
          }
        ], 
        "datePublished": "2022-02-18", 
        "datePublishedReg": "2022-02-18", 
        "description": "A graph H is k-common if the number of monochromatic copies of H in a k-edge-coloring of Kn is asymptotically minimized by a random coloring. For every k, we construct a connected non-bipartite k-common graph. This resolves a problem raised by Jagger, \u0160tov\u00ed\u010dek and Thomason [20]. We also show that a graph H is k-common for every k if and only if H is Sidorenko and that H is locally k-common for every k if and only if H is locally Sidorenko.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00493-020-4499-9", 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1136493", 
            "issn": [
              "0209-9683", 
              "1439-6912"
            ], 
            "name": "Combinatorica", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "42"
          }
        ], 
        "keywords": [
          "graph H", 
          "random coloring", 
          "monochromatic copy", 
          "common graph", 
          "graph", 
          "Sidorenko", 
          "coloring", 
          "problem", 
          "Thomason", 
          "Kn", 
          "number", 
          "copies", 
          "Jagger"
        ], 
        "name": "Non-Bipartite K-Common Graphs", 
        "pagination": "87-114", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1145698744"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00493-020-4499-9"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00493-020-4499-9", 
          "https://app.dimensions.ai/details/publication/pub.1145698744"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-11-24T21:09", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20221124/entities/gbq_results/article/article_955.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00493-020-4499-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-020-4499-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-020-4499-9'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00493-020-4499-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-020-4499-9'


     

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

    141 TRIPLES      21 PREDICATES      44 URIs      29 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00493-020-4499-9 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author Nbd270054f5b04b51a78046515572eb00
    4 schema:citation sg:pub.10.1007/bf01196136
    5 sg:pub.10.1007/bf01300130
    6 sg:pub.10.1007/bf02988307
    7 sg:pub.10.1007/s00039-010-0097-0
    8 sg:pub.10.1007/s004930050052
    9 sg:pub.10.1007/s004930200024
    10 sg:pub.10.1007/s11856-010-0005-1
    11 schema:datePublished 2022-02-18
    12 schema:datePublishedReg 2022-02-18
    13 schema:description A graph H is k-common if the number of monochromatic copies of H in a k-edge-coloring of Kn is asymptotically minimized by a random coloring. For every k, we construct a connected non-bipartite k-common graph. This resolves a problem raised by Jagger, Štovíček and Thomason [20]. We also show that a graph H is k-common for every k if and only if H is Sidorenko and that H is locally k-common for every k if and only if H is locally Sidorenko.
    14 schema:genre article
    15 schema:isAccessibleForFree true
    16 schema:isPartOf N06082f1c13b74a3aa8e0e796a4861895
    17 Nf7704c28179d4b5d9d1d9dd5589db445
    18 sg:journal.1136493
    19 schema:keywords Jagger
    20 Kn
    21 Sidorenko
    22 Thomason
    23 coloring
    24 common graph
    25 copies
    26 graph
    27 graph H
    28 monochromatic copy
    29 number
    30 problem
    31 random coloring
    32 schema:name Non-Bipartite K-Common Graphs
    33 schema:pagination 87-114
    34 schema:productId Ne5f288b4da4346cea55fdcd3417bca1b
    35 Nff001228e111489d8c16009a4cbbec49
    36 schema:sameAs https://app.dimensions.ai/details/publication/pub.1145698744
    37 https://doi.org/10.1007/s00493-020-4499-9
    38 schema:sdDatePublished 2022-11-24T21:09
    39 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    40 schema:sdPublisher Nbc6163790e934689999abb4fff6a9899
    41 schema:url https://doi.org/10.1007/s00493-020-4499-9
    42 sgo:license sg:explorer/license/
    43 sgo:sdDataset articles
    44 rdf:type schema:ScholarlyArticle
    45 N06082f1c13b74a3aa8e0e796a4861895 schema:issueNumber 1
    46 rdf:type schema:PublicationIssue
    47 N173c71a5a1dd4c868ee3a7662d113d04 rdf:first sg:person.01304547762.08
    48 rdf:rest Nbb4d48d33d264c32adebabc12a4974f4
    49 N300cf22f2b0f4654934abf01e06d783f rdf:first sg:person.010123063515.69
    50 rdf:rest Ndd1eea32e5254943a2974cf052e34095
    51 Nbb4d48d33d264c32adebabc12a4974f4 rdf:first sg:person.011531161016.65
    52 rdf:rest N300cf22f2b0f4654934abf01e06d783f
    53 Nbc6163790e934689999abb4fff6a9899 schema:name Springer Nature - SN SciGraph project
    54 rdf:type schema:Organization
    55 Nbd270054f5b04b51a78046515572eb00 rdf:first sg:person.012161533423.79
    56 rdf:rest N173c71a5a1dd4c868ee3a7662d113d04
    57 Ndd1eea32e5254943a2974cf052e34095 rdf:first sg:person.014130271043.94
    58 rdf:rest rdf:nil
    59 Ne5f288b4da4346cea55fdcd3417bca1b schema:name doi
    60 schema:value 10.1007/s00493-020-4499-9
    61 rdf:type schema:PropertyValue
    62 Nf7704c28179d4b5d9d1d9dd5589db445 schema:volumeNumber 42
    63 rdf:type schema:PublicationVolume
    64 Nff001228e111489d8c16009a4cbbec49 schema:name dimensions_id
    65 schema:value pub.1145698744
    66 rdf:type schema:PropertyValue
    67 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    68 schema:name Mathematical Sciences
    69 rdf:type schema:DefinedTerm
    70 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    71 schema:name Pure Mathematics
    72 rdf:type schema:DefinedTerm
    73 sg:journal.1136493 schema:issn 0209-9683
    74 1439-6912
    75 schema:name Combinatorica
    76 schema:publisher Springer Nature
    77 rdf:type schema:Periodical
    78 sg:person.010123063515.69 schema:affiliation grid-institutes:grid.10267.32
    79 schema:familyName Volec
    80 schema:givenName Jan
    81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010123063515.69
    82 rdf:type schema:Person
    83 sg:person.011531161016.65 schema:affiliation grid-institutes:grid.14709.3b
    84 schema:familyName Norin
    85 schema:givenName Sergey
    86 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011531161016.65
    87 rdf:type schema:Person
    88 sg:person.012161533423.79 schema:affiliation grid-institutes:grid.7372.1
    89 schema:familyName Král’
    90 schema:givenName Daniel
    91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012161533423.79
    92 rdf:type schema:Person
    93 sg:person.01304547762.08 schema:affiliation grid-institutes:grid.7372.1
    94 schema:familyName Noel
    95 schema:givenName Jonathan A.
    96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01304547762.08
    97 rdf:type schema:Person
    98 sg:person.014130271043.94 schema:affiliation grid-institutes:grid.78989.37
    99 schema:familyName Wei
    100 schema:givenName Fan
    101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014130271043.94
    102 rdf:type schema:Person
    103 sg:pub.10.1007/bf01196136 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005322044
    104 https://doi.org/10.1007/bf01196136
    105 rdf:type schema:CreativeWork
    106 sg:pub.10.1007/bf01300130 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048655559
    107 https://doi.org/10.1007/bf01300130
    108 rdf:type schema:CreativeWork
    109 sg:pub.10.1007/bf02988307 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035009926
    110 https://doi.org/10.1007/bf02988307
    111 rdf:type schema:CreativeWork
    112 sg:pub.10.1007/s00039-010-0097-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044742778
    113 https://doi.org/10.1007/s00039-010-0097-0
    114 rdf:type schema:CreativeWork
    115 sg:pub.10.1007/s004930050052 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051678555
    116 https://doi.org/10.1007/s004930050052
    117 rdf:type schema:CreativeWork
    118 sg:pub.10.1007/s004930200024 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046329522
    119 https://doi.org/10.1007/s004930200024
    120 rdf:type schema:CreativeWork
    121 sg:pub.10.1007/s11856-010-0005-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035779884
    122 https://doi.org/10.1007/s11856-010-0005-1
    123 rdf:type schema:CreativeWork
    124 grid-institutes:grid.10267.32 schema:alternateName Faculty of Informatics, Masaryk University, Botanická 68A, 602 00, Brno, Czech Republic
    125 schema:name Department of Mathematics Faculty of Nuclear Sciences and Physical Engineering, Czech Technical University in Prague, Trojanova 13, 120 00, Prague, Czech Republic
    126 Faculty of Informatics, Masaryk University, Botanická 68A, 602 00, Brno, Czech Republic
    127 rdf:type schema:Organization
    128 grid-institutes:grid.14709.3b schema:alternateName Department of Mathematics and Statistics, McGill University, Montreal, Canada
    129 schema:name Department of Mathematics and Statistics, McGill University, Montreal, Canada
    130 rdf:type schema:Organization
    131 grid-institutes:grid.7372.1 schema:alternateName Mathematics Institute DIMAP and Department of Computer Science, University of Warwick, CV4 7AL, Coventry, UK
    132 Mathematics Institute and DIMAP, University of Warwick, CV4 7AL, Coventry, UK
    133 schema:name Department of Mathematics and Statistics, University of Victoria, David Turpin Building A425 3800 Finnerty Road, V8P 5C2, Victoria, Canada
    134 Faculty of Informatics, Masaryk University, Botanická 68A, 602 00, Brno, Czech Republic
    135 Mathematics Institute DIMAP and Department of Computer Science, University of Warwick, CV4 7AL, Coventry, UK
    136 Mathematics Institute and DIMAP, University of Warwick, CV4 7AL, Coventry, UK
    137 rdf:type schema:Organization
    138 grid-institutes:grid.78989.37 schema:alternateName School of Mathematics, Institute for Advanced Study, Princeton, USA
    139 schema:name Department of Mathematics, Princeton University, Princeton, NJ, USA
    140 School of Mathematics, Institute for Advanced Study, Princeton, USA
    141 rdf:type schema:Organization
     




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


    ...