A Hypergraph Turán Problem with No Stability View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2022-02-18

AUTHORS

Xizhi Liu, Dhruv Mubayi

ABSTRACT

A fundamental barrier in extremal hypergraph theory is the presence of many near-extremal constructions with very different structures. Indeed, the classical constructions due to Kostochka imply that the notorious extremal problem for the tetrahedron exhibits this phenomenon assuming Turán’s conjecture.Our main result is to construct a finite family of triple systems ℳ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\cal M}$$\end{document}, determine its Turán number, and prove that there are two near-extremal ℳ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\cal M}$$\end{document}-free constructions that are far from each other in edit-distance. This is the first extremal result for a hypergraph family that fails to have a corresponding stability theorem. More... »

PAGES

1-30

References to SciGraph publications

  • 2014-01. ON possible Turán densities in ISRAEL JOURNAL OF MATHEMATICS
  • 2005-12. On A Hypergraph Turán Problem Of Frankl in COMBINATORICA
  • 2005-09. The Turán Number Of The Fano Plane in COMBINATORICA
  • 1982-06. A class of constructions for turán’s (3, 4)-problem in COMBINATORICA
  • 2008-03. An exact Turán result for the generalized triangle in COMBINATORICA
  • 1983. On an open problem of Paul Turán concerning 3-graphs in STUDIES IN PURE MATHEMATICS
  • 1995-06. What we know and what we do not know about Turán numbers in GRAPHS AND COMBINATORICS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00493-021-4561-2

    DOI

    http://dx.doi.org/10.1007/s00493-021-4561-2

    DIMENSIONS

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


    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": "Department of Mathematics, Statistics and Computer Science, University of Illinois, 60607, Chicago, IL, USA", 
              "id": "http://www.grid.ac/institutes/grid.185648.6", 
              "name": [
                "Department of Mathematics, Statistics and Computer Science, University of Illinois, 60607, Chicago, IL, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Liu", 
            "givenName": "Xizhi", 
            "id": "sg:person.014073515137.69", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014073515137.69"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Mathematics, Statistics and Computer Science, University of Illinois, 60607, Chicago, IL, USA", 
              "id": "http://www.grid.ac/institutes/grid.185648.6", 
              "name": [
                "Department of Mathematics, Statistics and Computer Science, University of Illinois, 60607, Chicago, IL, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Mubayi", 
            "givenName": "Dhruv", 
            "id": "sg:person.013521032647.30", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013521032647.30"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-3-0348-5438-2_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022991849", 
              "https://doi.org/10.1007/978-3-0348-5438-2_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00493-008-2187-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039527958", 
              "https://doi.org/10.1007/s00493-008-2187-2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00493-005-0042-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012136817", 
              "https://doi.org/10.1007/s00493-005-0042-2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02579317", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043990346", 
              "https://doi.org/10.1007/bf02579317"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00493-005-0034-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048155738", 
              "https://doi.org/10.1007/s00493-005-0034-2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01929486", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018637006", 
              "https://doi.org/10.1007/bf01929486"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s11856-014-0031-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049313706", 
              "https://doi.org/10.1007/s11856-014-0031-5"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2022-02-18", 
        "datePublishedReg": "2022-02-18", 
        "description": "A fundamental barrier in extremal hypergraph theory is the presence of many near-extremal constructions with very different structures. Indeed, the classical constructions due to Kostochka imply that the notorious extremal problem for the tetrahedron exhibits this phenomenon assuming Tur\u00e1n\u2019s conjecture.Our main result is to construct a finite family of triple systems \u2133\\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}$${\\cal M}$$\\end{document}, determine its Tur\u00e1n number, and prove that there are two near-extremal \u2133\\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}$${\\cal M}$$\\end{document}-free constructions that are far from each other in edit-distance. This is the first extremal result for a hypergraph family that fails to have a corresponding stability theorem.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00493-021-4561-2", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1136493", 
            "issn": [
              "0209-9683", 
              "1439-6912"
            ], 
            "name": "Combinatorica", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }
        ], 
        "keywords": [
          "corresponding stability theorem", 
          "stability theorem", 
          "hypergraph Tur\u00e1n problems", 
          "finite family", 
          "Tur\u00e1n number", 
          "extremal problems", 
          "extremal results", 
          "Tur\u00e1n problem", 
          "hypergraph theory", 
          "classical construction", 
          "Tur\u00e1n\u2019s conjecture", 
          "extremal construction", 
          "triple systems", 
          "hypergraph families", 
          "conjecture", 
          "extremal hypergraph theory", 
          "free construction", 
          "main results", 
          "theorem", 
          "problem", 
          "Kostochka", 
          "different structures", 
          "theory", 
          "construction", 
          "tetrahedra", 
          "phenomenon", 
          "results", 
          "system", 
          "fundamental barrier", 
          "stability", 
          "number", 
          "structure", 
          "family", 
          "presence", 
          "barriers"
        ], 
        "name": "A Hypergraph Tur\u00e1n Problem with No Stability", 
        "pagination": "1-30", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1145698746"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00493-021-4561-2"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00493-021-4561-2", 
          "https://app.dimensions.ai/details/publication/pub.1145698746"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-09-02T16:06", 
        "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_931.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00493-021-4561-2"
      }
    ]
     

    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-4561-2'

    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-4561-2'

    Turtle is a human-readable linked data format.

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

    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-4561-2'


     

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

    121 TRIPLES      21 PREDICATES      64 URIs      49 LITERALS      4 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00493-021-4561-2 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author N03a7b98e782346fcb30d9974e9db0d92
    4 schema:citation sg:pub.10.1007/978-3-0348-5438-2_9
    5 sg:pub.10.1007/bf01929486
    6 sg:pub.10.1007/bf02579317
    7 sg:pub.10.1007/s00493-005-0034-2
    8 sg:pub.10.1007/s00493-005-0042-2
    9 sg:pub.10.1007/s00493-008-2187-2
    10 sg:pub.10.1007/s11856-014-0031-5
    11 schema:datePublished 2022-02-18
    12 schema:datePublishedReg 2022-02-18
    13 schema:description A fundamental barrier in extremal hypergraph theory is the presence of many near-extremal constructions with very different structures. Indeed, the classical constructions due to Kostochka imply that the notorious extremal problem for the tetrahedron exhibits this phenomenon assuming Turán’s conjecture.Our main result is to construct a finite family of triple systems ℳ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\cal M}$$\end{document}, determine its Turán number, and prove that there are two near-extremal ℳ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\cal M}$$\end{document}-free constructions that are far from each other in edit-distance. This is the first extremal result for a hypergraph family that fails to have a corresponding stability theorem.
    14 schema:genre article
    15 schema:isAccessibleForFree false
    16 schema:isPartOf sg:journal.1136493
    17 schema:keywords Kostochka
    18 Turán number
    19 Turán problem
    20 Turán’s conjecture
    21 barriers
    22 classical construction
    23 conjecture
    24 construction
    25 corresponding stability theorem
    26 different structures
    27 extremal construction
    28 extremal hypergraph theory
    29 extremal problems
    30 extremal results
    31 family
    32 finite family
    33 free construction
    34 fundamental barrier
    35 hypergraph Turán problems
    36 hypergraph families
    37 hypergraph theory
    38 main results
    39 number
    40 phenomenon
    41 presence
    42 problem
    43 results
    44 stability
    45 stability theorem
    46 structure
    47 system
    48 tetrahedra
    49 theorem
    50 theory
    51 triple systems
    52 schema:name A Hypergraph Turán Problem with No Stability
    53 schema:pagination 1-30
    54 schema:productId Nc98b7ba007c04cac951f6e5d8db1af3d
    55 Nf849888e76f34913979324369f8f725e
    56 schema:sameAs https://app.dimensions.ai/details/publication/pub.1145698746
    57 https://doi.org/10.1007/s00493-021-4561-2
    58 schema:sdDatePublished 2022-09-02T16:06
    59 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    60 schema:sdPublisher Nc7197418da444320b5d47f987c145e5f
    61 schema:url https://doi.org/10.1007/s00493-021-4561-2
    62 sgo:license sg:explorer/license/
    63 sgo:sdDataset articles
    64 rdf:type schema:ScholarlyArticle
    65 N03a7b98e782346fcb30d9974e9db0d92 rdf:first sg:person.014073515137.69
    66 rdf:rest Ne1102080fded4c4fbff9a9478936f0c9
    67 Nc7197418da444320b5d47f987c145e5f schema:name Springer Nature - SN SciGraph project
    68 rdf:type schema:Organization
    69 Nc98b7ba007c04cac951f6e5d8db1af3d schema:name doi
    70 schema:value 10.1007/s00493-021-4561-2
    71 rdf:type schema:PropertyValue
    72 Ne1102080fded4c4fbff9a9478936f0c9 rdf:first sg:person.013521032647.30
    73 rdf:rest rdf:nil
    74 Nf849888e76f34913979324369f8f725e schema:name dimensions_id
    75 schema:value pub.1145698746
    76 rdf:type schema:PropertyValue
    77 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    78 schema:name Mathematical Sciences
    79 rdf:type schema:DefinedTerm
    80 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    81 schema:name Pure Mathematics
    82 rdf:type schema:DefinedTerm
    83 sg:journal.1136493 schema:issn 0209-9683
    84 1439-6912
    85 schema:name Combinatorica
    86 schema:publisher Springer Nature
    87 rdf:type schema:Periodical
    88 sg:person.013521032647.30 schema:affiliation grid-institutes:grid.185648.6
    89 schema:familyName Mubayi
    90 schema:givenName Dhruv
    91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013521032647.30
    92 rdf:type schema:Person
    93 sg:person.014073515137.69 schema:affiliation grid-institutes:grid.185648.6
    94 schema:familyName Liu
    95 schema:givenName Xizhi
    96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014073515137.69
    97 rdf:type schema:Person
    98 sg:pub.10.1007/978-3-0348-5438-2_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022991849
    99 https://doi.org/10.1007/978-3-0348-5438-2_9
    100 rdf:type schema:CreativeWork
    101 sg:pub.10.1007/bf01929486 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018637006
    102 https://doi.org/10.1007/bf01929486
    103 rdf:type schema:CreativeWork
    104 sg:pub.10.1007/bf02579317 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043990346
    105 https://doi.org/10.1007/bf02579317
    106 rdf:type schema:CreativeWork
    107 sg:pub.10.1007/s00493-005-0034-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048155738
    108 https://doi.org/10.1007/s00493-005-0034-2
    109 rdf:type schema:CreativeWork
    110 sg:pub.10.1007/s00493-005-0042-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012136817
    111 https://doi.org/10.1007/s00493-005-0042-2
    112 rdf:type schema:CreativeWork
    113 sg:pub.10.1007/s00493-008-2187-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039527958
    114 https://doi.org/10.1007/s00493-008-2187-2
    115 rdf:type schema:CreativeWork
    116 sg:pub.10.1007/s11856-014-0031-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049313706
    117 https://doi.org/10.1007/s11856-014-0031-5
    118 rdf:type schema:CreativeWork
    119 grid-institutes:grid.185648.6 schema:alternateName Department of Mathematics, Statistics and Computer Science, University of Illinois, 60607, Chicago, IL, USA
    120 schema:name Department of Mathematics, Statistics and Computer Science, University of Illinois, 60607, Chicago, IL, USA
    121 rdf:type schema:Organization
     




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


    ...