The min-term graph-property sensitivity conjecture

Let ff be a Boolean graph property on the (n2){n \choose 2} possible edges. A min-term graph property is a graph property of the type defined in Chakraborty's work, and ff is non-trivial when it is not constant. Min-term sensitivity conjecture. The sensitivity satisfies

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

This is proposed in the source as a weaker form of Turan's conjecture, restricted to non-trivial min-term graph properties; its status is not otherwise resolved in the supplied text.

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.