Turan's conjecture on graph-property sensitivity

Let ff be a non-trivial graph property for graphs with nn vertices, so that ff is a Boolean function of the (n2){n \choose 2} possible edges. Turan's conjecture. The sensitivity satisfies

s(f)n1.s(f)\geq n-1.

Turan had previously proved the lower bound s(f)n/4s(f)\geq \lfloor n/4\rfloor; the conjecture remains unresolved more than thirty years after it was formulated.

Sources & referencesView supporting material

Primary source

Ilan Karpas, “Lower bounds for sensitivity of graph properties”, arXiv:1609.05320 (2016).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.