Mientras estudio el teorema de Turan, me gustaría preguntar sobre algunas partes de esta demostración. Soy débil en probabilidad, así que a menos que me extienda y abra todo y lo formalice, no sería capaz de entenderlo. He revisado algunos posts en MSE también pero o bien preguntaban cosas diferentes o simplemente no pude entenderlos.
Quiero saber por qué cada gráfico $G$ de $n$ vértices tiene una camarilla de tamaño $\geq \sum_{v\in V(G)}\frac{1}{n-d(v)}$ . Esto es lo que he entendido hasta ahora:
En algunas notas que he comprobado, empiezan considerando una permutación aleatoria $p$ en $V=V(G)$ y consideremos el conjunto $Q_p$ que es el conjunto de vértices adyacentes a todos los vértices situados a su izquierda en $p$ . Ya veo por qué es una camarilla. A continuación, consideremos la variable aleatoria $X=|Q_p|$ . He aquí mi confusión: (Pregunta 1) ¿Significa esto que el espacio muestral es $S=\{Q_p\mid p \text{ is an permutation of }V\}$ o simplemente $S=\{p\mid p \text{ is a permutation of }V\}$ ?
A partir de esa definición de $X$ Pensé que sólo podía referirse al primer espacio de muestra, pero ahora supongo que se trata del segundo. Eso significa que la variable aleatoria $X$ asigna cualquier $p$ a $|Q_p|$ ¿tengo razón?
Y así, si $v$ es un vértice cualquiera, consideremos la variable aleatoria $X_v$ definida de forma que $X_v(p)=1$ si $v\in Q_p$ y $0$ de lo contrario. Entonces, $X=\sum_{v\in V(G)}X_v$ . (Pregunta 2: Si utilizo la primera $S$ y luego definir $X_v(Q_p)$ de la misma manera, entonces esta suma sigue siendo válida (sea útil o no), ¿verdad?).
A partir de aquí, simplemente necesito utilizar la linealidad de la expectativa, pero necesito la cantidad $E[X_v]=P(X_v=1)$ . Para conseguirlo, intento contarlo todo, lo que es
$$P(X_v=1)=P(\{p\mid X_v(p)=1\})=\frac{|\{p\mid X_v(p)=1\}|}{n!}.$$
El numerador es igual al número de $p$ tal que $v\in Q_p$ o eqv tal que $v$ aparece antes que cualquiera de sus no vecinos (hay $n-d(v)-1$ de ellos sin $v$ mismo). Para contar esto, primero ponemos $v$ y todos los no vecinos de $v$ en el $n$ cajas (realizado en $\binom{n}{n-d(v)}$ formas), permutarlas excepto $v$ ya que tiene que aparecer en primer lugar (hecho en $(n-d(v)-1)!$ formas), y permutar el resto en $d(v)!$ maneras. Así,
$$P(X_v=1)=\frac{\binom{n}{n-d(v)}(n-d(v)-1)!d(v)!}{n!}=\frac{\frac{1}{(n-d(v))!}(n-d(v)-1)!}{1}=\frac{1}{n-d(v)}.$$
Y hemos terminado. ¿Es esto correcto? Si utilizo en su lugar el primer espacio muestral, ¿se puede obtener también este resultado? Tengo problemas para contar $Q_p$ si utilizo la primera $S$ .
Por último, sin contar todo, ¿hay alguna otra forma de obtener el $\frac{1}{n-d(v)}$ ¿Más rápido? Gracias.
EDIT: El resto se deduce del método del primer momento.
