Sensibilité des propriétés du graphique

Dans [1], Turan montre que la sensibilité (appelée "complexité critique" dans l'article) d'une propriété graphique est strictement supérieure à oùmest le nombre de sommets du graphe. Il continue en conjecturant que toute propriété de graphe non triviale a une sensibilité≥m-1. Il mentionne que cela a été vérifié pourm≤5. Des progrès ont-ils été réalisés sur cette conjecture?$\lfloor {1\over 4} m \rfloor$$m$$\geq m-1$$m \leq 5$

Contexte

Soit une chaîne binaire dans { 0 , 1 } n . Définissez x i pour 1 ≤ i ≤ n comme la chaîne obtenue à partir de x en inversant le bit i t h . Pour une fonction booléenne f : { 0 , 1 } n \ à { 0 , 1 } , définissez la sensibilité de f à x comme s ( f ; $x$$\{0,1\}^n$$x^i$$1 \leq i \leq n$$x$$i^{th}$$f: \{0,1\}^n$$\{0,1\}$$f$$x$. Enfin, définissez lasensibilitéde f comme s ( f ) : = max$s(f;x) := |\{i : f(x) \neq f(x^i) \}|$$f$ .$s(f) := \mbox{max}_x\; s(f;x)$

Une propriété graphique est une collection Graphes telle que si G ∈ P et G ' est isomorphe à G alors G ' ∈ P . On peut penser à une propriété de graphe P comme l'union des propriétés P m où P m est le sous-ensemble de P composé de graphes à m sommets. De plus, nous pouvons concevoir une propriété de graphe P m comme une fonction booléenne sur { 0 , 1 } n où 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$ . On peut encoder un graphe surmsommets dans un vecteur binaire de longueurn; chaque entrée dans le vecteur correspond à une paire de sommets et l'entrée est1si ce bord est présent dans le graphique. Ainsi, la sensibilité d'une propriété graphique est sa sensibilitétantfonction booléenne.$n = {m \choose 2}$$m$$n$$1$

1. Turan, G., La complexité critique des propriétés des graphes, Information Processing Letters 18 (1984), 151-153.

L'enquête que Suresh a pointée fait apparaître un article de Wegener [1] qui confirme partiellement la conjecture. Il est valable pour toutes les propriétés de graphe monotone et l'inégalité est étroite (considérons la propriété "N'a pas de sommets isolés"). Tout résultat plus récent serait également apprécié.

1. Wegener, L. La complexité critique de toutes les fonctions booléennes (monotones) et les propriétés des graphes monotones. Information and Control , 67: 212-222, 1985.