Quais parâmetros do gráfico NÃO estão concentrados em gráficos aleatórios?

É sabido que muitos parâmetros gráficos importantes mostram concentração (forte) em gráficos aleatórios, pelo menos em alguma faixa da probabilidade da aresta. Alguns exemplos típicos são: número cromático, clique máximo, conjunto independente máximo, correspondência máxima, número de domínio, número de cópias de um subgráfico fixo, diâmetro, grau máximo, número de escolha (número de coloração da lista), número de Lovasz , largura da árvore, etc.$\theta$

Pergunta: Quais são as exceções, isto é, parâmetros gráficos significativos que não estão concentrados em gráficos aleatórios?

Editar. Uma definição possível de concentração é esta:

Seja um parâmetro de gráfico em gráficos aleatórios n -vertex. Chamamos-lhe concentrada , se para cada ε > 0 , ele sustenta que lim n → ∞ Pr ( ( 1 - ε ) E ( X n ) ≤ X n ≤ ( 1 + ε ) E ( X n ) ) = 1. A concentração é forte$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.$$ , se a probabilidade se aproximar de 1 a uma taxa exponencial. Mas às vezes forte é usado em um sentido diferente, referindo-se ao fato de que a convergência permanece verdadeira com um intervalo de encolhimento, produzindo uma faixa possivelmente muito estreita. Por exemplo, se é o grau mínimo, em seguida, por alguma gama da probabilidade borda p , pode-se provar lim n → ∞ Pr ( ⌊ E ( X n ) ⌋ ≤ X n ≤ ⌈ E ( X n ) ⌉ ) = $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$$ qual é o intervalo mais curto possível (como o grau é inteiro, mas o valor esperado pode não ser).

$X_n=n$

Muitos parâmetros do maior componente conectado não estão concentrados para $G(n,p)$ E se $p=1/n$ e mais geralmente se $p$está na janela crítica. Exemplos são o diâmetro e o tamanho do maior componente, o tamanho do segundo maior componente, o número de folhas que o componente possui etc.

Veja por exemplo

Aldous, David. "Excursões brownianas, gráficos aleatórios críticos e o coalescente multiplicativo". The Annals of Probability (1997): 812-854.

Nachmias, Asaf e Yuval Peres. "Gráficos aleatórios críticos: diâmetro e tempo de mistura." Os Anais da Probabilidade 36, n. 4 (2008): 1267-1286.

Addario-Berry, Louigi, Nicolas Broutin e Christina Goldschmidt. "O limite contínuo de gráficos aleatórios críticos." Teoria da Probabilidade e Campos Relacionados 152, no. 3-4 (2012): 367-406.

A falta de concentração acontece em algumas contagens ($\#\mathsf{P}$) propriedades, e talvez para muitas delas.

Um exemplo simples é o número de subgráficos de abrangência ($2^m$) O número de arestas de um gráfico aleatório flutua em$\pm \Theta(n)$ portanto, o número de subgráficos de abrangência flutua por um fator de $2^{\Theta(n)}$bem longe do $(1+\epsilon)$ fator que você está usando em sua definição de concentração.

Para mostrar que este não é um exemplo isolado, aqui está um argumento (não totalmente rigoroso, mas possivelmente capaz de ser rigoroso) sobre por que a falta de concentração também deve ser verdadeira quanto ao número de ciclos hamiltonianos. O valor esperado desse número é claramente$(n-1)!/2^{n+1}$: cada um dos $(n-1)!/2$ seqüências cíclicas de vértices tem um $1/2^n$chance de realmente ser um ciclo hamiltoniano. Por um argumento semelhante, a quantidade esperada de alteração nesse número causada pela introdução de uma nova margem seria$(n-2)!/2^{n-1}$, menor por um fator linear. Se o número de ciclos hamiltonianos estivesse fortemente concentrado, a maioria dos flips de borda causaria uma quantidade de alteração nesse número que se aproxima do valor esperado. Mas então o$\Theta(n)$ a flutuação no número de arestas causaria uma flutuação no número de ciclos hamiltonianos proporcional ao valor esperado, contradizendo a hipótese de forte concentração.

Outros candidatos plausíveis à falta de concentração incluem o número de cores (partições dos vértices em conjuntos independentes), número de combinações ou combinações perfeitas ou número de árvores que medem.