<p>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.</p>

<ol>
<li>Wegener, L. The critical complexity of all (monotone) Boolean functions and monotone graph properties. <i>Information and Control</i>, 67:212-222, 1985.</li>
</ol>

CC BY-SA 2.5
2010-08-31T06:37:27.000Z
2010-08-31T06:37:27.000Z
mhum
<p>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? </p>

<p><i>Background</i></p>

<p>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 <i>sensitivity of $f$ at $x$</i> as $s(f;x) := |\{i : f(x) \neq f(x^i) \}|$. Finally, define the <i>sensitivity</i> of $f$ as $s(f) := \mbox{max}_x\; s(f;x)$.</p>

<p>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 <i>qua</i> boolean function.</p>

<ol>
<li>Turan, G., The critical complexity of graph properties, <i>Information Processing Letters</i> 18 (1984), 151-153. </li>
</ol>

CC BY-SA 3.0
2012-03-05T11:50:56.763Z
the encoding needs $(\binom{m}{2}+1)\log m$ bits
didest
CC BY-SA 2.5
2010-08-31T04:32:59.330Z
have you seen the 2002 survey by Buhrman and de Wolf (http://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.
Suresh Venkat
<graph-theory><property-testing>
Sensitivity of Graph Properties
mhum
# Sensitivity of Graph Properties

(Asked by: username_0 on 2010-08-30)

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.

1. Turan, G., The critical complexity of graph properties, *Information Processing Letters* 18 (1984), 151-153.

**Tags:** graph-theory, property-testing
> **Comments:**
> **username_2**: have you seen the 2002 survey by Buhrman and de Wolf (http://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.  
> **username_1**: the encoding needs $(\binom{m}{2}+1)\log m$ bits  

---

## 1 answers

### Answer by username_0 on 2010-08-31. Score: 2

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.


---

