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

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-12-01T06:18", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221201/entities/gbq_results/article/article_155.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 N1d7c966833184619828cdbdce04c1d0e
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 N00476c4d81f54067b53275b40d6b0f82
14 N641213ac0a8849179891edcefeeca8a7
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 N64d19cf4b74f4c97a5f758f2926127c4
56 N75249f56572642a2a21e41583607d332
57 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003545223
58 https://doi.org/10.1007/bf02579140
59 schema:sdDatePublished 2022-12-01T06:18
60 schema:sdLicense https://scigraph.springernature.com/explorer/license/
61 schema:sdPublisher N687ed0fa9c104ee4b32f41c8b055ec64
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 N00476c4d81f54067b53275b40d6b0f82 schema:issueNumber 4
67 rdf:type schema:PublicationIssue
68 N1d7c966833184619828cdbdce04c1d0e rdf:first sg:person.07651605463.67
69 rdf:rest N21d0a612ce4c43e9b54f3cd7cb003045
70 N21d0a612ce4c43e9b54f3cd7cb003045 rdf:first sg:person.011520224512.05
71 rdf:rest N85d0a377959f44d19b2df843464124ff
72 N641213ac0a8849179891edcefeeca8a7 schema:volumeNumber 4
73 rdf:type schema:PublicationVolume
74 N64d19cf4b74f4c97a5f758f2926127c4 schema:name doi
75 schema:value 10.1007/bf02579140
76 rdf:type schema:PropertyValue
77 N687ed0fa9c104ee4b32f41c8b055ec64 schema:name Springer Nature - SN SciGraph project
78 rdf:type schema:Organization
79 N75249f56572642a2a21e41583607d332 schema:name dimensions_id
80 schema:value pub.1003545223
81 rdf:type schema:PropertyValue
82 N85d0a377959f44d19b2df843464124ff rdf:first sg:person.011567122771.36
83 rdf:rest rdf:nil
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)


...