简介:AgraphpropertyisasetofgraphssuchthatifthesetcontainssomegraphGthenitalsocontainseachisomorphiccopyofG(withthesamevertexset).AgraphpropoertyPonnverticesissaidtobeelusive,ifeverydecisiontreealgorithmrecognizingPmustexaminealln(n-1)/2parisofverticesintheworstcase.Karpconjecturedthateverynontrivialmonotonegraphpropertyiselusive,Inthispaper,thisconjectureisprovedforsomecases,Especially,itisshownthatiftheabstractsimplicialcomplexofanontrivialmonotonegraphpropertyPhasdimensionnotexceeding5,thenPiselusive.