Αριθμοί Ramsey:
Creators: name: Ιωσηφίδης, Λεωνίδας Γεωργίου
Publisher: name: Aristotle University of Thessaloniki
Year: 2009
Subjects: Θεωρία γραφήματος
Probablistic μέθοδος
Αριθμοί Ramsey
Ramsey numbers
Probabilistc method
Theory group

description: Οι αριθμοί Ramsey είναι μέρος της θεωρίας γραφημάτων, που λόγω της ανάπτυξής τους, τελικά εξελίχθηκαν σε θεωρία. Οι αριθμοί αυτοί πρωτοεμφανίστηκαν από τον ίδιο τον Ramsey το 1930. Στη συνέχεια, τη σκυτάλη πήρε ο Erdös, που κατάφερε να κατασκευάσει μια αναδρομική ανισότητα, για να φράξει από πάνω τους αριθμούς αυτούς. Από τότε μέχρι τώρα, έχουν γίνει πολλές προσπάθειες, για να υπολογιστούν οι αριθμοί αυτοί αλλά μόλις 9 αριθμοί έχουν υπολογιστεί. Παρόλη την ανάπτυξη των υπολογιστών και της δύναμής τους, δεν μπορούμε να υπολογίσουμε και άλλους αριθμούς. Ωστόσο, για πολλούς από αυτούς έχουμε ικανοποιητικά φράγματα. Δεν είναι τυχαίο πως στη θεωρία Ramsey έχουμε πολλά ανοιχτά προβλήματα. Η προσπάθεια υπολογισμού αυτών των αριθμών είχε ως συνέπεια να αναπτυχθούν και κάποιες άλλες ενότητες της θεωρίας γραφημάτων.Στο πρώτο κεφάλαιο, αναφέρω κάποιες βασικές έννοιες στη θεωρία γραφημάτων, που είναι απαραίτητες για τη συνέχεια. Στο δεύτερο κεφάλαιο, αναφέρονται και αποδεικνύονται κάποιοι γνωστοί αριθμοί Ramsey και τα φράγματα τους, ενώ το τρίτο έχει να κάνει με κάποιες γενικεύσεις και παρατηρήσεις του πρώτου μη τετριμμένου αριθμού Ramsey και γίνεται επαλήθευση μέσω υπολογιστή. Στο τέταρτο κεφάλαιο, αναφέρονται οι πολλαπλοί αριθμοί Ramsey σε γραφήματα (k). Στο πέμπτο κεφάλαιο, κάνουμε λόγο για δύο βασικά θεωρήματα, του Schur και του Turan, γενικεύσεις τους και εφαρμογές τους στους αριθμούς Ramsey. Είναι θεωρήματα που δημιουργήθηκαν για τον υπολογισμό των αριθμών Ramsey.Στο έκτο κεφάλαιο, κάνουμε λόγο για την probabilistic μέθοδο, μια σχετικά καινούργια μέθοδο, που είχε πρωτοεφαρμόσει ο Erdös. Στο έβδομο και τελευταίο κεφάλαιο, αποδεικνύονται κάποιοι γενικοί αρθμοί Ramsey και για κάποιους από αυτούς γίνεται επαλήθευση μέσω υπολογιστή.
description: Ramsey numbers are part of the theory of graphs which, by reason of their development, finally evolved as a theory.These numbers were first developed by Ramsey himself, in 1930. After that, Erdös took up the baton, and succeeded in constructing a retrospective inequality in order to bound these upper numbers. Since then up to the present day, many attempts have been made to calculate these numbers, but so far, only 9 of them have been calculated. Despite developments in computers and their power, we haven’t been able to calculate the remaining numbers. However, for many of these numbers we do have satisfactory bounds. It is not accidental that the Ramsey theory has many open-ended problems. Efforts to calculate these numbers have resulted in the development of certain other units in the theory of graphs.In the first chapter, I refer to certain basic meanings in the theory of graphs which are essential for what follows. In the second chapter, certain known Ramsey numbers and barriers are referred to and proved, while the third chapter has to do with certain generalisations and observations on the first apparent Ramsey number, which is verified by means of a computer. In the fourth chapter, the multiple Ramsey numbers are referred to in graphs (k). In the fifth chapter we discuss two basic theorems, those of Schur and Turan, their generalizations and applications of the Ramsey numbers. These are theorems which were devised to calculate the Ramsey numbers. In the sixth chapter we discuss the probabilistic method, a relatively new method which was developed by Erdös. In the seventh and final chapter, certain general Ramsey numbers are proved and for some of these verification is given by means of a computer.