On the Sensitivity Complexity of <i>k</i> -Uniform Hypergraph Properties
On the Sensitivity Complexity of <i>k</i> -Uniform Hypergraph Properties
In this article, we investigate the sensitivity complexity of hypergraph properties. We present a k -uniform hypergraph property with sensitivity complexity O ( n (⌈ k/3 ⌉) for any k ≥ 3 , where n is the number of vertices. Moreover, we can do better when k ≡ 1 (mod …