ECCC-Report TR14-061https://eccc.weizmann.ac.il/report/2014/061Comments and Revisions published for TR14-061en-usMon, 21 Apr 2014 19:23:56 +0300
Paper TR14-061
| Any Monotone Property of 3-uniform Hypergraphs is Weakly Evasive |
Raghav Kulkarni,
Youming Qiao,
Xiaoming Sun
https://eccc.weizmann.ac.il/report/2014/061 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 \cite{rv} show that any non-constant monotone property $\mathcal{P} : \{0, 1\}^{n \choose 2} \to \{0, 1\}$ of $n$-vertex graphs has $D(\mathcal{P}) = \Omega(n^2).$
We extend their result to $3$-uniform hypergraphs. In particular, we show that any non-constant monotone property $\mathcal{P} : \{0, 1\}^{n \choose 3} \to \{0, 1\}$ of $n$-vertex $3$-uniform hypergraphs has $D(\mathcal{P}) = \Omega(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 Goldbach Conjecture), inspired by its recent use by Babai et. al. \cite{bbkn} in the context of the topological approach. Our work leaves the generalization to $k$-uniform hypergraphs as an intriguing open question. Mon, 21 Apr 2014 19:23:56 +0300https://eccc.weizmann.ac.il/report/2014/061