Θεώρημα Ράμσεϋ

Στη συνδυαστική, το Θεώρημα Ράμσεϋ δηλώνει ότι σε οποιεσδήποτε χρωματισμένες  κορυφές από ένα αρκετά μεγάλο πλήρες γράφημα, θα βρει κανείς μονοχρωματικό πλήρη υπογράφημα. Για δύο χρώματα, το θεώρημα Ramsey αναφέρει ότι για κάθε ζεύγος θετικών ακεραίων (r, s), υπάρχει ένας μικρότερος θετικός ακέραιος R (R, S) τέτοιος ώστε για κάθε 2-χρωματισμούς του πλήρες γράφημα R (r, s) κορυφές, υπάρχει ένα πλήρες μονοχρωματικό υπογράφημα είτε r ή s κορυφές. Εδώ R (R, S) σημαίνει έναν ακέραιο που εξαρτάται τόσο από r και s. Είναι κατανοητό να αντιπροσωπεύει το μικρότερο ακέραιο για την οποία το θεώρημα κατέχει.
Το θεώρημα του Ramsey είναι ένα θεμελιώδες αποτέλεσμα της Συνδυαστικής. Η πρώτη εκδοχή αυτού του αποτελέσματος αποδείχθηκε μέσω του F. P. Ramsey. Αυτό, ξεκίνησε τη συνδυαστική θεωρία που σήμερα ονομάζεται θεωρία ράμσεϋ,που επιδιώκει την κανονικότητα μέσα διαταραχή: γενικές προϋποθέσεις για την ύπαρξη υποδομών με τακτικές ιδιότητες. Σε αυτή την εφαρμογή είναι ένα ζήτημα της ύπαρξης μονοχρωματικά υποσύνολα, δηλαδή, υποσύνολα συνδεδεμένα άκρα του ένα μόνο χρώμα.
Η επέκταση αυτού του θεωρήματος ισχύει για κάθε πεπερασμένο αριθμό των χρωμάτων, και όχι μόνο για δύο. Ακριβέστερα, το θεώρημα δηλώνει ότι για οποιοδήποτε δεδομένο αριθμό χρωμάτων c, και οποιοδήποτε δεδομένο ακέραιοι n₁,...,nc, υπάρχει ένας αριθμός, R(n₁, ..., nc), έτσι ώστε όταν οι κορυφές ενός πλήρους γραφήματος R(n₁, ..., nc) είναι χρωματισμένες με c διαφορετικά χρώματα, τότε για κάποιο i από 1 έως c,πρέπει να περιέχει ένα πλήρες υπογράφημα της τάξης nᵢ των οποίων οι κορυφές είναι όλες χρώμα i. Η ειδική περίπτωση παραπάνω έχει c = 2 (and n₁ = r and n₂ = s).

Παράδειγμα: R(3,3) = 6

