Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.
share|improve this question
    
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. –  Suresh Venkat Aug 31 '10 at 4:32
    
the encoding needs $(\binom{m}{2}+1)\log m$ bits –  Diego de Estrada Mar 5 '12 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.
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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