An improved lower bound on the sensitivity complexity of graph properties

Turán (1984) [11], initiated the study of the sensitivity complexity of graph properties. He conjectured that for any non-trivial graph properties on n vertices, the sensitivity complexity is at least n−1. He proved an lower bound for sensitivity in his paper: Turán (1984) [11], . Wegener (1985) [12] proved this conjecture for all monotone graph properties. In this paper we improve Turán’s lower bound to . We hope that this will shed some light on the proof of Turán’s conjecture.