Στο ακόλουθο παράδειγμα, ο τύπος R(3,3) παρέχει μια λύση στο ζήτημα το οποίο ζητά από τον ελάχιστο αριθμό των κορυφών ενός γραφήματος πρέπει να περιέχει, προκειμένου να διασφαλιστεί ότι είτε (1) τουλάχιστον 3 κορυφές στο γράφημα που συνδέονται ή (2) τουλάχιστον 3 κορυφές στο γράφημα είναι ασύνδετες. Σημειώστε ότι, λόγω της συμμετρικής φύσεως του προβλήματος χώρου, R(r,s) είναι ίσο με R(s,r).
Ας υποθέσουμε ότι οι κορυφές ενός πλήρους γραφήματος 6 κορυφές χρώματος κόκκινο και μπλε. Διαλέγουμε μια κορυφή v. Υπάρχουν 5 κορυφές εκτός από τη v και έτσι (από αρχή περιστερώνα) τουλάχιστον 3 από αυτές θα πρέπει να είναι το ίδιο χρώμα. Χωρίς το πρόβλημα της γενικότητας μπορούμε να υποθέσουμε τουλάχιστον 3 από αυτές τις άκρες, που συνδέει την κορυφή v σε κορυφές r, s και t, είναι μπλε. (Αν όχι, η ανταλλαγή κόκκινο και μπλε σε ότι ακολουθεί.) Εάν κάποια από τις ακμές (R, S), (R, T), (s, t) είναι επίσης μπλε, τότε έχουμε ένα εντελώς μπλε τρίγωνο. Αν όχι, τότε αυτές οι τρεις πλευρές είναι όλα κόκκινα και έχουμε ένα εντελώς κόκκινο τρίγωνο. Δεδομένου ότι το επιχείρημα αυτό λειτουργεί για τις χρωστικές ουσίες, κάθε K6 περιέχει ένα μονοχρωματικό K3, και ως εκ τούτου, R (3,3) ≤ 6. Η δημοφιλής έκδοση αυτή ονομάζεται θεώρημα των φίλων και των αγνώστων.
Μια εναλλακτική απόδειξη λειτουργεί με διπλή μέτρηση. Στη συνέχεια, ως εξής: Μετρήστε τον αριθμό των διατεταγμένων τριπλών  κορυφών x, y, z τέτοιο ώστε η άκρη (xy) να είναι κόκκινη και η ακμή (yz) είναι μπλε. Πρώτον, κάθε συγκεκριμένη κορυφή θα είναι η μέση είτε 0 × 5 = 0 (όλες οι ακμές από την κορυφή είναι το ίδιο χρώμα) 1 × 4 = 4 (τέσσερις έχουν το ίδιο χρώμα, το ένα είναι το άλλο χρώμα), ή 2 × 3 = 6 (τρεις έχουν το ίδιο χρώμα, δύο είναι το άλλο χρώμα), όπως τρίκλινα. Ως εκ τούτου, υπάρχουν πλέον 6 × 6 = 36 τέτοιες τριάδες. Δεύτερον, για κάθε μη-μονοχρωματικό τρίγωνο (xyz), υπάρχουν ακριβώς δύο τέτοιες τριάδες. Ως εκ τούτου, υπάρχουν πλέον 18 μη μονοχρωματικά τρίγωνα. Ως εκ τούτου, τουλάχιστον 2 από τα 20 τρίγωνα στο Κ6 είναι μονοχρωματικά.
Αντίθετα, είναι δυνατόν να 2-χρώμα ένα Κ5 χωρίς να δημιουργεί μονοχρωματικό K3, δείχνοντας ότι η R (3,3)> 5. Το μοναδικό χρώμα εμφανίζεται στα δεξιά. έτσι R(3,3) = 6.
Το έργο της απόδειξης ότι η R(3,3) ≤ 6 ήταν ένα από τα προβλήματα των William Lowell Putnam Mathematical Competition το 1953.

Γενική περίπτωση

Αποδεικνύουμε τώρα το αποτέλεσμα για τη γενική περίπτωση της με c χρώματα. Η απόδειξη είναι και πάλι από την επαγωγή, αυτή τη φορά σχετικά με τον αριθμό των χρωμάτων c. Έχουμε το αποτέλεσμα για c = 1  και c = 2 (ανωτέρω). Τώρα ας c> 2.
Λήμμα 2. R(n₁, ..., nc) ≤ R(n₁, ..., nc−2, R(nc−1, nc)).
Απόδειξη.Σκεφτείτε ένα γράφημα για t κορυφές και χρωματίζουν τις άκρες του με c χρώματα.Τώρα «πάμε αχρωματοψία» και υποθέτουμε ότι c − 1 και c έχουν το ίδιο χρώμα. Έτσι, η γραφική παράσταση είναι τώρα (c − 1)-χρωματισμένη.Από την επαγωγική υπόθεση, που περιέχει είτε ένα Kₙᵢ μονοχρωματικά με το χρώμα  i για κάποια 1 ≤ i ≤ c − 2 ή ένα KR₍ₙc−1,ₙc₎-χρωματισμένο με «θολό χρώμα». Στην πρώτη περίπτωση έχουμε τελειώσει. Στην τελευταία περίπτωση, μπορούμε να ανακτήσουμε πάλι την όραση μας και να δούμε από τον ορισμό ότι για R(nc−1, nc) εμείς πρέπει να έχουμε είτε μια (c − 1)-μονόχρωμη Kₙc−1 είτε μια c-μονόχρωμη Kₙc. Σε κάθε περίπτωση η απόδειξη είναι πλήρης.
Η δεξιά πλευρά της ανισότητας στο λήμμα 2 περιέχει Ramsey αριθμούς για c − 1 χρώματα και 2 χρώματα, και ως εκ τούτου υπάρχει και είναι ένας πεπερασμένος αριθμός t,από την επαγωγική υπόθεση. Έτσι, αποδεικνύοντας τον ισχυρισμό θα αποδειχθεί το θεώρημα.

