En matemáticas, la elección aleatoria dependiente es una técnica probabilística que muestra cómo encontrar un gran conjunto de vértices en un gráfico denso, de modo que cada pequeño subconjunto de vértices tiene muchos vecinos comunes. Es una herramienta útil para incrustar un gráfico en otro gráfico con muchos bordes. Por lo tanto, tiene su aplicación en la teoría de grafos extremos , la combinatoria aditiva y la teoría de Ramsey .
Dejar
,
y supongamos: [1] [2] [3] [4] [5]
![{\displaystyle n\alpha ^{t}-{n \choose r}\left({\frac {m}{n}}\right)^{t}\geq u.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Cada gráfico en
vértices con al menos
bordes contiene un subconjunto
de vértices con
tal que para todos
con
,
tiene al menos
vecinos comunes.
La idea básica es elegir el conjunto de vértices de forma aleatoria. Sin embargo, en lugar de elegir cada vértice uniformemente al azar, el procedimiento elige aleatoriamente una lista de
vértices primero y luego elige vecinos comunes como el conjunto de vértices. La esperanza es que de esta manera, el conjunto elegido tendría más probabilidades de tener más vecinos comunes.
Formalmente, deja
ser una lista de
vértices elegidos uniformemente al azar de
con reemplazo (permitiendo la repetición). Dejar
ser el vecindario común de
. El valor esperado de
es
![{\displaystyle {\begin{aligned}\mathbb {E} |A|&=\sum _{v\in V}\mathbb {P} (v\in A)=\sum _{v\in V}\mathbb {P} (T\subseteq N(v))=\sum _{v\in V}\left({\frac {d(v)}{n}}\right)^{t}\\&\geq n\left({\frac {1}{n}}\sum _{v\in V}{\frac {d(v)}{n}}\right)^{t}\quad {\text{(convexity)}}\\&\geq n\alpha ^{t}.\end{aligned}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Para cada
-subconjunto de elementos
de
,
contiene
si y solo si
está contenido en el vecindario común de
, que ocurre con probabilidad
Un
es malo si tiene menos de
vecinos comunes. Entonces para cada fijo
-subconjunto de elementos
de
, está contenido en
con probabilidad menor que
. Por tanto, por la linealidad de la expectativa, ![{\displaystyle \mathbb {E} [\#{\text{bad }}r{\text{-element subset of }}A]<{\binom {n}{r}}\left({\frac {m}{n}}\right)^{t}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Para eliminar subconjuntos defectuosos, el procedimiento consiste en excluir un elemento en cada subconjunto defectuoso. El número de elementos restantes es al menos
, cuyo valor esperado es al menos
En consecuencia, existe un
tal que hay al menos
elementos en
restante después de deshacerse de todo lo malo
-subconjuntos de elementos. El conjunto
del resto
elementos expresa las propiedades deseadas. Números de turán de un gráfico bipartito
DRC puede ayudar a encontrar el número de Turán . Usando los parámetros apropiados, si
es un grafo bipartito en el que todos los vértices en
tener un título como máximo
, luego el número extremo
dónde
solo depende de
. [1] [5]
Formalmente, si
y
es una constante suficientemente grande para que
Si
luego
![{\displaystyle n\alpha ^{t}-{\binom {n}{r}}\left({\frac {m}{n}}\right)^{t}=(2c)^{r}-{\binom {n}{r}}\left({\frac {a+b}{n}}\right)^{r}\geq (2c)^{r}-(a+b)^{r}\geq a=u,}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
y así se cumple el supuesto de elección aleatoria dependiente. Por lo tanto, para cada gráfico
con al menos
aristas, existe un subconjunto de vértices
de tamaño
satisfaciendo que cada
-subconjunto de
tiene al menos
vecinos comunes. Incrustando
dentro
por incrustación
dentro
arbitrariamente y luego incrustar los vértices en
uno por uno, luego para cada vértice
en
, tiene como máximo
vecinos en
, lo que demuestra que sus imágenes en
tener por lo menos
vecinos comunes. Por lo tanto
se puede incrustar en uno de los vecinos comunes evitando colisiones. Esto se puede generalizar para degenerar gráficos utilizando la variación de la elección aleatoria dependiente.
Incrustar una subdivisión en 1 de un gráfico completo
DRC se puede aplicar directamente para demostrar que si
es un gráfico en
vértices y
bordes, entonces
contiene una subdivisión en 1 de un gráfico completo con
vértices. Esto se puede mostrar de manera similar a la prueba anterior del límite en el número de Turán de un gráfico bipartito. [1]
De hecho, si establecemos
, tenemos (desde
)
![{\displaystyle n\alpha ^{t}-{\binom {n}{r}}\left({\frac {m}{n}}\right)^{t}\geq (2\epsilon )^{t}n-{\binom {n}{2}}\epsilon ^{3t}\geq n^{1/2}\geq a=u,}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
y así se mantiene la suposición de la RDC. Dado que una subdivisión en 1 del gráfico completo en
vértices es un gráfico bipartito con partes de tamaño
y
donde cada vértice en la segunda parte tiene grado dos, el argumento de incrustación en la prueba del límite en el número de Turán de un gráfico bipartito produce el resultado deseado. Una versión más fuerte encuentra dos subconjuntos de vértices
en un gráfico denso
de modo que cada pequeño subconjunto de vértices en
tiene muchos vecinos comunes en
.
Formalmente, deja
ser algunos enteros positivos con
, y deja
ser un número real. Suponga que se cumplen las siguientes restricciones:
![{\displaystyle {\begin{aligned}n\alpha ^{t}-{\binom {n}{q}}\left({\frac {m}{n}}\right)^{t}&\geq u\\{\binom {n}{r}}\left({\frac {m}{u}}\right)^{q-r}&<1.\end{aligned}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Entonces cada gráfico
en
vértices con al menos
bordes contiene dos subconjuntos
de vértices para que cualquier
vértices en
tener por lo menos
vecinos comunes en
. [1]Número extremo de un gráfico bipartito degenerado
Usando esta declaración más fuerte, uno puede limitar el número extremo de
-Gráfico bipartito degenerado: para cada
-Gráfico bipartito degenerado
con como máximo
vértices, el número extremo
es como mucho
[1]
Número de Ramsey de un gráfico bipartito degenerado
Esta declaración también se puede aplicar para obtener un límite superior del número de Ramsey de un gráfico bipartito degenerado. Si
es un entero fijo, entonces para cada bipartito
-Gráfico bipartito degenerado
en
vértices, el número de Ramsey
es de la orden
[1]