Ακρότατη Συνολοθεωρία

Οι ερωτήσεις που μας απασχολούν στην ακρότατη συνολοθεωρία (extremal set theory) είναι του πιο κάτω τύπου: Έχουμε ένα, συνήθως πεπερασμένο, σύνολο . Έχουμε επίσης κάποια υποσύνολα του τα οποία ικανοποιούν κάποιες ιδιότητες. Συνήθως οι ιδιότητες που ικανοποιούν έχουν να κάνουν με τις τομές, τις ενώσεις, κ.τ.λ. των συνόλων . Σκοπός μας είναι να βρούμε το μέγιστο ή ελάχιστο δυνατό πλήθος των .

Advertisements

Latex to Wordpress

Εδώ θα βρείτε το Latex2WP ένα αρκετά βοηθητικό πρόγραμμα από τον Luca Trevisan που μετατρέπει τον κώδικα Latex σε κώδικα κατανοητό από το WordPress.

Μια εισαγωγή στην αριθμησιμότητα (2)

Στην εισαγωγή στην αριθμησιμότητα ορίσαμε ότι ένα σύνολο είναι αριθμήσιμο αν υπάρχει 1-1 συνάρτηση και είδαμε ορισμένα σύνολα όπως τα τα οποία είναι αριθμήσιμα. Παρέμεινε όμως το ερώτημα αν υπάρχει σύνολο το οποίο δεν είναι αριθμήσιμο.

Το θεώρημα Beck-Fiala

Το θεώρημα των Beck και Fiala είναι ένα από τα κυριότερα θεωρήματα στην θεωρία ασυμφωνίας (discrepancy theory). Στην θεωρία ασυμφωνίας μας ενδιαφέρει το πόσο κοντά μπορούμε να φτάσουμε σε μια «ιδανική» ομοιόμορφη διάταξη. Π.χ. ο χρωματισμός μιας σκακιέρας με τα χρώματα μαύρο-άσπρο είναι ομοιόμορφος υπό την άποψη ότι κάθε οριζόντια και κάθε κάθετη ευθεία έχει τέσσερα άσπρα και τέσσερα μαύρα τετράγωνα. Από την άλλη αν λάβουμε υπόψη και τις διαγωνίους της σκακιέρας τότε ο χρωματισμός παύει να είναι ομοιόμορφος με αυτήν την έννοια αφού για παράδειγμα έχουμε μια διαγώνιο με οκτώ μαύρα και κανένα άσπρο τετράγωνο. Η ασυμφωνία αυτού του χρωματισμού είναι , όσο και η μέγιστη διαφορά (σε απόλυτη τιμή) μεταξύ των μαύρων και άσπρων τετραγώνων στις ευθείες που μας ενδιαφέρουν.

Μια εισαγωγή στην αριθμησιμότητα (1)

Πως μπορούμε να συγκρίνουμε δυο σύνολα ως προς το «μέγεθος» τους; Για τα πεπερασμένα σύνολα αυτό είναι εύκολο. Απλά μετράμε τον αριθμό των στοιχείων τους. Για παράδειγμα το σύνολο έχει περισσότερα στοιχειά από το σύνολο . Μπορούμε λοιπόν να πούμε ότι το έχει μεγαλύτερο «μέγεθος» από το . Οι δυσκολίες αρχίζουν όταν θέλουμε να συγκρίνουμε άπειρα σύνολα. Για παράδειγμα, πως θα συγκρίνουμε το σύνολο των φυσικών αριθμών, με το σύνολο των τέλειων τετραγώνων;

Δημοκρατία ή … δικτατορία; – Το παράδοξο του Arrow

Παίρνοντας αφορμή από τις προσεχείς βουλευτικές εκλογές στην Κύπρο, επιστρέφω μετά από περισσότερο από ένα χρόνο απραξίας με ένα καινούργιο άρθρο.

Φυσικά εδώ θα ασχοληθούμε με μαθηματικά και όχι με την πολιτική. Θα παρουσιάσω λοιπόν ένα εκλογικό παράδοξο το οποίο ανακαλύφθηκε από τον οικονομολόγο Kenneth Arrow ο οποίος το 1972 τιμήθηκε και με το βραβείο Νόμπελ.

Το θεώρημα του Dirac

Έχουμε μια συγκέντρωση ατόμων, στην οποία κάθε άτομο γνωρίζεται με τουλάχιστον άλλα άτομα. Το θεώρημα του Dirac λέει ότι σε αυτήν την περίπτωση μπορούμε να καθίσουμε όλους σε ένα κυκλικό τραπέζι ώστε κάθε άτομο να γνωρίζει και τους δύο που κάθονται δίπλα του.

(Το πρόβλημα υποθέτει ότι η σχέση γνωριμίας είναι συμμετρική. Αν o γνωρίζει τον τότε και ο γνωρίζει τον .)

Ο Dirac από τον οποίο πήρε το όνομα αυτό το θεώρημα είναι ο Gabriel Andrew Dirac, θετός γιος του διάσημου θεωρητικού φυσικού Paul Dirac. Η απόδειξη του θεωρήματος που θα δώσουμε είναι του Louis Pósa ο οποίος και ανακάλυψε αυτήν την απόδειξη στην ηλικία των δεκαπέντε ετών.