Lower bounds for sensitivity of graph properties

Abstract

We prove that the sensitivity of any non-trivial graph property on $n$ vertices is at least $\lfloor \frac{1}{2}n\rfloor$ , provided $n$ is sufficiently large.

arXiv comment14 pages

References in corpus (1)

• On the Sensitivity Complexity of $k$-Uniform Hypergraph Properties