Ένα πολύχρωμο παράδειγμα: R(3,3,3) = 17

Ένας πολύχρωμος αριθμός Ράμσευ είναι ένας αριθμός Ράμσευ με 3 ή περισσότερα χρώματα. Υπάρχει μόνο ένας τετριμμένος πολύχρωμος αριθμός Ράμσευ  για τον οποίο η ακριβής τιμή του είναι γνωστή, ο R(3,3,3) = 17.
Έστω ότι έχουμε την γωνία ενός πλήρους γραφήματος χρωματισμένη με τρία χρώματα, κόκκινο, κίτρινο και πράσινο. Έστω ακόμη ότι πως αυτή η άκρη του φραφήματος δεν έχει μονοχρωματικά τρίγωνα. Επιλέγουμε ενα ακρότατο v. Θεωρούμε το σύνολο των ακροτάτων τα οποία έχουν πράσινη πλευρά στο ακρότατο ν. Αυτό ονομάζεται "πράσινη γειτονιά του ν". Η πράσινη γειτονιά του ν δεν μπορεί να περιέχει άλλες πράσινες πλευρές, αφού αν είχε θα υπήρχαν τρίγωνα με τρεις πράσινες γωνίες στα δύο καταληκτικά σημεία αυτής της πράσινης γειτονιάς και του ακροτάτου ν. Συνεπώς, η περιεχόμενη γωνία χρωματιζόμενη στη πρασινη γειτονιά του ν έχει πλευρές χρωματιζόμενες μόνο με 2 χρώματα, το κίτρινο και το κόκκινο. Αφού R(3,3) = 6, η πράσινη γειτονιά του ν μπορει να περιέχει 5 ακρότατα. Ομοίως, οι κόκκινες και πράσινες γειτονιές του ν μπορούν να περιέχουν το πολυ 5 ακρότατα η κάθε μιαred and yellow. Αφού κάθε ακρότατο , εκτός από το ίδιο το ν ,είναι σε μία από τις πράσινες ,κόκκινες ή κίτρινες γειτονιές του ν, όλο το πλήρες γράφημα μπορεί να έχει  1 + 5 + 5 + 5 = 16 ακρότατα. Άρα, έχουμε R(3,3,3) ≤ 17.
Για να δούμε οτι το R(3,3,3) ≥ 17, επαρκεί για να ισοσταθμήσουμε μία γωνία χρωματίζοντας στην στο πλήρες γράφημα σε 16 ακρότατα με 3 χρώματα για να αποφύγουμε τα μονοχρωματικά τρίγωνα. Φαίνεται ότι υπάρχουν μόνο δύο χρωματισμοί στον K₁₆, οι αποκαλλούμενοι στρεβλοί και μη-στρεβλοί. Και οι δύο φαίνονται στο σχήμα στα δεξιά της σελίδας, με τον στρεβλό στο πάνω μέρος και τον μη-στρεβλό στο κάτω.Και στους δύο χρωματισμούς, παρατηρήστε οτι τα ακρότατα έχουν επισημανθεί, και οτι απο το v₁₁ εως το v₁₅ έχουν σκιαγραφηθεί διπλά,και στα αριστερά και στα δεξία ,για να απλοποιήσουμε.
Συνεπώς, R(3,3,3) = 17.
Αν επιλέξουμε ένα χρώμα σε οποιοδήποτε στρεβλό ή μη στρεβλό γράφημα K₁₆, και θεωρήσουμε το γράφημα του οποίου οι γωνίες είναι ακριβώς αυτές με το συγκεκριμμένο χρώμα, τότε θα έχουμε ένα διάγραμμα Clebsch (Clebsch γράφημα).
Είναι γνωστό ότι υπάρχουν 3 χρωματισμοί με 3 χρώματα στον K₁₅ οι οποίοι αποφεύγουν τα μονοχρωματικά τρίγωνα, και μπορούν να κατασκευαστούν σβήνοντας οποιοδήποτε ακρότατο απο το στρεβλό και μη στρεβλό διάγραμμα του K₁₆, διαδοχικά.
Είναι επίσης γνωστό ότι υπάρχουν 115 χρωματισμοί γωνιών με 3 χρώματα στον K₁₄ που αποφεύγουν τα μονοχρωματικά τρίγωνα,δεδομένου ότι θεωρουμε τους χρωματισμούς των γωνιών που διαφέρουν κατά μία μετάθεση χρώματος από το να γίνουν οι ίδιο.

