Los subconjuntos aleatorios de 3 elementos de [n]

Question

Se me asignan$2n$ subconjuntos de 3 elementos de$\{1,2,...,n\}$ que fueron elegidos de manera uniforme e independiente al azar (de todos los posibles subconjuntos de 3 elementos). ¿Cómo puedo probar que con probabilidad$\geq 1-e^{-\Theta(n)}$ se pueden seleccionar$n$ subconjuntos del total$2n$, de forma que ningún elemento de$\{1,2,...,n\}$ aparezca en más de 40 subconjuntos?

Estoy bastante seguro de que un Chernoff límite debe ser utilizado aquí, pero no podía deshacerse de la dependencia entre las variables aleatorias ...

Algunas ideas..?

Answer 1

Poissonization podría ser el camino.

En lugar de elegir exactamente $2n$ trillizos, dibujar uniformemente al azar $X_n$ trillizos, donde $X_n$ ha Poisson $cn$ distribución. Aquí y más adelante, escribir whp para con alta probabilidad en el sentido de que la probabilidad de que el evento es $\ge1-2^{-\Theta(n)}$. Por ejemplo, $X_n\ge2n$ whp si $c>2$, por lo tanto, si podemos seleccionar $n$ trillizos entre estos $X_n$ de tal manera que ningún vértice pertenece a más de $k=40$ de ellos, hemos terminado.

Para cada triplete $t$, vamos a $T_n(t)$ denotar el número de veces que $t$ fue el elegido. Para cada vértice $i$, vamos a $T_n(i)$ denotar la suma de $T_n(t)$ sobre los trillizos $t$ tal que $i\in t$, por lo tanto $T_n(i)$ es el número de tripletes $i$ pertenece.

Condicionalmente en $X_n$, $T_n(t)$ es binomial $(X_n,1/b_n)$ $b_n={n\choose 3}$ por lo tanto, incondicionalmente, el $(T_n(t))_t$ son yo.yo.d. variables aleatorias con distribución de Poisson $cn/b_n\approx6c/n^2$ distribución. Cada una de las $T_n(i)$ es la suma de ${n-1\choose 2}$ i.yo.d. $T_n(t)$ por lo tanto $T_n(i)$ es de Poisson con parámetro de ${n-1\choose 2}cn/b_n=3c$.

Tal vez usted puede continuar a partir de aquí.