The Number of Maximal Independent Sets in the Hamming Cube View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2022-03-14

AUTHORS

Jeff Kahn, Jinyoung Park

ABSTRACT

Let Qn be the n-dimensional Hamming cube and N = 2n. We prove that the number of maximal independent sets in Qn is asymptotically 2n2N/4,\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2n{2^{N/4}},$$\end{document} as was conjectured by Ilinca and the first author in connection with a question of Duffus, Frankl and Rödl.The value is a natural lower bound derived from a connection between maximal independent sets and induced matchings. The proof that it is also an upper bound draws on various tools, among them “stability” results for maximal independent set counts and old and new results on isoperimetric behavior in Qn. More... »

PAGES

1-28

References to SciGraph publications

  • 2020-03-16. The number of 4-colorings of the Hamming cube in ISRAEL JOURNAL OF MATHEMATICS
  • 2007-06. The number of independent sets in graphs in MOSCOW UNIVERSITY MATHEMATICS BULLETIN
  • 2003-03. On homomorphisms from the Hamming cube to Z in ISRAEL JOURNAL OF MATHEMATICS
  • 2012-03-09. Counting Maximal Antichains and Independent Sets in ORDER
  • Identifiers

    URI

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

    DOI

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

    DIMENSIONS

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


    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, Rutgers University Hill Center for the Mathematical Sciences, 110 Frelinghuysen Rd., 08854-8019, Piscataway, NJ, USA", 
              "id": "http://www.grid.ac/institutes/grid.430387.b", 
              "name": [
                "Department of Mathematics, Rutgers University Hill Center for the Mathematical Sciences, 110 Frelinghuysen Rd., 08854-8019, Piscataway, NJ, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Kahn", 
            "givenName": "Jeff", 
            "id": "sg:person.07651605463.67", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07651605463.67"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Mathematics, Stanford University, 450Jane Stanford Way, Building 380, 94305, Stanford, CA, USA", 
              "id": "http://www.grid.ac/institutes/grid.168010.e", 
              "name": [
                "Department of Mathematics, Stanford University, 450Jane Stanford Way, Building 380, 94305, Stanford, CA, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Park", 
            "givenName": "Jinyoung", 
            "id": "sg:person.010363001175.67", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010363001175.67"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/s11856-020-1984-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1125683848", 
              "https://doi.org/10.1007/s11856-020-1984-1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.3103/s0027132207030072", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001251756", 
              "https://doi.org/10.3103/s0027132207030072"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s11083-012-9253-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004967282", 
              "https://doi.org/10.1007/s11083-012-9253-5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02783426", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053142527", 
              "https://doi.org/10.1007/bf02783426"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2022-03-14", 
        "datePublishedReg": "2022-03-14", 
        "description": "Let Qn be the n-dimensional Hamming cube and N = 2n. We prove that the number of maximal independent sets in Qn is asymptotically 2n2N/4,\\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}$$2n{2^{N/4}},$$\\end{document} as was conjectured by Ilinca and the first author in connection with a question of Duffus, Frankl and R\u00f6dl.The value is a natural lower bound derived from a connection between maximal independent sets and induced matchings. The proof that it is also an upper bound draws on various tools, among them \u201cstability\u201d results for maximal independent set counts and old and new results on isoperimetric behavior in Qn.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00493-021-4729-9", 
        "isAccessibleForFree": true, 
        "isFundedItemOf": [
          {
            "id": "sg:grant.4057944", 
            "type": "MonetaryGrant"
          }
        ], 
        "isPartOf": [
          {
            "id": "sg:journal.1136493", 
            "issn": [
              "0209-9683", 
              "1439-6912"
            ], 
            "name": "Combinatorica", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }
        ], 
        "keywords": [
          "maximal independent sets", 
          "Hamming cube", 
          "independent set", 
          "induced matching", 
          "new results", 
          "Qn", 
          "set", 
          "first author", 
          "R\u00f6dl", 
          "cube", 
          "number", 
          "connection", 
          "proof", 
          "Duffus", 
          "Frankl", 
          "matching", 
          "tool", 
          "results", 
          "behavior", 
          "authors", 
          "values", 
          "draw", 
          "questions", 
          "count"
        ], 
        "name": "The Number of Maximal Independent Sets in the Hamming Cube", 
        "pagination": "1-28", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1146254934"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00493-021-4729-9"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00493-021-4729-9", 
          "https://app.dimensions.ai/details/publication/pub.1146254934"
        ], 
        "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_943.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00493-021-4729-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-4729-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-4729-9'

    Turtle is a human-readable linked data format.

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


     

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

    103 TRIPLES      21 PREDICATES      50 URIs      38 LITERALS      4 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00493-021-4729-9 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author N1801ec612eb445338bd35ea94215ca02
    4 schema:citation sg:pub.10.1007/bf02783426
    5 sg:pub.10.1007/s11083-012-9253-5
    6 sg:pub.10.1007/s11856-020-1984-1
    7 sg:pub.10.3103/s0027132207030072
    8 schema:datePublished 2022-03-14
    9 schema:datePublishedReg 2022-03-14
    10 schema:description Let Qn be the n-dimensional Hamming cube and N = 2n. We prove that the number of maximal independent sets in Qn is asymptotically 2n2N/4,\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2n{2^{N/4}},$$\end{document} as was conjectured by Ilinca and the first author in connection with a question of Duffus, Frankl and Rödl.The value is a natural lower bound derived from a connection between maximal independent sets and induced matchings. The proof that it is also an upper bound draws on various tools, among them “stability” results for maximal independent set counts and old and new results on isoperimetric behavior in Qn.
    11 schema:genre article
    12 schema:isAccessibleForFree true
    13 schema:isPartOf sg:journal.1136493
    14 schema:keywords Duffus
    15 Frankl
    16 Hamming cube
    17 Qn
    18 Rödl
    19 authors
    20 behavior
    21 connection
    22 count
    23 cube
    24 draw
    25 first author
    26 independent set
    27 induced matching
    28 matching
    29 maximal independent sets
    30 new results
    31 number
    32 proof
    33 questions
    34 results
    35 set
    36 tool
    37 values
    38 schema:name The Number of Maximal Independent Sets in the Hamming Cube
    39 schema:pagination 1-28
    40 schema:productId N43c7df8b381c46f689db4e7e328c5754
    41 Nd28d9402af6b421790efe0dd8c4d65be
    42 schema:sameAs https://app.dimensions.ai/details/publication/pub.1146254934
    43 https://doi.org/10.1007/s00493-021-4729-9
    44 schema:sdDatePublished 2022-09-02T16:08
    45 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    46 schema:sdPublisher N3eaf1c4f32774ded859f126a4a5836a3
    47 schema:url https://doi.org/10.1007/s00493-021-4729-9
    48 sgo:license sg:explorer/license/
    49 sgo:sdDataset articles
    50 rdf:type schema:ScholarlyArticle
    51 N1801ec612eb445338bd35ea94215ca02 rdf:first sg:person.07651605463.67
    52 rdf:rest N26a1a636ffe34f40986f503054b8bc61
    53 N26a1a636ffe34f40986f503054b8bc61 rdf:first sg:person.010363001175.67
    54 rdf:rest rdf:nil
    55 N3eaf1c4f32774ded859f126a4a5836a3 schema:name Springer Nature - SN SciGraph project
    56 rdf:type schema:Organization
    57 N43c7df8b381c46f689db4e7e328c5754 schema:name doi
    58 schema:value 10.1007/s00493-021-4729-9
    59 rdf:type schema:PropertyValue
    60 Nd28d9402af6b421790efe0dd8c4d65be schema:name dimensions_id
    61 schema:value pub.1146254934
    62 rdf:type schema:PropertyValue
    63 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    64 schema:name Mathematical Sciences
    65 rdf:type schema:DefinedTerm
    66 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    67 schema:name Pure Mathematics
    68 rdf:type schema:DefinedTerm
    69 sg:grant.4057944 http://pending.schema.org/fundedItem sg:pub.10.1007/s00493-021-4729-9
    70 rdf:type schema:MonetaryGrant
    71 sg:journal.1136493 schema:issn 0209-9683
    72 1439-6912
    73 schema:name Combinatorica
    74 schema:publisher Springer Nature
    75 rdf:type schema:Periodical
    76 sg:person.010363001175.67 schema:affiliation grid-institutes:grid.168010.e
    77 schema:familyName Park
    78 schema:givenName Jinyoung
    79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010363001175.67
    80 rdf:type schema:Person
    81 sg:person.07651605463.67 schema:affiliation grid-institutes:grid.430387.b
    82 schema:familyName Kahn
    83 schema:givenName Jeff
    84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07651605463.67
    85 rdf:type schema:Person
    86 sg:pub.10.1007/bf02783426 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053142527
    87 https://doi.org/10.1007/bf02783426
    88 rdf:type schema:CreativeWork
    89 sg:pub.10.1007/s11083-012-9253-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004967282
    90 https://doi.org/10.1007/s11083-012-9253-5
    91 rdf:type schema:CreativeWork
    92 sg:pub.10.1007/s11856-020-1984-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1125683848
    93 https://doi.org/10.1007/s11856-020-1984-1
    94 rdf:type schema:CreativeWork
    95 sg:pub.10.3103/s0027132207030072 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001251756
    96 https://doi.org/10.3103/s0027132207030072
    97 rdf:type schema:CreativeWork
    98 grid-institutes:grid.168010.e schema:alternateName Department of Mathematics, Stanford University, 450Jane Stanford Way, Building 380, 94305, Stanford, CA, USA
    99 schema:name Department of Mathematics, Stanford University, 450Jane Stanford Way, Building 380, 94305, Stanford, CA, USA
    100 rdf:type schema:Organization
    101 grid-institutes:grid.430387.b schema:alternateName Department of Mathematics, Rutgers University Hill Center for the Mathematical Sciences, 110 Frelinghuysen Rd., 08854-8019, Piscataway, NJ, USA
    102 schema:name Department of Mathematics, Rutgers University Hill Center for the Mathematical Sciences, 110 Frelinghuysen Rd., 08854-8019, Piscataway, NJ, USA
    103 rdf:type schema:Organization
     




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


    ...