Any monotone property of 3-uniform hypergraphs is weakly evasive

Publication Type:
Conference Proceeding
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2013, 7876 LNCS pp. 224 - 235
Issue Date:
Filename Description Size
Thumbnail2013005434OK.pdf230.47 kB
Adobe PDF
Full metadata record
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 [18] show that any non-constant monotone property P: {0,1} (2n) → {0,1} of n-vertex graphs has D(P) = Ω (n). We extend their result to 3-uniform hypergraphs. In particular, we show that any non-constant monotone property P: {0,1} (3n) → {0,1} of n-vertex 3-uniform hypergraphs has D(P) = Ω (n). 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. [1] in the context of the topological approach. Our work leaves the generalization to k-uniform hypergraphs as an intriguing open question. © Springer-Verlag Berlin Heidelberg 2013.
Please use this identifier to cite or link to this item: