Edge search in graphs and hypergraphs of bounded rank

AbstractGiven a finite graph G=(V,E), what is the worst-case complexity L(G) of finding an unknown edge e∗ϵE if the following tests are admitted: For any W⊂V we may test whether e∗⊂W or not. We prove that L(G)⩽log2|E|+3. This result is generalized to hypergraphs H=(V;E) of bounded rank: For any r, there exists some constant γr such that L(H)⩽log2|E|+γr for any hypergraph with rank ⩽r