Sensibilidade das propriedades do gráfico

Em [1], Turan mostra que a sensibilidade (chamada "complexidade crítica" no artigo) de uma propriedade de gráfico é estritamente maior que ondemé o número de vértices no gráfico. Ele continua conjecturando que qualquer propriedade não-trivial do gráfico tenha sensibilidade≥m-1. Ele menciona que isso foi verificado param≤5. Houve algum progresso nessa conjectura?$\lfloor {1\over 4} m \rfloor$$m$$\geq m-1$$m \leq 5$

fundo

Seja uma string binária em { 0 , 1 } n . Defina x i para 1 ≤ i ≤ n como a sequência obtida de x ao inverter o bit i t h . Para uma função booleana f : { 0 , 1 } n \ a { 0 , 1 } , defina a sensibilidade de f em x como s ( f ; $x$$\{0,1\}^n$$x^i$$1 \leq i \leq n$$x$$i^{th}$$f: \{0,1\}^n$$\{0,1\}$$f$$x$. Finalmente, defina asensibilidadede f como s ( f ) : = max$s(f;x) := |\{i : f(x) \neq f(x^i) \}|$$f$ .$s(f) := \mbox{max}_x\; s(f;x)$

Uma propriedade gráfico é um conjunto de gráficos de tal modo que, se L ∈ P e L ' é isomorfa a L então L ' ∈ P . Podemos pensar em uma propriedade de gráfico P como a união de propriedades P m onde P m é o subconjunto de P que consiste em gráficos com m vértices. Além disso, pode-se conceber uma propriedade gráfico P m como uma função booleana em { 0 , 1 } n onde 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$ . Podemos codificar um gráfico emmvértices em um vetor binário de comprimenton; cada entrada no vetor corresponde a um par de vértices e a entrada é1se a borda estiver presente no gráfico. Assim, a sensibilidade de uma propriedade gráfico é a sua sensibilidadequafunção booleano.$n = {m \choose 2}$$m$$n$$1$

1. Turan, G., A complexidade crítica das propriedades do gráfico, Information Processing Letters 18 (1984), 151-153.

A pesquisa que Suresh apontou traz um artigo de Wegener [1] que confirma parcialmente a conjectura. Ele é válido para todas as propriedades de gráfico monótono e a desigualdade é pequena (considere a propriedade "Não possui vértices isolados"). Qualquer resultado mais recente também seria apreciado.

1. Wegener, L. A complexidade crítica de todas as funções booleanas (monótonas) e propriedades de gráficos monótonas. Information and Control , 67: 212-222, 1985.