Επεκτάσεις του θεωρήματος

Το θεώρημα μπορεί επίσης να επεκταθεί σε υπεργραφήματα. Ένα m-υπερ-γράφος είναι μια γραφική παράσταση του οποίου "άκρες" είναι σύνολα κορυφών m - σε ένα κανονικό γράφημα και μια ακμή είναι ένα σύνολο από 2 κορυφές. Η πλήρης δήλωση του θεωρήματος του Ramsey για υπεργραφήματα είναι ότι για κάθε ακέραιους m και c, και κάθε ακέραιοι n₁,...,nc,υπάρχει ένας ακέραιος R(n₁, ..., nc;c,m) οπότε, αν οι hyperedges ενός πλήρους m-υπεργράφημα της τάξης R(n₁,...,nc;c,m), χρωματισμένα με διαφορετικά χρώματα C, τότε για κάποια i μεταξύ 1 και c, η υπεργράφημα πρέπει να περιλαμβάνει μια πλήρη υπο-m-υπεργράφημα της ni τάξη που hyperedges είναι όλα τα χρώματα i. Το θεώρημα αυτό  συνήθως αποδεικνύεται από επαγωγή στο m, το «υπερ-ness» του γραφήματος. Η βασική περίπτωση για την απόδειξη είναι m = 2, το οποίο είναι ακριβώς το παραπάνω θεώρημα.

Απειροστικό θεώρημα Ramsey

