En 1990 la gente, cada uno está conectado a al menos 1327 a los demás, entonces no es un totalmente conectado 4-grupo de personas

Question

Hemos 1990 gente y cada uno es "conectado" al menos 1327 otros. Mostrar que hay un grupo de 4 personas, donde cada uno es "conectado" a todas las demás personas de ese grupo.

Podríamos modelo de la relación "conectado" como un grafo, donde cada nodo es una persona (por lo $n=1990$$G(V,E)$) y dos personas $u,v$ están conectados iff $u,v\in E$. Luego de la declaración del problema, $δ(G)\geq 1327$ e lo $m\geq 1327$. Tenemos que mostrar que $G(V,E)$ tiene el grafo completo $K_4$ como un subgrafo, es decir,$K_4\subset G$. Pero estoy atascado aquí. Cualquier ayuda para avanzar en mi solución?

Answer 1

Cada persona está conectado a al menos 1327 de la otra de 1989 a la gente. Por lo que cada persona es disconectado desde en la mayoría de las $1989-1327=662$ de los otros. Escoge a una persona de manera arbitraria, y le llaman de Una persona; será el primero de los cuatro mutuamente conectados a la gente que me voy a encontrar. Toda la gente que desconecta de puede ser enviado lejos, ya que no puede estar entre los cuatro. Las personas que permanecen son Una y la 1327 o más personas se conecta.

Escoge arbitrariamente uno de los 1327 personas, y llamar a su persona B; ella va a ser el segundo de los cuatro mutuamente conectados a la gente que me voy a encontrar. Todas las personas que está desconectado de puede ser enviado lejos, ya que no puede estar entre los cuatro. Le acabo de enviar lejos a la mayoría de 662 personas. Las personas que permanecen son a, B, y, al menos, $1327-1-662=664$ otros. (La resta $1$ es B; la resta 662 son los que nos acaba de enviar).

Escoge arbitrariamente uno de los 664 o más que otros, y le llaman de la persona C; él va a ser el tercero de los cuatro mutuamente conectados a la gente que me voy a encontrar. Toda la gente que desconecta de puede ser enviado lejos, ya que no puede estar entre los cuatro. De 664 personas (distinto de a y B) que se mantuvo al final del paso anterior, uno se ha cambiado el nombre de C, y en la mayoría de los 662 otros, han sido enviados. Así que a menos que uno se queda. Llame a su D.

A continuación, a, B, C, y D son todos conectados. Prueba: Si dos de ellos se han desconectado, la última de las dos (en orden alfabético) habría sido enviado inmediatamente después de la primera de las dos fue el elegido.

Answer 2

En primer lugar usted puede demostrar que no es un clique de tamaño 3 - un conjunto de 3 personas, cada uno de los cuales está conectado a los otros dos. Tomar un par de personas que están conectadas. Cada uno está conectado a al menos 1326 otros. $1326 + 1326 = 2652 > 1988$ , por lo que estas dos personas deben tener al menos una conexión en común.

Una vez que usted sabe que hay un clique de tamaño 3 se puede extender el mismo argumento para mostrar que hay un clique de tamaño 4, como sigue:

(1) Considerar cualquier par en el tamaño 3 camarilla. Cómo es que muchas de las conexiones que la pareja debe compartir fuera de la camarilla.

(2) Considerar todas las 3 parejas en el tamaño 3 camarilla. Muestran que el 3 pares debe tener al menos una conexión compartida en común. Agregar esta conexión para el tamaño de 3 camarilla y tiene un tamaño de 4 camarilla.

Answer 3

Yo supuse que como cada par de tamaño 3 camarilla conecta con 664 otros vértices, y si nos excepto v1,v2,v3 hay 663 otros vértices que puede concluir en un tamaño de 4 camarilla. (Hay 1990 nodos, 1987 si ponemos v1,v2,v3, y 3*663=1989. Por lo tanto, al menos dos pares de la talla 3 camarilla tiene un nodo común)