11.8: Ejercicios

Última actualización
Guardar como PDF

Page ID: 118378

Mitchel T. Keller & William T. Trotter
Georgia Tech & Morningside College

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

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.