Чувствительность свойств графика

В [1] Turan показывает, что чувствительность (называемая в статье «критической сложностью») свойства графа строго больше, чем гдеm- количество вершин в графе. Он продолжает предполагать, что любое нетривиальное свойство графа имеет чувствительность≥m-1. Он упоминает, что это было проверено дляm≤5. Был ли достигнут какой-либо прогресс в этой гипотезе?$\lfloor {1\over 4} m \rfloor$$m$$\geq m-1$$m \leq 5$

Фон

Пусть - двоичная строка в { 0 , 1 } n . Определите x i для 1 ≤ i ≤ n как строку, полученную из x путем переключения бита i t h . Для булевой функции f : { 0 , 1 } n \ to { 0 , 1 } определите чувствительность f в точке x как s ( f ; $x$$\{0,1\}^n$$x^i$$1 \leq i \leq n$$x$$i^{th}$$f: \{0,1\}^n$$\{0,1\}$$f$$x$, И, наконец, определитьчувствительностьиз F как S ( ф ) : = макс$s(f;x) := |\{i : f(x) \neq f(x^i) \}|$$f$ .$s(f) := \mbox{max}_x\; s(f;x)$

Граф свойство представляет собой набор графиков , такие , что если G ∈ P и G ' изоморфна G то G ' ∈ P . Мы можем рассматривать свойство графа P как объединение свойств P m, где P m - это подмножество P, состоящее из графов с m вершинами. Кроме того, мы можем представить свойство графа P m как булеву функцию на { 0 , 1 } n, где n $\mathcal P$$G \in \mathcal P$$G'$$G$$G' \in \mathcal P$$\mathcal P$$\mathcal P_m$$\mathcal P_m$$\mathcal P$$m$$\mathcal P_m$$\{0,1\}^n$ . Мы можем закодировать граф наmвершинах в двоичном векторе длиныn; каждая запись в векторе соответствует паре вершин, и эта запись равна1,если ребро присутствует в графе. Таким образом, чувствительность свойства графа является его чувствительностьусловиембулевой функции.$n = {m \choose 2}$$m$$n$$1$

1. Туран, Г., Критическая сложность свойств графов, Письма обработки информации 18 (1984), 151-153.

Обзор, на который указал Суреш, приводит статью Вегенера [1], которая частично подтверждает гипотезу. Он выполняется для всех свойств монотонного графа, и неравенство является жестким (рассмотрим свойство «Не имеет изолированных вершин»). Любые более свежие результаты также будут оценены.

1. Вегенер Л. Критическая сложность всех (монотонных) булевых функций и свойства монотонных графов. Информация и контроль , 67: 212-222, 1985.