EDGE SEARCH IN GRAPHS AND HYPERGRAPHS OF BOUNDED RANK

Given a finite graph G = (V, E), what is the worst-case complexity L(G ) of finding an unknown edge e is-an-element-of E if the following te sts are admitted. For any W subset-of V we may test whether e subset- of W or not. We prove that L(G) less-than-or-equal-to log2 Absolute va lue of E + 3. This result is generalized to hypergraphs H = (V, E) of bounded rank: For any r, there exists some constant gamma(r) such that L(H) less-than-or-equal-to 1092 Absolute value of E + gamma(r) for an y hypergraph with rank less-than-or-equal-to r.