11.8: Ejercicios

1. Considera una gráfica aleatoria con conjunto de vértices$\{1,2,;n\}$. Si la probabilidad de borde es$p=1/2$, entonces vamos$X$ denotar el número de subgráficos completos de tamaño$t=2 \log ⁡n$ y dejar$Y$ denotar el número de conjuntos independientes de tamaño$t=2 \log ⁡n$.

a. demostrar que$E(X+Y)<1$, cuando$n$ es suficientemente grande.

b. Usar el resultado de la parte a para mostrar que$ω(G)$ es menor que$2 \log ⁡n$, mientras que el número cromático de$G$ es al menos$n/(2 \log ⁡n)$ (ambas declaraciones se mantienen con alta probabilidad). En consecuencia, la desigualdad básica$\chi(G)≥ω(G)$ está lejos de ser ajustada para una gráfica aleatoria.

2. Formamos un torneo aleatorio de la siguiente manera. Comience con una gráfica completa con conjunto de vértices$\{1,2,…,n\}$. Por cada par distinto$i, j$ con$1≤i<j≤n$, voltear una moneda justa. Si el resultado son cabezas, orienta el borde de$i$ a$j$, que denotamos por$(x,y)$. Si el lanzamiento es colas, entonces el borde se orienta de$j$ a$i$, denotado$(y,x)$. Mostrar que cuando$n$ es grande, con alta probabilidad, la siguiente afirmación es verdadera: Por cada conjunto$S$ de tamaño$\log ⁡n/10$, hay un vértice para$x$ que$(x,y)$ en$T$ para cada$y \in S$.

3. Dejar$T$ ser un torneo aleatorio sobre$n$ vértices. Mostrar que con alta probabilidad, la siguiente afirmación es verdadera: Por cada par$x, y$ de vértices distintos, ya sea (1)$(x,y)$ en$T$, o (2) hay un vértice$z$ para el que ambos$(x,z)$ y$(z,y)$ están en$T$.

4. Muchas declaraciones para gráficas aleatorias exhiben un comportamiento umbral. Mostrar que una gráfica aleatoria con probabilidad de borde$p=10 \log⁡ n/n$ casi con certeza no tiene vértices aislados, mientras que una gráfica aleatoria con probabilidad de borde$p= \log ⁡n/(10n)$ casi con certeza tiene al menos un vértice aislado.

5. En el sentido del problema anterior, determinar la probabilidad umbral para que se conecte una gráfica.