Które parametry wykresu NIE są skoncentrowane na losowych wykresach?

Dobrze wiadomo, że wiele ważnych parametrów wykresu pokazuje (silne) stężenie na losowych wykresach, przynajmniej w pewnym zakresie prawdopodobieństwa krawędzi. Niektóre typowe przykłady to liczba chromatyczna, maksymalna klika, maksymalna niezależny zestaw maksymalne dopasowanie, numer dominacja, liczba kopii stałe podgrafu, średnicy, maksymalny stopień, numer Choice (lista kolorowania numer), Lovász $\theta$ -liczba, szerokość drzewo, itp.

Pytanie: Jakie są wyjątki, to znaczy znaczące parametry wykresu, które nie są skoncentrowane na losowych wykresach?

Edytować. Możliwa definicja koncentracji jest następująca:

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

$$\lim_{n\rightarrow\infty}\Pr\big((1-\epsilon)E(X_n)\leq X_n \leq (1+\epsilon)E(X_n)\big)=1.$$ $X_n$lim n → ∞ Pr ( ⌊ E ( X n ) ⌋ ≤ X n ≤ ⌈ E ( X n ) ⌉ ) = $p$ $$\lim_{n\rightarrow\infty}\Pr\big(\lfloor E(X_n)\rfloor\leq X_n \leq \lceil E(X_n)\rceil\big)=1$$ który jest najkrótszym możliwym przedziałem (ponieważ stopień jest liczbą całkowitą, ale oczekiwana wartość może nie być).

Uwaga: Można skonstruować sztuczne wyłączenia z reguły koncentracji. Na przykład, niech $X_n=n$ , jeśli wykres ma nieparzystą liczbę krawędzi, a 0 w przeciwnym razie. To wyraźnie nie jest skoncentrowane, ale nie uważałbym tego za znaczący parametr.

Wiele parametrów największego połączonego komponentu nie jest skoncentrowanych dla jeśli a bardziej ogólnie, jeśli jest w oknie krytycznym. Przykładami są średnica i rozmiar największego komponentu, rozmiar drugiego co do wielkości komponentu, liczba liści komponentu itp.$G(n,p)$$p=1/n$$p$

Zobacz np

Aldous, David. „Wycieczki Browna, krytyczne losowe wykresy i multiplikatywna koalescencja”. The Annals of Prawdopodobieństwo (1997): 812-854.

Nachmias, Asaf i Yuval Peres. „Krytyczne losowe wykresy: średnica i czas mieszania”. The Annals of Probability 36, no. 4 (2008): 1267–1286.

Addario-Berry, Louigi, Nicolas Broutin i Christina Goldschmidt. „Limit ciągłości krytycznych losowych wykresów”. Teoria prawdopodobieństwa i pola pokrewne 152, no. 3-4 (2012): 367-406.

Brak koncentracji zdarza się w przypadku niektórych właściwości liczenia ( ), a może w przypadku wielu z nich.$\#\mathsf{P}$

Prostym przykładem jest liczba obejmujących podgrupy ( ). Liczba krawędzi losowego wykresu zmienia się o więc liczba obejmujących podgrupy zmienia się o współczynnik , z dala od współczynnika używają w twojej definicji koncentracji. ± Θ ( n ) 2 Θ ( n ) ( 1 + ϵ $2^m$$\pm \Theta(n)$$2^{\Theta(n)}$$(1+\epsilon)$

Aby pokazać, że nie jest to izolowany przykład, oto argument (nie do końca rygorystyczny, ale być może dający się rygorystycznie), dlaczego brak koncentracji powinien być również prawdziwy w odniesieniu do liczby cykli hamiltonowskich. Oczekiwana wartość tej ilości jest wyraźnie : Każdy z cyklicznych sekwencji wierzchołków ma szansę faktycznie będąc Cykl hamiltonowski. Podobnym argumentem oczekiwana wielkość zmiany tej liczby spowodowana wprowadzeniem nowej krawędzi byłaby , mniejsza o współczynnik liniowy. Gdyby liczba cykli hamiltonowskich była silnie skoncentrowana, większość przewrotów krawędzi powodowałaby zmianę tej liczby, która jest bliska jego oczekiwanej wartości. Ale potem ( n - 1 ) ! / 2 1 / 2 n ( n - 2 ) ! / 2 n - 1 Θ ( n $(n-1)!/2^{n+1}$$(n-1)!/2$$1/2^n$$(n-2)!/2^{n-1}$$\Theta(n)$ fluktuacja liczby krawędzi spowodowałaby fluktuację liczby cykli hamiltonowskich, która jest proporcjonalna do jej oczekiwanej wartości, co jest sprzeczne z założeniem silnej koncentracji.

Innymi prawdopodobnymi kandydatami do braku koncentracji są liczba zabarwień (podział wierzchołków na niezależne zestawy), liczba dopasowań lub idealnych dopasowań lub liczba drzew spinających.