elección aleatoria dependiente

En matemáticas, la selección aleatoria dependiente es una técnica probabilística que muestra cómo encontrar un conjunto grande de vértices en un grafo denso , de manera que cada subconjunto pequeño de vértices tenga muchos vecinos comunes. Es una herramienta útil para incrustar un grafo en otro con muchas aristas. Por lo tanto, tiene aplicaciones en la teoría extremal de grafos , la combinatoria aditiva y la teoría de Ramsey .

Dejar${\displaystyle u,n,r,m,t\in \mathbb {N} }$,${\displaystyle \alpha >0}$y supongamos: ^{[ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ]}$${\displaystyle n\alpha ^{t}-{n \choose r}\left({\frac {m}{n}}\right)^{t}\geq u.}$$Cada gráfico en${\displaystyle n}$vértices con al menos${\displaystyle {\frac {\alpha n^{2}}{2}}}$los bordes contienen un subconjunto${\displaystyle U}$de vértices con${\displaystyle |U|\geq u}$de tal manera que para todos${\displaystyle S\subset U}$con${\displaystyle |S|=r}$,${\displaystyle S}$tiene al menos${\displaystyle m}$vecinos comunes.

La idea básica es elegir el conjunto de vértices al azar. Sin embargo, en lugar de elegir cada vértice uniformemente al azar, el procedimiento elige aleatoriamente una lista de${\displaystyle t}$Primero se seleccionan los vértices y luego se eligen los vecinos comunes para conformar el conjunto de vértices. Se espera que, de esta manera, el conjunto elegido tenga mayor probabilidad de tener vecinos comunes.

Formalmente, dejemos${\displaystyle T}$ser una lista de${\displaystyle t}$vértices elegidos uniformemente al azar de${\displaystyle V(G)}$con reemplazo (permitiendo repetición). Deje${\displaystyle A}$ser el vecindario común de${\displaystyle T}$. El valor esperado de${\displaystyle |A|}$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{(convexidad)}}\\&\geq n\alpha ^{t}.\end{aligned}}}$$Por cada${\displaystyle r}$subconjunto de elementos${\displaystyle S}$de${\displaystyle V}$,${\displaystyle A}$contiene${\displaystyle S}$si y solo si${\displaystyle T}$está contenido en el vecindario común de${\displaystyle S}$, lo cual ocurre con probabilidad${\textstyle \left({\frac {\#{\text{vecinos comunes de }}S}{n}}\right)^{t}.}$ Un${\displaystyle S}$es malo si tiene menos de${\displaystyle m}$vecinos comunes. Luego, para cada fijo${\displaystyle r}$subconjunto de elementos${\displaystyle S}$de${\displaystyle V}$, está contenido en${\displaystyle A}$con probabilidad menor que${\displaystyle (m/n)^{t}}$Por lo tanto, debido a la linealidad de la esperanza,$${\displaystyle \mathbb {E} [\#{\text{subconjunto malo de r elementos de }}A]<{\binom {n}{r}}\left({\frac {m}{n}}\right)^{t}.}$$Para eliminar subconjuntos defectuosos, excluimos un elemento de cada subconjunto defectuoso. El número de elementos restantes es al menos${\displaystyle |A|-(\#{\text{bad }}r{\text{-element subset of }}A)}$, cuyo valor esperado es al menos${\textstyle n\alpha ^{t}-{\binom {n}{r}}\left({\frac {m}{n}}\right)^{t}\geq u.}$En consecuencia, existe una${\displaystyle T}$de tal manera que haya al menos${\displaystyle u}$elementos en${\displaystyle A}$lo que queda después de deshacerse de todo lo malo${\displaystyle r}$subconjuntos de elementos. El conjunto${\displaystyle U}$de los restantes${\displaystyle u}$Los elementos expresan las propiedades deseadas.

Una versión más robusta encuentra dos subconjuntos de vértices.${\displaystyle U_{1},U_{2}}$en un grafo denso${\displaystyle G}$de modo que cada pequeño subconjunto de vértices en${\displaystyle U_{i}}$tiene muchos vecinos en común en${\displaystyle U_{3-i}}$.

Formalmente, dejemos${\displaystyle u,n,r,m,t,q}$sean algunos enteros positivos con${\displaystyle q>r}$y dejar${\displaystyle \alpha >0}$Sea un número real . Supongamos 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}}}$$ Entonces cada gráfico${\displaystyle G}$en${\displaystyle n}$vértices con al menos${\displaystyle \alpha n^{2}/2}$Los bordes contienen dos subconjuntos${\displaystyle U_{1},U_{2}}$de vértices de modo que cualquier${\displaystyle r}$vértices en${\displaystyle U_{i}}$tener al menos${\displaystyle m}$vecinos comunes en${\displaystyle U_{3-i}}$. ^{[ 1 ]}

• Elección aleatoria dependiente - Matemáticas del MIT