Quels paramètres de graphique ne sont PAS concentrés sur des graphiques aléatoires?

Il est bien connu que de nombreux paramètres de graphique importants montrent une concentration (forte) sur des graphiques aléatoires, au moins dans une certaine plage de probabilité de bord. Quelques exemples typiques sont le nombre chromatique, la clique maximale, l'ensemble indépendant maximal, la correspondance maximale, le numéro de domination, le nombre de copies d'un sous-graphique fixe, le diamètre, le degré maximal, le numéro de choix (numéro de coloration de la liste), le numéro Lovasz $\theta$ , la largeur de l'arbre, etc.

Question: Quelles sont les exceptions, c'est-à-dire les paramètres de graphique significatifs qui ne sont pas concentrés sur des graphiques aléatoires?

Modifier. Une définition possible de la concentration est la suivante:

$X_n$ $n$ $\epsilon>0$

lim_{n \to \infty} Pr ((1 - ϵ) E (X_{n}) \leq X_{n} \leq (1 + ϵ) E (X_{n})) = 1.

$\lim_{n\rightarrow\infty}\Pr\big((1-\epsilon)E(X_n)\leq X_n \leq (1+\epsilon)E(X_n)\big)=1.$

X_{n}

$X_n$

p

$p$

lim_{n \to \infty} Pr (⌊ E (X_{n}) ⌋ \leq X_{n} \leq ⌈ E (X_{n}) ⌉) = 1

$\lim_{n\rightarrow\infty}\Pr\big(\lfloor E(X_n)\rfloor\leq X_n \leq \lceil E(X_n)\rceil\big)=1$ qui est l'intervalle le plus court possible (car le degré est un entier, mais la valeur attendue peut ne pas l'être).

Remarque: On peut construire des exemptions artificielles de la règle de concentration. Par exemple, supposons , si le graphique a un nombre impair d'arêtes, et 0 sinon. Ce n'est clairement pas concentré, mais je ne le considérerais pas comme un paramètre significatif . $X_n=n$

graph-theory pr.probability random-graphs Andras Farago
la source

Veuillez donner la définition d'une forte concentration sur des graphiques aléatoires.

Mohammad Al-Turkistany

La définition est probablement "probabilité très élevée (1-exp) que le paramètre est dans une plage (petite) spécifique".

Suresh Venkat

@ MohammadAl-Turkistany J'ai modifié la question pour inclure une définition.

Andras Farago

possiblement des propriétés binaires simples comme la connectivité? ou peut-être l'idée est d'exclure les propriétés binaires? pense que cela nécessite peut-être une meilleure analyse du modèle de graphique aléatoire. pour les graphes erdos-renyi (n'est-ce pas ce que vous avez en tête?), la connectivité elle-même passe par un phénomène de seuil.

vzn

La concentration ne doit-elle se produire que dans l'attente? Je pense que le nombre de copies d'un sous-graphique fixe

est concentré, mais pas autour de l'attente à moins que

ne soit équilibré.

H

$H$

H

$H$

Aravind

Réponses:

De nombreux paramètres de la plus grande composante connectée ne sont pas concentrés pour $G(n,p)$ si $p=1/n$ et plus généralement si $p$ est dans la fenêtre critique. Des exemples sont le diamètre et la taille du plus grand composant, la taille du deuxième plus grand composant, le nombre de feuilles du composant, etc.

Voir par exemple

Aldous, David. "Excursions browniennes, graphes aléatoires critiques et coalescent multiplicatif." The Annals of Probability (1997): 812-854.

Nachmias, Asaf et Yuval Peres. "Graphiques aléatoires critiques: diamètre et temps de mélange." Les Annales de Probabilité 36, no. 4 (2008): 1267-1286.

Addario-Berry, Louigi, Nicolas Broutin et Christina Goldschmidt. "La limite du continuum des graphes aléatoires critiques." Théorie des probabilités et domaines connexes 152, no. 3-4 (2012): 367-406.

Yuval Peres
la source

Le défaut de concentration se produit pour certaines propriétés de comptage ( ), et peut-être pour beaucoup d'entre elles. $\#\mathsf{P}$

Un exemple simple est le nombre de sous-graphiques couvrant ( ). Le nombre d'arêtes d'un graphe aléatoire fluctue de sorte que le nombre de sous-graphes s'étendant varie d'un facteur de , bien loin du facteur vous utilisez dans votre définition de la concentration . $2^m$ $\pm \Theta(n)$ $2^{\Theta(n)}$ $(1+\epsilon)$

Pour montrer que ce n'est pas un exemple isolé, voici un argument (pas entièrement rigoureux mais pouvant être rendu rigoureux) pour expliquer pourquoi le manque de concentration devrait également être vrai du nombre de cycles hamiltoniens. La valeur attendue de ce nombre est clairement : chacun des séquences cycliques de sommets a un chances d'être en fait un cycle hamiltonien. Par un argument similaire, la quantité attendue de changement à ce nombre causée par l'introduction d'un nouveau bord serait $(n-1)!/2^{n+1}$ $(n-1)!/2$ $1/2^n$ , plus petit d'un facteur linéaire. Si le nombre de cycles hamiltoniens était fortement concentré, la plupart des flips de bord entraîneraient une variation de ce nombre proche de sa valeur attendue. Mais alors lafluctuation du nombre d'arêtes entraînerait une fluctuation du nombre de cycles hamiltoniens proportionnelle à sa valeur attendue, contredisant l'hypothèse d'une forte concentration. $(n-2)!/2^{n-1}$ $\Theta(n)$

D'autres candidats plausibles pour l'échec de la concentration comprennent le nombre de colorations (partitions des sommets en ensembles indépendants), le nombre de correspondances ou de correspondances parfaites, ou le nombre d'arbres couvrant.

David Eppstein
la source

Ce sont en effet des exemples intéressants. Apparemment, ils nécessitent tous des paramètres qui peuvent être exponentiellement grands en

. Je me demande s'il y a un paramètre significatif non concentrant parmi ceux qui sont délimités par un polynôme de la taille du graphique?

n

$n$

Andras Farago

Il serait également intéressant de trouver des propriétés naturelles non concentrées même dans le modèle G (n, m) des graphes aléatoires; ceux de cette réponse ne fonctionnent que pour G (n, p).

David Eppstein

Les réponses de «l'argument de comptage» de David sont toujours si perspicaces pour moi. : D

Daniel Apon