Coincidencia con los bordes probabilísticos

Question

Consideremos dos conjuntos de $A,B$, cada una con $n$ vértices. Para cada par $(a,b)\in A\times B$, el borde entre el $a$ $b$ aparece con una probabilidad de $0.01$, independientemente de los bordes restantes. Es cierto que como $n\rightarrow\infty$, la probabilidad de que exista una coincidencia entre el $A$ $B$ enfoques $1$?

Creo que debe ser cierto, porque por un gran $n$ el número de opciones que cada vértice de $A$ $B$ crece. En particular, el número de opciones es aproximadamente el $0.01n$, y con alta probabilidad de que no está lejos de eso. Ayuntamiento de matrimonio teorema puede ser de ayuda, pero no estoy seguro de cómo.

Answer 1

Sin duda es cierto.

De hecho, creo que debe ser cierto si la probabilidad de $p$ de un borde, es decir $\frac{4\log n}{n}$. Erdos y Renyi probablemente resultó un umbral resultado perfecto matchings en general (es decir, no necesariamente bipartito) gráficos.

Ahora algunos justificación: voy a Salón de uso del teorema de e indicar por qué $|N(S)| \geq |S|$ es cierto para todos los conjuntos de $S \subset A$ con probabilidad tiende a 1.

Deje $S$ ser un conjunto fijo de tamaño $s$. Divida $B$ a $s$ grupos de igual tamaño. Fijar un orden en tanto $S$ y los conjuntos de $B$ y considerar un conjunto de $s$ perfecto matchings entre ellos (pairwise discontinuo). Para cada coincidencia, vamos a intentar buscar a un vecino de cualquier elemento de $S$ en el conjunto correspondiente de $B$. La probabilidad de que esto no puede ser hecho por cualquier coincidencia es en la mayoría de las $s^s(1-p)^{st}$ donde $t=\frac{n}{s}$. La probabilidad de que una mala $S$ existe en la mayoría de las ${(\frac{en}{s})}^{s}s^se^{-pn}$, que va a cero cuando se $s<< \frac{n}{\log n}$.

Si $n \leq 3s$, podemos ver que $N(S)=B$ con prob tendiendo a 1. Tenemos $ Pr[\exists S: |S|=s, N(S) \neq B] \leq {n \choose s}np^s \leq {(\dfrac{en}{s})}^sn(1-p)^s$; que va a cero desde $(1-p)^s$ domina a los otros términos.

[Continúa...]