Ένα περαιτέρω αποτέλεσμα, επίσης κοινώς ονομάζεται θεώρημα Ράμσεϊ, εφαρμόζεται σε άπειρες γραφικές παραστάσεις. Σε ένα πλαίσιο όπου πεπερασμένα γραφήματα συζητούνται επίσης είναι συχνά αποκαλείται το «Άπειρο Ramsey θεώρημα".Διαισθητικά όπως παρέχονται από την εικονογραφημένη αναπαράσταση ενός γραφήματος είναι μειωμένη κατά τη μετακίνηση από το πεπερασμένο στο άπειρο γραφήματα, θεωρήματα σε αυτόν τον τομέα είναι συνήθως διατυπώνονται σε σύνολο-θεωρητικές ορολογία.
Θεώρημα. Έστω X κάποιο αριθμήσιμο άπειρο σύνολο και το χρώμα των στοιχείων του X (υποσύνολα του X μεγέθους n) σε c διαφορετικά χρώματα. Τότε υπάρχει κάποιο άπειρο υποσύνολο M του X τέτοιο ώστε με μέγεθος n υποσυνόλων M όλα έχουν το ίδιο χρώμα.
Aπόδειξη :Η απόδειξη δίνεται για c = 2 Είναι εύκολο να αποδείξει το θεώρημα για έναν αυθαίρετο αριθμό χρωμάτων χρησιμοποιώντας το επιχείρημα «αχρωματοψία», όπως παραπάνω.. Η απόδειξη γίνεται με (πλήρης) επαγωγή στο n, το μέγεθος των υποσυνόλων. Για n = 1, η δήλωση είναι ισοδύναμη με λέγοντας ότι αν χωρίσετε ένα άπειρο σύνολο σε δύο ομάδες, μία από αυτές είναι άπειρη. Αυτό είναι εμφανές. Υποθέτοντας ότι το θεώρημα ισχύει για n ≤ r, θα το αποδείξουμε για n = r + 1. Λαμβάνοντας υπόψη ένα 2-χρωματισμός των υποσυνόλων (r + 1)-στοιχείο του Χ, ας a₀  είναι ένα στοιχείο του Χ και αφήστε Υ = Χ \ {a₀}. Στη συνέχεια, να προκαλέσει μια 2-χρωματισμός των υποσυνόλων r-στοιχείο του Y, προσθέτοντας απλά a₀ σε κάθε υποσύνολο r-στοιχείου (για να πάρετε μια (r + 1)-υποσύνολο στοιχείο του Χ). Από την επαγωγική υπόθεση, υπάρχει ένας άπειρος Y₁ υποσύνολο εντός Y τέτοια ώστε κάθε στοιχείο r-υποσύνολο των Y₁ είναι χρωματισμένο το ίδιο χρώμα στην επαγόμενη χρωματισμό. Έτσι, υπάρχει μια a₀ στοιχείο και ένα άπειρο υποσύνολο Y₁ τέτοια ώστε όλη η (r + 1)-στοιχείου υποσύνολα του Χ που αποτελείται από a₀ και r στοιχεία των Y₁ έχουν το ίδιο χρώμα. Από το ίδιο επιχείρημα, υπάρχει ένα στοιχείο στο  Y₁ και ένα άπειρο υποσύνολο των Y₁ Y₂ με τις ίδιες ιδιότητες. Επαγωγικά, παίρνουμε μια ακολουθία {a₀, a₁, a₂, ...} τέτοια ώστε το χρώμα του κάθε (r + 1)-υποσύνολο στοιχείο (aᵢ₍₁₎,(aᵢ₍₂₎), ..., (aᵢ₍ᵣ + 1)) με το i i(1) < i(2)<... <i(r + 1) εξαρτάται μόνο από την τιμή του i(1). Περαιτέρω, υπάρχουν άπειρες τιμές του i(1) έτσι ώστε αυτό το χρώμα θα είναι το ίδιο. Πάρτε αυτά τα aᵢ₍ₙ₎ να πάρει το επιθυμητό μονοχρωματικό σύνολο.

Η άπειρη προϋποθέτει την πεπερασμένη

