A topological approach to evasiveness View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1984-12

AUTHORS

Jeff Kahn, Michael Saks, Dean Sturtevant

ABSTRACT

The complexity of a digraph property is the number of entries of the vertex adjacency matrix of a digraph which must be examined in worst case to determine whether the graph has the property. Rivest and Vuillemin proved the result (conjectured by Aanderaa and Rosenberg) that every graph property that is monotone (preserved by addition of edges) and nontrivial (holds for some but not all graphs) has complexity Ω(v2) wherev is the number of vertices. Karp conjectured that every such property is evasive, i.e., requires that every entry of the incidence matrix be examined. In this paper the truth of Karp’s conjecture is shown to follow from another conjecture concerning group actions on topological spaces. A special case of the conjecture is proved which is applied to prove Karp’s conjecture for the case of properties of graphs on a prime power number of vertices. More... »

PAGES

297-306

References to SciGraph publications

  • 1975-12. Fixed-point sets of group actions on finite acyclic complexes in COMMENTARII MATHEMATICI HELVETICI
  • <error retrieving object. in <ERROR RETRIEVING OBJECT
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/bf02579140

    DOI

    http://dx.doi.org/10.1007/bf02579140

    DIMENSIONS

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


    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"
          }, 
          {
            "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"
          }, 
          {
            "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": "Department of Mathematics, Rutgers University, 08903, New Brunswick, NJ, U.S.A.", 
              "id": "http://www.grid.ac/institutes/grid.430387.b", 
              "name": [
                "Department of Mathematics, Rutgers University, 08903, New Brunswick, NJ, U.S.A."
              ], 
              "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, Rutgers University, 08903, New Brunswick, NJ, U.S.A.", 
              "id": "http://www.grid.ac/institutes/grid.430387.b", 
              "name": [
                "Department of Mathematics, Rutgers University, 08903, New Brunswick, NJ, U.S.A."
              ], 
              "type": "Organization"
            }, 
            "familyName": "Saks", 
            "givenName": "Michael", 
            "id": "sg:person.011520224512.05", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Mathematics, University of Illinois, Chicago, U.S.A.", 
              "id": "http://www.grid.ac/institutes/grid.411030.7", 
              "name": [
                "Department of Mathematics, University of Illinois, Chicago, U.S.A."
              ], 
              "type": "Organization"
            }, 
            "familyName": "Sturtevant", 
            "givenName": "Dean", 
            "id": "sg:person.011567122771.36", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011567122771.36"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bf02565743", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038906228", 
              "https://doi.org/10.1007/bf02565743"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4612-9967-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042660971", 
              "https://doi.org/10.1007/978-1-4612-9967-7"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1984-12", 
        "datePublishedReg": "1984-12-01", 
        "description": "The complexity of a digraph property is the number of entries of the vertex adjacency matrix of a digraph which must be examined in worst case to determine whether the graph has the property. Rivest and Vuillemin proved the result (conjectured by Aanderaa and Rosenberg) that every graph property that is monotone (preserved by addition of edges) and nontrivial (holds for some but not all graphs) has complexity \u03a9(v2) wherev is the number of vertices. Karp conjectured that every such property is evasive, i.e., requires that every entry of the incidence matrix be examined. In this paper the truth of Karp\u2019s conjecture is shown to follow from another conjecture concerning group actions on topological spaces. A special case of the conjecture is proved which is applied to prove Karp\u2019s conjecture for the case of properties of graphs on a prime power number of vertices.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/bf02579140", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1136493", 
            "issn": [
              "0209-9683", 
              "1439-6912"
            ], 
            "name": "Combinatorica", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "4", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "4"
          }
        ], 
        "keywords": [
          "vertex adjacency matrix", 
          "number of vertices", 
          "prime power number", 
          "digraph properties", 
          "graph properties", 
          "group actions", 
          "adjacency matrix", 
          "topological spaces", 
          "incidence matrix", 
          "special case", 
          "topological approach", 
          "conjecture", 
          "case of properties", 
          "vertices", 
          "graph", 
          "such properties", 
          "worst case", 
          "power number", 
          "matrix", 
          "complexity", 
          "whereV", 
          "digraphs", 
          "properties", 
          "space", 
          "Karp", 
          "number", 
          "number of entries", 
          "cases", 
          "Rivest", 
          "approach", 
          "results", 
          "entry", 
          "evasiveness", 
          "truth", 
          "action", 
          "Vuillemin", 
          "paper"
        ], 
        "name": "A topological approach to evasiveness", 
        "pagination": "297-306", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1003545223"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf02579140"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf02579140", 
          "https://app.dimensions.ai/details/publication/pub.1003545223"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-10-01T06:27", 
        "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_154.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/bf02579140"
      }
    ]
     

    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/bf02579140'

    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/bf02579140'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf02579140'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf02579140'


     

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

    127 TRIPLES      21 PREDICATES      66 URIs      54 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf02579140 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 anzsrc-for:08
    4 anzsrc-for:0802
    5 schema:author N15290a124ccb4e3688ba6d6390e90af1
    6 schema:citation sg:pub.10.1007/978-1-4612-9967-7
    7 sg:pub.10.1007/bf02565743
    8 schema:datePublished 1984-12
    9 schema:datePublishedReg 1984-12-01
    10 schema:description The complexity of a digraph property is the number of entries of the vertex adjacency matrix of a digraph which must be examined in worst case to determine whether the graph has the property. Rivest and Vuillemin proved the result (conjectured by Aanderaa and Rosenberg) that every graph property that is monotone (preserved by addition of edges) and nontrivial (holds for some but not all graphs) has complexity Ω(v2) wherev is the number of vertices. Karp conjectured that every such property is evasive, i.e., requires that every entry of the incidence matrix be examined. In this paper the truth of Karp’s conjecture is shown to follow from another conjecture concerning group actions on topological spaces. A special case of the conjecture is proved which is applied to prove Karp’s conjecture for the case of properties of graphs on a prime power number of vertices.
    11 schema:genre article
    12 schema:isAccessibleForFree false
    13 schema:isPartOf N231ccafd3c56456c997997f9775ec29b
    14 N4084553a8ce5447f8683f8ca0b7f6bf5
    15 sg:journal.1136493
    16 schema:keywords Karp
    17 Rivest
    18 Vuillemin
    19 action
    20 adjacency matrix
    21 approach
    22 case of properties
    23 cases
    24 complexity
    25 conjecture
    26 digraph properties
    27 digraphs
    28 entry
    29 evasiveness
    30 graph
    31 graph properties
    32 group actions
    33 incidence matrix
    34 matrix
    35 number
    36 number of entries
    37 number of vertices
    38 paper
    39 power number
    40 prime power number
    41 properties
    42 results
    43 space
    44 special case
    45 such properties
    46 topological approach
    47 topological spaces
    48 truth
    49 vertex adjacency matrix
    50 vertices
    51 whereV
    52 worst case
    53 schema:name A topological approach to evasiveness
    54 schema:pagination 297-306
    55 schema:productId N4685ff1eaa7d4c2a96c45a1f090f9af6
    56 Na520f75d39954f1d8ef8225fc5102ccc
    57 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003545223
    58 https://doi.org/10.1007/bf02579140
    59 schema:sdDatePublished 2022-10-01T06:27
    60 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    61 schema:sdPublisher Nb8e696feda1742338bc5cce9bc40cac3
    62 schema:url https://doi.org/10.1007/bf02579140
    63 sgo:license sg:explorer/license/
    64 sgo:sdDataset articles
    65 rdf:type schema:ScholarlyArticle
    66 N0f2326d41c6c4afda215a26fa77d3c07 rdf:first sg:person.011567122771.36
    67 rdf:rest rdf:nil
    68 N15290a124ccb4e3688ba6d6390e90af1 rdf:first sg:person.07651605463.67
    69 rdf:rest N1b0ed78fb06d45e1acfe3225ee60662a
    70 N1b0ed78fb06d45e1acfe3225ee60662a rdf:first sg:person.011520224512.05
    71 rdf:rest N0f2326d41c6c4afda215a26fa77d3c07
    72 N231ccafd3c56456c997997f9775ec29b schema:volumeNumber 4
    73 rdf:type schema:PublicationVolume
    74 N4084553a8ce5447f8683f8ca0b7f6bf5 schema:issueNumber 4
    75 rdf:type schema:PublicationIssue
    76 N4685ff1eaa7d4c2a96c45a1f090f9af6 schema:name doi
    77 schema:value 10.1007/bf02579140
    78 rdf:type schema:PropertyValue
    79 Na520f75d39954f1d8ef8225fc5102ccc schema:name dimensions_id
    80 schema:value pub.1003545223
    81 rdf:type schema:PropertyValue
    82 Nb8e696feda1742338bc5cce9bc40cac3 schema:name Springer Nature - SN SciGraph project
    83 rdf:type schema:Organization
    84 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    85 schema:name Mathematical Sciences
    86 rdf:type schema:DefinedTerm
    87 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    88 schema:name Pure Mathematics
    89 rdf:type schema:DefinedTerm
    90 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    91 schema:name Information and Computing Sciences
    92 rdf:type schema:DefinedTerm
    93 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    94 schema:name Computation Theory and Mathematics
    95 rdf:type schema:DefinedTerm
    96 sg:journal.1136493 schema:issn 0209-9683
    97 1439-6912
    98 schema:name Combinatorica
    99 schema:publisher Springer Nature
    100 rdf:type schema:Periodical
    101 sg:person.011520224512.05 schema:affiliation grid-institutes:grid.430387.b
    102 schema:familyName Saks
    103 schema:givenName Michael
    104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05
    105 rdf:type schema:Person
    106 sg:person.011567122771.36 schema:affiliation grid-institutes:grid.411030.7
    107 schema:familyName Sturtevant
    108 schema:givenName Dean
    109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011567122771.36
    110 rdf:type schema:Person
    111 sg:person.07651605463.67 schema:affiliation grid-institutes:grid.430387.b
    112 schema:familyName Kahn
    113 schema:givenName Jeff
    114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07651605463.67
    115 rdf:type schema:Person
    116 sg:pub.10.1007/978-1-4612-9967-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042660971
    117 https://doi.org/10.1007/978-1-4612-9967-7
    118 rdf:type schema:CreativeWork
    119 sg:pub.10.1007/bf02565743 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038906228
    120 https://doi.org/10.1007/bf02565743
    121 rdf:type schema:CreativeWork
    122 grid-institutes:grid.411030.7 schema:alternateName Department of Mathematics, University of Illinois, Chicago, U.S.A.
    123 schema:name Department of Mathematics, University of Illinois, Chicago, U.S.A.
    124 rdf:type schema:Organization
    125 grid-institutes:grid.430387.b schema:alternateName Department of Mathematics, Rutgers University, 08903, New Brunswick, NJ, U.S.A.
    126 schema:name Department of Mathematics, Rutgers University, 08903, New Brunswick, NJ, U.S.A.
    127 rdf:type schema:Organization
     




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


    ...