Turan's conjecture on graph-property sensitivity
Turan's conjecture on graph-property sensitivity
Let be a non-trivial graph property for graphs with vertices, so that is a Boolean function of the possible edges. Turan's conjecture. The sensitivity satisfies
Turan had previously proved the lower bound ; 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
Sign in to submit a solution.
No solutions have been posted yet.