Loading [MathJax]/jax/output/HTML-CSS/jax.js
Saltar al contenido principal
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
LibreTexts Español

11.8: Ejercicios

( \newcommand{\kernel}{\mathrm{null}\,}\)

1. Considera una gráfica aleatoria con conjunto de vértices{1,2,;n}. Si la probabilidad de borde esp=1/2, entonces vamosX denotar el número de subgráficos completos de tamañot=2logn y dejarY denotar el número de conjuntos independientes de tamañot=2logn.

a. demostrar queE(X+Y)<1, cuandon es suficientemente grande.

b. Usar el resultado de la parte a para mostrar queω(G) es menor que2logn, mientras que el número cromático deG es al menosn/(2logn) (ambas declaraciones se mantienen con alta probabilidad). En consecuencia, la desigualdad básicaχ(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 distintoi,j con1i<jn, voltear una moneda justa. Si el resultado son cabezas, orienta el borde dei aj, que denotamos por(x,y). Si el lanzamiento es colas, entonces el borde se orienta dej ai, denotado(y,x). Mostrar que cuandon es grande, con alta probabilidad, la siguiente afirmación es verdadera: Por cada conjuntoS de tamañologn/10, hay un vértice parax que(x,y) enT para cadayS.

3. DejarT ser un torneo aleatorio sobren vértices. Mostrar que con alta probabilidad, la siguiente afirmación es verdadera: Por cada parx,y de vértices distintos, ya sea (1)(x,y) enT, o (2) hay un vérticez para el que ambos(x,z) y(z,y) están enT.

4. Muchas declaraciones para gráficas aleatorias exhiben un comportamiento umbral. Mostrar que una gráfica aleatoria con probabilidad de bordep=10logn/n casi con certeza no tiene vértices aislados, mientras que una gráfica aleatoria con probabilidad de bordep=logn/(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.


This page titled 11.8: Ejercicios is shared under a CC BY-SA 4.0 license and was authored, remixed, and/or curated by Mitchel T. Keller & William T. Trotter via source content that was edited to the style and standards of the LibreTexts platform.

Support Center

How can we help?