Derived from Koslov, Evasiveness Conjecture; Fwd: SEQ FROM Jonathan Vos Post

[Jonathan Post]

I'm wondering if this one got lost in the mail, or is still being
edited?  Seems as if enough time has gone by, and enouigh new seqs
online.  Just wondering.

---------- Forwarded message ----------
From: The On-Line Encyclopedia of Integer Sequences <oeis at research.att.com>
Date: Feb 28, 2008 12:56 PM
Subject: SEQ FROM Jonathan Vos Post
To: njas at research.att.com
Cc: jvospost3 at gmail.com

The following is a copy of the email message that was sent to njas
 containing the sequence you submitted.

 All greater than and less than signs have been replaced by their html
 equivalents.  They will be changed back when the message is processed.

 This copy is just for your records.  No reply is expected.
  Subject: NEW SEQUENCE FROM Jonathan Vos Post


 %I A000001
 %S A000001 1, 2, 3, 4, 5, 6, 7, 8, 9, 11
 %N A000001 The number of vertices for which the Evasiveness
Conjecture has been verified for nontrivial monotone graph properties.
 %C A000001 Kozlov, p.3: "To get a rough idea, the reader should
consider the set of all graphs on n vertices, where n is fixed,
satisfying a certain graph property that is preserved by deletion of
edges (i.e. planarity). The Evasiveness Conjecture then says that if
one is trying to determine whether a given graph has this property or
not, by using simple edge oracles, i.e. by asking whether a certain
edge is in the graph or not, then one may have to ask all
[A000217(n-1)] questions. Curiously, this conjecture is still open."
 %D A000001 Dmitry Kozlov, Combinatorial algebraic topology
(Algorithms & computation in mathematics, Vol. 21), Springer, 2008,
Chapter 13.
 %e A000001 "Conjecture 13.4. (Evasiveness Conjecture, a.k.a. Karp
Conjecture).  Every nontrivial monotone graph property for graphs on n
vertices is evasive. So far, the Evasiveness Conjecture has been
verified in the case when n is a prime power [A000961], and
additionally when n = 6." [Kozlov, p.228]. Hence n=10 is the first
integer which we do not know belongs in this sequence or not.
 %Y A000001 cf. A000217, A000961.
 %O A000001 1,2
 %K A000001 ,hard,nonn,
 %A A000001 Jonathan Vos Post (jvospost3 at gmail.com), Feb 28 2008
 RH
 RA 192.20.225.32
 RU
 RI