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?


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.

  1. Turan, G., The critical complexity of graph properties, Information Processing Letters 18 (1984), 151-153.
  • $\begingroup$ have you seen the 2002 survey by Buhrman and de Wolf (homepages.cwi.nl/~rdewolf/publ/qc/dectree.ps)? it doesn't answer your question directly, but has more information on sensitivity of functions in general, and also for monotone graph properties. $\endgroup$ Aug 31, 2010 at 4:32
  • $\begingroup$ the encoding needs $(\binom{m}{2}+1)\log m$ bits $\endgroup$
    – didest
    Mar 5, 2012 at 11:50

1 Answer 1


The survey that Suresh pointed to brings up a paper by Wegener [1] that partially confirms the conjecture. It holds for all monotone graph properties and the inequality is tight (consider the property "Has no isolated vertices"). Any more recent results would be appreciated as well.

  1. Wegener, L. The critical complexity of all (monotone) Boolean functions and monotone graph properties. Information and Control, 67:212-222, 1985.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.