Any monotone property of 3-uniform hypergraphs is weakly evasive
For a Boolean function f , let D(f) D ( f ) denote its deterministic decision tree complexity, i.e., minimum number of (adaptive) queries required in worst case in order to determine f. In a classic paper, Rivest and Vuillemin [11] show that any non-constant monotone property P : { 0 , 1 } ( n 2 ) ? { 0 , 1 } of n -vertex graphs has D(P)=?(n2) D ( P ) = ? ( n 2 ) . We extend their result to 3-uniform hypergraphs. In particular, we show that any non-constant monotone property P : { 0 , 1 } ( n 3 ) ? { 0 , 1 } of n -vertex 3-uniform hypergraphs has D(P)=?(n3) D ( P ) = ? ( n 3 ) . Our proof combines the combinatorial approach of Rivest and Vuillemin with the topological approach of Kahn, Saks, and Sturtevant [6]. Interestingly, our proof makes use of Vinogradov's Theorem (weak Goldbach Conjecture), inspired by its recent use by Babai et al. [1] in the context of the topological approach. Our work leaves the generalization to k-uniform hypergraphs as an intriguing open question.
evasiveness decision tree complexity hypergraph properties query complexity group actions