¿Qué parámetros de gráfico NO se concentran en gráficos aleatorios?

Es bien sabido que muchos parámetros importantes del gráfico muestran una concentración (fuerte) en gráficos aleatorios, al menos en algún rango de la probabilidad de borde. Algunos ejemplos típicos son el número cromático, la camarilla máxima, el conjunto independiente máximo, la coincidencia máxima, el número de dominación, el número de copias de un subgrafo fijo, el diámetro, el grado máximo, el número de elección (número de coloración de la lista), número Lovasz , ancho del árbol etc. $\theta$

Pregunta: ¿Cuáles son las excepciones, es decir, los parámetros de gráficos significativos que no se concentran en gráficos aleatorios?

Editar. Una posible definición de concentración es esta:

Deje que sea un parámetro de gráfico en gráficos aleatorios de vértices. Lo llamamos concentrado , si por cada , mantiene que La concentración es fuerte , si la probabilidad se acerca a 1 a una tasa exponencial. Pero a veces fuerte se usa en un sentido diferente, refiriéndose al hecho de que la convergencia sigue siendo cierta con un intervalo de contracción, produciendo un rango posiblemente muy estrecho. Por ejemplo, si es el grado mínimo, entonces, para algún rango de la probabilidad de borde , se puede demostrar $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$ que es el intervalo más corto posible (como el grado es entero, pero el valor esperado puede no serlo).

Nota: Se pueden construir exenciones artificiales de la regla de concentración. Por ejemplo, deje , si el gráfico tiene un número impar de aristas, y 0 en caso contrario. Esto claramente no está concentrado, pero no lo consideraría un parámetro significativo . $X_n=n$

graph-theory pr.probability random-graphs Andras Farago
fuente

Indique la definición de concentración fuerte en gráficos aleatorios.

Mohammad Al-Turkistany

Probablemente la definición es "muy alta probabilidad (1-exp) de que el parámetro esté en un rango específico (pequeño)".

Suresh Venkat

@ MohammadAl-Turkistany Edité la pregunta para incluir una definición.

Andras Farago

¿Posiblemente propiedades binarias simples como conectividad? o tal vez la idea es excluir propiedades binarias? Creo que esto quizás necesite un mejor análisis del modelo de gráfico aleatorio. Para los gráficos erdos-renyi (¿no es eso lo que tienes en mente?), la conectividad en sí misma pasa por un fenómeno umbral.

vzn

H

$H$

H

$H$

$\#\mathsf{P}$

$2^m$ $\pm \Theta(n)$ $2^{\Theta(n)}$ $(1+\epsilon)$

$(n-1)!/2^{n+1}$ $(n-1)!/2$ $1/2^n$ $(n-2)!/2^{n-1}$ $\Theta(n)$

Otros posibles candidatos para la falta de concentración incluyen la cantidad de coloraciones (particiones de los vértices en conjuntos independientes), la cantidad de combinaciones o combinaciones perfectas, o la cantidad de árboles que se extienden.

David Eppstein
fuente

n

$n$

También sería interesante encontrar propiedades naturales que no estén concentradas, incluso en el modelo G (n, m) de gráficos aleatorios; los de esta respuesta funcionan solo para G (n, p).

David Eppstein

Las respuestas de "argumento de conteo" de David siempre son muy perspicaces para mí. : D

Daniel Apon

¿Qué parámetros de gráfico NO se concentran en gráficos aleatorios?

Respuestas: