Teorema de Ramsey dice que el número más pequeño $n$ de manera tal que en $n$-vértice camarilla siempre hay 3 personas que se conocen o 5 personas que no se conocían entre sí es igual a $14$. He visto pruebas de $R(3, 5) = 14$, pero que le estaban dando a algunos de superior/inferior de límites en $R(3, 5)$ basado en los valores de algunos otros $R(a, b)$. Estoy interesado en cómo demostrar que $14$-vértice de la camarilla es de hecho un gráfico donde 3 personas se conocen o 5 personas que no saben el uno del otro.
Respuesta
¿Demasiados anuncios?
runeh
Puntos
1304
Creo que usted tiene que construir un poco, porque de lo contrario se pierde la pista de lo que está pasando.
Entre cualquiera de las seis personas hay tres que se conocen o tres que son mutuos extranjeros. Podemos ver esto mediante la adopción de un individuo y el examen de que él (o ella) sabe - hay otras cinco personas, y si él sabe más de la mitad, él sabe que al menos tres. Si cualquier par de estos conocernos tenemos tres amigos comunes (la persona original, además de los dos que se conocen). Si ninguno de los tres se conocen son tres mutuo extraños. El argumento a la inversa funciona si la primera persona que sabe menos de la mitad de la de los demás.
Ahora nos muestran que entre cualquiera a nueve personas hay tres amigos comunes o cuatro mutuo extraños. Tomar una de las personas. Si él no sabe hasta seis de los demás, entre los que seis son tres amigos comunes (que se hacen) o tres mutuo extraños, a los que podemos añadir a la primera persona para hacer cuatro. Si una persona sabe como a muchos como a otros cuatro, y después un par de estos se conocen entre sí y tenemos tres conocidos con la primera persona, o sin pareja hace, y los cuatro son mutuos extranjeros.
Así que el único caso de que no hemos cubierto es si ninguno de los nueve saber más de tres personas y ninguno es un extraño para más de cinco así que cada uno debe saber exactamente tres. Sin embargo, estas relaciones son mutuos, y vienen en pares, mientras que $9\times 3$ es impar. Así que debe haber al menos una persona que sabe más de tres o es un extraño para más de cinco, y el caso no puede surgir.
A continuación, se consideran $14$ de la gente. Supongamos que la persona a $1$ sabe como a muchos como a otros cinco. Entonces, si cualquier par de estos se conocen, hay tres amigos comunes, y si no lo hacen hay cinco mutuo extraños. Así, esta persona debe saber que la mayoría de cuatro personas y ser un extraño al menos nueve. Entre los nueve no será tres amigos comunes (y se hacen) o cuatro mutuo extraños, que hacen un grupo de cinco cuando incluimos el original de la persona que nos eligió.
Esto no prueba catorce es el mínimo, (ni seis ni nueve) - y, por tanto, no soluciona los números de Ramsey, pero sí hacer lo que quiera.
