Ramseys Theorem besagt, dass jeder Graph mit Knoten enthält entweder eine Clique oder eine unabhängige Menge mit mindestens Knoten.
Ich habe versucht, es an einigen Stellen nachzuschlagen (einschließlich Sipser), aber ich konnte aus den Beweisen nicht viel Sinn erkennen. Ich würde es begrüßen, wenn mir jemand einen Beweis (oder eine klare Intuition) dafür geben könnte.
Antworten:
LassenR(s,t) sei die kleinste ganze Zahl k so dass jeder Graph auf k oder mehr Eckpunkte enthalten entweder a s -clique oder unabhängige Größe t.
Es stellt sich heraus, dass diese Nummer gut definiert ist ( Ramsey-Nummer genannt ) und die Aussage in Ihrer Frage lediglich darauf hinausläuft, dies zu sagen
Eine bekannte Obergrenze für Ramsey-Zahlenzustände
Beweisen(1) man kann Induktion auf verwenden s+t . Verlassen der InduktionsbasisR(1,t),R(s,1) Nehmen wir als Übung für Sie an, dass die Ungleichheit für alle gilt s+t<k und lass G sei ein Graph mit R(s,t−1)+R(s−1,t) Eckpunkte.
Lassenv sei ein beliebiger Scheitelpunkt von G und unterteilen Sie die verbleibenden Eckpunkte des Diagramms in zwei Gruppen A,N - die angrenzenden mit v und diejenigen, die nicht benachbart sind mit v. Jetzt seit
quelle