The min-term graph-property sensitivity conjecture
The min-term graph-property sensitivity conjecture
Let be a Boolean graph property on the possible edges. A min-term graph property is a graph property of the type defined in Chakraborty's work, and is non-trivial when it is not constant. Min-term sensitivity conjecture. The sensitivity satisfies
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
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.