Είναι δυνατόν να συναχθεί το πεπερασμένο θεώρημα Ramsey από την έκδοση του άπειρου, από την απόδειξη με αντίφαση.Ας υποθέσουμε ότι το πεπερασμένο θεώρημα Ramsey είναι ψευδή. Τότε υπάρχουν ακέραιοι c, n, T τέτοιοι ώστε για κάθε ακέραιο k, υπάρχει ένας c-χρωματισμός  χωρίς ένα μονοχρωματικό σύνολο μεγέθους T.Ας Cₖ δηλώνουν τις c-χρωστικές ουσίες  χωρίς ένα μονοχρωματικό σύνολο μεγέθους T.
Για κάθε k, ο περιορισμός μιας χρωστικής από Cₖ₊₁ σε  (αγνοώντας το χρώμα όλων των συνόλων που περιέχουν k+1) είναι ένας χρωματισμός σε Cₖ.Ορίζουν  να είναι οι χρωστικές ουσίες σε Cₖ οι οποίες είναι οι περιορισμοί των χρωστικών ουσιών στα Cₖ₊₁. Όσο Cₖ₊₁ δεν είναι κενή, ούτε είναι .
Ομοίως, ο περιορισμός για τις χρωστικές ουσίες σε  είναι σε , επιτρέποντας έτσι να καθορίσει  ως το σύνολο όλων αυτών των περιορισμών, ένα μη-κενό σύνολο. Συνεχίζοντας έτσι, ορίζουν  για όλους τους ακέραιους m, k.
Τώρα, για κάθε ακέραιο k, ,και κάθε σύνολο, είναι μη κενό. Επιπλέον, Cₖ είναι πεπερασμένη, όπως . Επομένως, η διασταύρωση όλων αυτών των συνόλων είναι μη κενή, και ας .Στη συνέχεια, κάθε χρωματισμός σε Dₖ είναι ο περιορισμός μιας χρωστικής σε Dₖ₊₁.Ως εκ τούτου, με την unrestricting χρωστική σε Dₖ σε χρωστικές ουσίες Dₖ₊₁, και συνεχίζοντας αυτόν τον τρόπο, ένας κατασκευάζει ένα χρωματισμό  χωρίς μονοχρωματικό σύνολο μεγέθους T. Αυτό έρχεται σε αντίθεση με το άπειρο θεώρημα Ramsey.
Αν μια κατάλληλη τοπολογική άποψη έχει ληφθεί, το επιχείρημα αυτό μετατρέπεται σε ένα τυπικό συμπαγές επιχείρημα δείχνοντας ότι η άπειρη έκδοση του θεωρήματος συνεπάγεται την πεπερασμένη έκδοση.

Κατευθυνόμενο γράφημα αριθμοί Ramsey

Είναι επίσης δυνατό να καθοριστούν οι αριθμοί Ramsey για κατευθυνόμενη γραφήματα.  (Αυτά εισήχθησαν από P. Erdős & L. Moser.)  Έστω R (n) είναι ο μικρότερος αριθμός Q τέτοιος ώστε κάθε πλήρες γράφημα με μεμονωμένα τόξα (ονομάζεται επίσης «τουρνουά») και με κόμβους ≥ Q περιέχει μία μη κυκλική (ονομάζεται επίσης "μεταβατικό") τουρνουά υπο n-κόμβο.
Αυτό είναι το ανάλογο κατευθυνόμενο γράφημα του τι (ανωτέρω) έχει κληθεί R (Ν, Ν? 2), ο μικρότερος αριθμός Ζ τέτοια ώστε κάθε 2-χρωματισμός των ακμών ενός πλήρους μη-κατευθυνόμενου γραφήματος με ≥ Ζ κόμβους, περιέχει ένα μονοχρωματικό πλήρες γράφημα n κόμβων. (Η κατευθυνόμενη αναλογική των δύο πιθανών χρώματα τόξου είναι οι δύο κατευθύνσεις των τόξων, το ανάλογο της «μονοχρωματικό" είναι "όλα τα arc-βέλη δείχνουν τον ίδιο τρόπο", δηλαδή "άκυκλων.")
Πράγματι, πολλοί που θεωρούν το κατευθυνόμενο γράφημα για να είναι πιο κομψό από το μη-κατευθυνόμενο. Έχουμε R(0) = 0, το R(1) = 1, το R(2) = 2, το R(3) = 4, το R(4) = 8, το R(5) = 14, το R(6) = 28 , 32 ≤ R(7) ≤ 55, και R(8) είναι ένα πρόβλημα και πάλι, σύμφωνα με Erdős, ότι κάποιος δεν θέλει ισχυρό αλλοδαπούς να θέσουν.