A generalized model for understanding evasiveness (Q1825645)

In the study of evasive graph properties one considers decision-tree like algorithms which decide graph properties by probing for the resence or absence of particular edges in an initially fully unknown graph. The algorithms are adaptive in the sense that the answers on previous questions influence the choice of the next edge to be probed. The algorithm terminates as soon as the property under investigation can be decided on the basis of the partial information about the graph selected so far. Evasive properties are those properties where the algorithm can be forced to probe all edges before it can decide the property. It is known that a large collection of monotone non-trivial graph properties are evasive, and that all such properties force the algorithm to probe at least one quarter of all edges. The class of possible questions has been enlarged: given a set of vertices the number of edges between vertices in this set is provided. On the other hand the aim of the algorithm has become the determination of the complete graph - a target which in the single-edge probe model immediately would force evasiveness. The authors show that, given the new type of questions arbitrary graphs (and consequently all graph properties) can be deciced in \((2n^ 2/\log n)+o(n^ 2/\log n)\) questions and that this number is optimal up to a constant factor. This result is obtained from a similar result (an O(n/log n) bound) for a one-dimensional version of the problem, which in turn is used as a key lemma in the proof of the two-dimensional result. Only in the final section the case of deciding graph properties with use of the new sort of questions is addressed. A connection with a communication complexity result by Hajnal, Mass and Turan is presented.