Συμβολές στην Ευκλείδεια Θεωρία Ramsey

Abstract

The subject of this PhD dissertation thesis, is Euclidean Ramsey theory and more specifically the problem of characterization of Ramsey sets. A finite subset Χ of some Euclidean space Rn for some n ∈ N is Ramsey, if for every number of colors r ∈ N there exists a large enough dimension N ∈ N, such that, for every coloring of RN we can find a monochromatic congruent copy of X.In the Introduction, we start by exploring the wealth of the results and new objects of study that where stated in the work titled “Euclidean Ramsey Theorems I”, which is considered the seminal paper for the new theory. We explore the simplest of Ramsey sets, like the regular simplex in any dimension and we see that no three co-linear points are Ramsey. Then we discuss some of the structural properties of Ramsey sets, for example we see that the finite products of Ramsey sets are Ramsey and that every Ramsey set must be spherical. Continuing our discussion, we list all known Ramsey sets, together with rough sketches for some of the proofs. The most significant results concerning the subject of characterizing Ramsey sets are two. The first is due to Frankl and Rödl, who in 1990 proved that any simplex is Ramsey. The second we owe it to Kříž, who in 1991 proved that, every transitive set with a solvable group of isometries with at most two orbits, is Ramsey. This, gives as a corollary that regular polygons and vertex sets of all platonic solids are Ramsey.Starting with our results, we describe how the apparent generality of Kříž’s theorem led us to wonder if Frankl’s and Rödl’s theorem about simplices can be induced in a similar fashion. We answer affirmatively this question, by showing that any simplex can be embedded into a regular polygonal torus, that is, the cartesian product of finitely many regular polygons. Afterwards, we discuss the two rival conjectures about Ramsey sets, the one due to Graham which says that all spherical sets are Ramsey, and the other due to Leader, Russell and Walters which say that Ramsey sets are exactly the sets that embed into some transitive set. The later group, have shown that the sufficient part of their conjecture, corresponds to a series of equivalent conjectures, which are striped from geometry and resemble the famous theorem of Hales and Jewett. One of these conjectures is a statement about a property that all finite groups must have. After we give the necessary definitions, we state two results concerning solvable groups and general actions from solvable groups, that confirm LRW conjecture in a stronger form for the case of solvable groups. Furthermore, we recover refined versions of all of Kříž results.During the next chapters, we present our proofs. For the simplices, first we show that all “almost regular” simplices embed into some regular polygonal torus. Then we show that regular polygonal tori, are in a specific sense “dense”. Finally with the help of a theorem which characterizes finite metric spaces that embed into some Euclidean space, we first break any simplex into one almost regular part and another which also embeds into a regular polygonal torus completing the proof. For the Hales-Jewett type results, we modify a well known lemma due to Shelah, and with techniques from Ramsey theory for product spaces combined with a combinatorial argument due to Kříž we manage to prove the stated results.In the last chapters, we mention some more things about another of the equivalent conjectures made by LRW. Their proof about a special case of this conjecture produces some new Ramsey sets. We then go and prove, that all these new Ramsey sets can be also obtained from Kříž results, by embedding them into a transitive set with a solvable group of isometries. We conclude with the remark, that until now, all known Ramsey sets, can be shown to be so using Kříž theorem.

