A Short Proof of the Blow-Up Lemma for Approximate Decompositions View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2022-05-19

AUTHORS

Stefan Ehard, Felix Joos

ABSTRACT

Kim, Kühn, Osthus and Tyomkyn (Trans. Amer. Math. Soc. 371 (2019), 4655–4742) greatly extended the well-known blow-up lemma of Komlós, Sárközy and Szemerédi by proving a ‘blow-up lemma for approximate decompositions’ which states that multipartite quasirandom graphs can be almost decomposed into any collection of bounded degree graphs with the same multipartite structure and slightly fewer edges. This result has already been used by Joos, Kim, Kühn and Osthus to prove the tree packing conjecture due to Gyárfás and Lehel from 1976 and Ringel’s conjecture from 1963 for bounded degree trees as well as implicitly in the recent resolution of the Oberwolfach problem (asked by Ringel in 1967) by Glock, Joos, Kim, Kühn and Osthus.Here we present a new and significantly shorter proof of the blow-up lemma for approximate decompositions. In fact, we prove a more general theorem that yields packings with stronger quasirandom properties which is useful for potential applications. More... »

PAGES

1-49

References to SciGraph publications

  • 2017-04. Packing spanning graphs from separable families in ISRAEL JOURNAL OF MATHEMATICS
  • 1997-03. Blow-up Lemma in COMBINATORICA
  • 1999-03. Perfect Matchings in ε-Regular Graphs and the Blow-Up Lemma in COMBINATORICA
  • 2016-01-05. An approximate version of the tree packing conjecture in ISRAEL JOURNAL OF MATHEMATICS
  • 2021-06. A proof of Ringel’s conjecture in GEOMETRIC AND FUNCTIONAL ANALYSIS
  • Identifiers

    URI

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

    DOI

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

    DIMENSIONS

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


    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/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Institut f\u00fcr Optimierung und Operations Research, Universit\u00e4t Ulm, Ulm, Germany", 
              "id": "http://www.grid.ac/institutes/grid.6582.9", 
              "name": [
                "Institut f\u00fcr Optimierung und Operations Research, Universit\u00e4t Ulm, Ulm, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Ehard", 
            "givenName": "Stefan", 
            "id": "sg:person.015003522537.44", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015003522537.44"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Institut f\u00fcr Informatik, Universit\u00e4t Heidelberg, Heidelberg, Germany", 
              "id": "http://www.grid.ac/institutes/grid.7700.0", 
              "name": [
                "Institut f\u00fcr Informatik, Universit\u00e4t Heidelberg, Heidelberg, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Joos", 
            "givenName": "Felix", 
            "id": "sg:person.012010701657.64", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012010701657.64"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/s11856-015-1277-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032447673", 
              "https://doi.org/10.1007/s11856-015-1277-2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00039-021-00576-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1140864762", 
              "https://doi.org/10.1007/s00039-021-00576-2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01196135", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045706665", 
              "https://doi.org/10.1007/bf01196135"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s11856-017-1504-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1085394553", 
              "https://doi.org/10.1007/s11856-017-1504-0"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s004930050063", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031275435", 
              "https://doi.org/10.1007/s004930050063"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2022-05-19", 
        "datePublishedReg": "2022-05-19", 
        "description": "Kim, K\u00fchn, Osthus and Tyomkyn (Trans. Amer. Math. Soc. 371 (2019), 4655\u20134742) greatly extended the well-known blow-up lemma of Koml\u00f3s, S\u00e1rk\u00f6zy and Szemer\u00e9di by proving a \u2018blow-up lemma for approximate decompositions\u2019 which states that multipartite quasirandom graphs can be almost decomposed into any collection of bounded degree graphs with the same multipartite structure and slightly fewer edges. This result has already been used by Joos, Kim, K\u00fchn and Osthus to prove the tree packing conjecture due to Gy\u00e1rf\u00e1s and Lehel from 1976 and Ringel\u2019s conjecture from 1963 for bounded degree trees as well as implicitly in the recent resolution of the Oberwolfach problem (asked by Ringel in 1967) by Glock, Joos, Kim, K\u00fchn and Osthus.Here we present a new and significantly shorter proof of the blow-up lemma for approximate decompositions. In fact, we prove a more general theorem that yields packings with stronger quasirandom properties which is useful for potential applications.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00493-020-4640-9", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1136493", 
            "issn": [
              "0209-9683", 
              "1439-6912"
            ], 
            "name": "Combinatorica", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }
        ], 
        "keywords": [
          "approximate decomposition", 
          "short proof", 
          "quasirandom graphs", 
          "general theorem", 
          "degree graphs", 
          "quasirandom properties", 
          "lemma", 
          "conjecture", 
          "Tree Packing Conjecture", 
          "graph", 
          "Osthus", 
          "theorem", 
          "Tyomkyn", 
          "Lehel", 
          "proof", 
          "Koml\u00f3s", 
          "Szemer\u00e9di", 
          "decomposition", 
          "blow", 
          "S\u00e1rk\u00f6zy", 
          "Gy\u00e1rf\u00e1s", 
          "degree trees", 
          "Kim", 
          "recent resolution", 
          "problem", 
          "Oberwolfach problem", 
          "Bounded Degree Trees", 
          "potential applications", 
          "multipartite structure", 
          "edge", 
          "properties", 
          "applications", 
          "structure", 
          "Joos", 
          "K\u00fchn", 
          "resolution", 
          "fact", 
          "results", 
          "trees", 
          "packing", 
          "collection", 
          "Glock"
        ], 
        "name": "A Short Proof of the Blow-Up Lemma for Approximate Decompositions", 
        "pagination": "1-49", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1147999038"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00493-020-4640-9"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00493-020-4640-9", 
          "https://app.dimensions.ai/details/publication/pub.1147999038"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-10-01T06:49", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/article/article_924.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00493-020-4640-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-4640-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-4640-9'

    Turtle is a human-readable linked data format.

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


     

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

    123 TRIPLES      21 PREDICATES      69 URIs      56 LITERALS      4 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00493-020-4640-9 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author Nbfc3decab1bf4695b28bd0efaa034ef3
    4 schema:citation sg:pub.10.1007/bf01196135
    5 sg:pub.10.1007/s00039-021-00576-2
    6 sg:pub.10.1007/s004930050063
    7 sg:pub.10.1007/s11856-015-1277-2
    8 sg:pub.10.1007/s11856-017-1504-0
    9 schema:datePublished 2022-05-19
    10 schema:datePublishedReg 2022-05-19
    11 schema:description Kim, Kühn, Osthus and Tyomkyn (Trans. Amer. Math. Soc. 371 (2019), 4655–4742) greatly extended the well-known blow-up lemma of Komlós, Sárközy and Szemerédi by proving a ‘blow-up lemma for approximate decompositions’ which states that multipartite quasirandom graphs can be almost decomposed into any collection of bounded degree graphs with the same multipartite structure and slightly fewer edges. This result has already been used by Joos, Kim, Kühn and Osthus to prove the tree packing conjecture due to Gyárfás and Lehel from 1976 and Ringel’s conjecture from 1963 for bounded degree trees as well as implicitly in the recent resolution of the Oberwolfach problem (asked by Ringel in 1967) by Glock, Joos, Kim, Kühn and Osthus.Here we present a new and significantly shorter proof of the blow-up lemma for approximate decompositions. In fact, we prove a more general theorem that yields packings with stronger quasirandom properties which is useful for potential applications.
    12 schema:genre article
    13 schema:isAccessibleForFree false
    14 schema:isPartOf sg:journal.1136493
    15 schema:keywords Bounded Degree Trees
    16 Glock
    17 Gyárfás
    18 Joos
    19 Kim
    20 Komlós
    21 Kühn
    22 Lehel
    23 Oberwolfach problem
    24 Osthus
    25 Szemerédi
    26 Sárközy
    27 Tree Packing Conjecture
    28 Tyomkyn
    29 applications
    30 approximate decomposition
    31 blow
    32 collection
    33 conjecture
    34 decomposition
    35 degree graphs
    36 degree trees
    37 edge
    38 fact
    39 general theorem
    40 graph
    41 lemma
    42 multipartite structure
    43 packing
    44 potential applications
    45 problem
    46 proof
    47 properties
    48 quasirandom graphs
    49 quasirandom properties
    50 recent resolution
    51 resolution
    52 results
    53 short proof
    54 structure
    55 theorem
    56 trees
    57 schema:name A Short Proof of the Blow-Up Lemma for Approximate Decompositions
    58 schema:pagination 1-49
    59 schema:productId N122c2d10aac94e5cbce2a4abe6bfea9f
    60 Nf29fe3d9374d40bdb3138a8ea66dfe8e
    61 schema:sameAs https://app.dimensions.ai/details/publication/pub.1147999038
    62 https://doi.org/10.1007/s00493-020-4640-9
    63 schema:sdDatePublished 2022-10-01T06:49
    64 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    65 schema:sdPublisher N977b28957b7c409fb2e6b02de6213abf
    66 schema:url https://doi.org/10.1007/s00493-020-4640-9
    67 sgo:license sg:explorer/license/
    68 sgo:sdDataset articles
    69 rdf:type schema:ScholarlyArticle
    70 N122c2d10aac94e5cbce2a4abe6bfea9f schema:name dimensions_id
    71 schema:value pub.1147999038
    72 rdf:type schema:PropertyValue
    73 N977b28957b7c409fb2e6b02de6213abf schema:name Springer Nature - SN SciGraph project
    74 rdf:type schema:Organization
    75 N9a08fa37eaa54784b6976d7ac7dc20f9 rdf:first sg:person.012010701657.64
    76 rdf:rest rdf:nil
    77 Nbfc3decab1bf4695b28bd0efaa034ef3 rdf:first sg:person.015003522537.44
    78 rdf:rest N9a08fa37eaa54784b6976d7ac7dc20f9
    79 Nf29fe3d9374d40bdb3138a8ea66dfe8e schema:name doi
    80 schema:value 10.1007/s00493-020-4640-9
    81 rdf:type schema:PropertyValue
    82 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    83 schema:name Information and Computing Sciences
    84 rdf:type schema:DefinedTerm
    85 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    86 schema:name Computation Theory and Mathematics
    87 rdf:type schema:DefinedTerm
    88 sg:journal.1136493 schema:issn 0209-9683
    89 1439-6912
    90 schema:name Combinatorica
    91 schema:publisher Springer Nature
    92 rdf:type schema:Periodical
    93 sg:person.012010701657.64 schema:affiliation grid-institutes:grid.7700.0
    94 schema:familyName Joos
    95 schema:givenName Felix
    96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012010701657.64
    97 rdf:type schema:Person
    98 sg:person.015003522537.44 schema:affiliation grid-institutes:grid.6582.9
    99 schema:familyName Ehard
    100 schema:givenName Stefan
    101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015003522537.44
    102 rdf:type schema:Person
    103 sg:pub.10.1007/bf01196135 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045706665
    104 https://doi.org/10.1007/bf01196135
    105 rdf:type schema:CreativeWork
    106 sg:pub.10.1007/s00039-021-00576-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1140864762
    107 https://doi.org/10.1007/s00039-021-00576-2
    108 rdf:type schema:CreativeWork
    109 sg:pub.10.1007/s004930050063 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031275435
    110 https://doi.org/10.1007/s004930050063
    111 rdf:type schema:CreativeWork
    112 sg:pub.10.1007/s11856-015-1277-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032447673
    113 https://doi.org/10.1007/s11856-015-1277-2
    114 rdf:type schema:CreativeWork
    115 sg:pub.10.1007/s11856-017-1504-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1085394553
    116 https://doi.org/10.1007/s11856-017-1504-0
    117 rdf:type schema:CreativeWork
    118 grid-institutes:grid.6582.9 schema:alternateName Institut für Optimierung und Operations Research, Universität Ulm, Ulm, Germany
    119 schema:name Institut für Optimierung und Operations Research, Universität Ulm, Ulm, Germany
    120 rdf:type schema:Organization
    121 grid-institutes:grid.7700.0 schema:alternateName Institut für Informatik, Universität Heidelberg, Heidelberg, Germany
    122 schema:name Institut für Informatik, Universität Heidelberg, Heidelberg, Germany
    123 rdf:type schema:Organization
     




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


    ...