Any Monotone Property of 3-Uniform Hypergraphs Is Weakly Evasive

摘要

For a Boolean function f, let 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 show that any non-constant monotone property Ρ : {0,1}~（(_2~n)） → {0,1} of n-vertex graphs has 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}~（(_3~n)） → {0, 1} of n-vertex 3-uniform hypergraphs has D(P) = Ω(n~3). Our proof combines the combinatorial approach of Rivest and Vuillemin with the topological approach of Kahn, Saks, and Sturtevant. Interestingly, our proof makes use of Vinogradov's Theorem (weak Gold-bach Conjecture), inspired by its recent use by Babai et. Al. in the context of the topological approach. Our work leaves the generalization to k-uniform hypergraphs as an intriguing open question.