Η παρούσα διδακτορική διατριβή έχει σαν αντικείμενο μελέτης την Ευκλείδεια θεωρία Ramsey και πιο συγκεκριμένα, τα Ramsey υποσύνολα των ευκλείδειων χώρων. Ένα πεπερασμένο σύνολο X, το οποίο είναι υποσύνολο κάποιου ευκλείδειου χώρου Rm για κάποιο m ∈ N, λέγεται Ramsey, αν για κάθε αριθμό χρωμάτων r ∈ N, υπάρχει μια αρκετά μεγάλη διάσταση N ∈ N, η οποία είναι τέτοια, ώστε για κάθε διαμέριση του ευκλείδειου χώρου RN διάστασης N σε r σύνολα (την οποία αποκαλούμε χρωματισμό), υπάρχει ένα ισομετρικό (ως προς την ευκλείδεια νόρμα) αντίγραφο του X, το οποίο είναι μονοχρωματικό (περιέχεται σε ένα στοιχείο της διαμέρισης).Στην Εισαγωγή, αφού κάνουμε μια αναφορά στο θεμελιώδες θεώρημα του Frank Plumpton Ramsey, στην συνέχεια εξετάζουμε κάποια αποτελέσματα από την εργασία του 1973 “Euclidean Ramsey Theorems I” όπου ορίστηκαν για πρώτη φορά τα Ramsey σύνολα και από την οποία ουσιαστικά γεννήθηκε η Ευκλείδεια θεωρία Ramsey. Συγκεκριμένα, βλέπουμε τα πρώτα παραδείγματα Ramsey συνόλων, όπως για παράδειγμα το σύνολο των κορυφών ενός κανονικού simplex και τα πρώτα αντιπαραδείγματα, όπως κάθε σύνολο τριών συνευθειακών σημείων. Στην συνέχεια, αναφέρουμε τα θεμελιώδη δομικά χαρακτηριστικά των Ramsey συνόλων, δηλαδή ότι το καρτεσιανό γινόμενο Ramsey συνόλων είναι Ramsey και ότι κάθε Ramseyσύνολο είναι υποσύνολο της επιφάνειας μιας σφαίρας. Ύστερα, αναφέρουμε (σχεδόν) όλα τα αποτελέσματα από τα οποία προέκυψαν νέες κλάσεις Ramsey συνόλων, σκιαγραφώντας κάποιες από τις αποδείξεις. Τα πιο σημαντικά αποτελέσματα όσον αφορά το πρόβλημα του χαρακτηρισμού των Ramsey συνόλων είναι τα εξής. Το πρώτο είναι αυτό των Frankl και Rödl οι οποίοι το 1990 κατάφεραν να δείξουν ότι κάθε simplex, δηλαδή κάθε πεπερασμένο αφινικά ανεξάρτητο σύνολο, είναι Ramsey. Το δεύτερο και σημαντικότερο, το οφείλουμε στον Igor Kříž, ο οποίος το 1991 απέδειξε ότι κάθε πεπερασμένο transitive ευκλείδειο σύνολο, για το οποίο υπάρχει μία επιλύσιμη ομάδα συμμετριών, με το πολύ δύο τροχιές, είναι Ramsey. Σαν άμεσο πόρισμα τα κανονικά πολύγωνα και τα σύνολα κορυφών όλων των πλατωνικών στερεών είναι Ramsey. Στην συνέχεια, περνάμε στην περιγραφή των αποτελεσμάτων που προέκυψαν κατά την διάρκεια αυτής της διατριβής. Οδηγούμενοι από την διαφαινόμενη εφαρμοστικότητα του θεωρήματος του Kříž, αναρωτιόμαστε αν το θεώρημα των Frankl και Rödl για τα simplices μπορεί να προκύψει από το αποτέλεσμα του Kříž. Απαντάμε καταφατικά, δείχνοντας ότι κάθε simplex μπορεί να εμφυτευτεί ισομετρικά σε έναν κανονικό πολυγωνικό τόρο, που δεν είναι τίποτα άλλο, από το καρτεσιανό γινόμενο ενός πεπερασμένου αριθμού κανονικών πολυγώνων.Υπάρχουν δύο διαδεδομένες εικασίες όσον αφορά τα Ramsey σύνολα. Η πρώτη, του Graham, υποστηρίζει ότι όλα τα σφαιρικά σύνολα είναι Ramsey. Η δεύτερη και πιο πρόσφατη, από τους Leader, Russell και Walters λέει ότι τα Ramsey σύνολα είναι ακριβώς αυτά που εμφυτεύονται σε κάποιο transitive σύνολο. Οι τελευταίοι, σε μια σειρά από ισοδύναμες εικασίες, εξέφρασαν μια ικανή συνθήκη ώστε όλα τα transitive σύνολα να είναι Ramsey, μετασχηματίζοντας το πρόβλημα σε καθαρά συνδυαστικό. Οι εικασίες αυτές, προσομοιάζουν το γνωστό αποτέλεσμα των Hales και Jewett για μεταβλητές λέξεις και μια από αυτές αφορά μια ιδιότητα που πρέπει να έχει κάθε πεπερασμένη ομάδα. Αφού δώσουμε κατάλληλους ορισμούς, διατυπώνουμε κάποια σχετικά αποτελέσματα που αφορούν γενικές δράσεις επιλύσιμων ομάδων, από τα οποία προκύπτει μια ισχυρότερη μορφή της αντίστοιχης εικασίας των LRW και μια εκλέπτυνση των αποτελεσμάτων του Kříž.Στα επόμενα δύο κεφάλαια παρουσιάζουμε τις αποδείξεις των αποτελεσμάτων μας. Για τα simplices, πρώτα δείχνουμε ότι κάθε “σχεδόν κανονικό” simplex, εμφυτεύεται ισομετρικά σε έναν κανονικό πολυγωνικό τόρο. Στην συνέχεια, δείχνουμε ότι κάθε πεπερασμένο σύνολο, είναι αυθαίρετα κοντά σε ένα υποσύνολο ενός κανονικού πολυγωνικού τόρου. Τέλος, με την βοήθεια ενός χαρακτηρισμού των πεπερασμένων μετρικών χώρων που εμφυτεύονται ισομετρικά σε κάποιο Ευκλείδειο χώρο, “σπάμε” το simplex, σε μέρη που εμφυτεύονται σε κάποιο πολυγωνικό τόρο και ολοκληρώνουμε την απόδειξη. Για τα αποτελέσματα “τύπου” Hales-Jewett, προσαρμόζουμε ένα γνωστό λήμμα του Shelah στις ανάγκες της απόδειξης και με τεχνικές της σχετικής θεωρίας, εκμεταλλευόμαστε ένα συνδυαστικό επιχείρημα του Kříž χρησιμοποιώντας το ως αρχή του περιστερώνα, για να φτάσουμε στο ζητούμενο.Στα τελευταία κεφάλαια, αναφέρουμε λίγα πράγματα επιπλέον για μια άλλη από τις ισοδύναμες εικασίες των LRW, που δεν αφορά πεπερασμένες ομάδες και για την οποία απέδειξαν την εικασία τους σε μια πολύ συγκεκριμένη περίπτωση. Στην συνέχεια, δείχνουμε ότι για τα ευκλείδεια σύνολα για τα οποία προκύπτει ότι είναι Ramsey μέσω των αποτελεσμάτων των LRW, υπάρχει εναλλακτική απόδειξη μέσω του θεωρήματος του Kříž και καταλήγουμε στο συμπέρασμα, ότι όλα τα μέχρι σήμερα γνωστά Ramsey σύνολα, έπονται ως τέτοια από το θεώρημα του Kříž. Κλείνουμε αυτή την εργασία κάνοντας μια αφελή εικασία για τα transitive ευκλείδεια σύνολα και προτείνοντας κάποιες πιθανές κατευθύνσεις της σχετικής έρευνας.