In [1], Turan shows that the sensitivity (called "critical complexity" in the paper) of a graph property is strictly greater than $\lfloor {1\over 4} m \rfloor$ where $m$ is the number of vertices in the graph. He goes on to conjecture that any non-trivial graph property has sensitivity $\geq m-1$. He mentions that this has been verified for $m \leq 5$. Has any progress been made on this conjecture?
Background
Let $x$ be a binary string in $\{0,1\}^n$. Define $x^i$ for $1 \leq i \leq n$ to be the string obtained from $x$ by flipping the $i^{th}$ bit. For a boolean function $f: \{0,1\}^n$ \to $\{0,1\}$, define the sensitivity of $f$ at $x$ as $s(f;x) := |\{i : f(x) \neq f(x^i) \}|$. Finally, define the sensitivity of $f$ as $s(f) := \mbox{max}_x\; s(f;x)$.
A graph property $\mathcal P$ is a collection graphs such that if $G \in \mathcal P$ and $G'$ is isomorphic to $G$ then $G' \in \mathcal P$. We can think of a graph property $\mathcal P$ as the union of properties $\mathcal P_m$ where $\mathcal P_m$ is the subset of $\mathcal P$ consisting of graphs with $m$ vertices. Further, we can conceive of a graph property $\mathcal P_m$ as a boolean function on $\{0,1\}^n$ where $n = {m \choose 2}$. We can encode a graph on $m$ vertices in a binary vector of length $n$; each entry in the vector corresponds to a pair of vertices and the entry is $1$ iff that edge is present in the graph. Thus, the sensitivity of a graph property is its sensitivity qua boolean function.
- Turan, G., The critical complexity of graph properties, Information Processing Letters 18 (1984), 151-153.
