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

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

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 ο οποίος και ανακάλυψε αυτήν την απόδειξη στην ηλικία των δεκαπέντε ετών.

Το θεώρημα Bolyai–Gerwien

Το θεώρημα των Bolyai-Gerwien λέει το εξής:

Για κάθε δύο πολύγωνα με το ίδιο εμβαδόν μπορούμε να κόψουμε το ένα σε πεπερασμένο αριθμό πολυγώνων και να τα επανατοποθετήσουμε με τέτοιο τρόπο ώστε να φτιάξουμε το δεύτερο πολύγωνο. (Τα κομμάτια επιτρέπεται να μεταφερθούν και να περιστραφούν.)

Ο Bolyai σε αυτό το θεώρημα είναι ο Farkas Bolyai, ο πατέρας του γνωστού για την δουλειά του στην μη Ευκλείδια γεωμετρία János Bolyai.

Το θεώρημα του γάμου (ΙΙ)

Ας δούμε και μερικές εφαρμογές του θεωρήματος του γάμου.

Το θεώρημα του γάμου

Έχουμε μια ομάδα αγοριών τα οποία θέλουμε να τα παντρέψουμε με κάποια κορίτσια. Αυτό θα γίνει με τον εξής τρόπο: Κάθε αγόρι ετοιμάζει μια λίστα με όλα τα κορίτσια τα οποία θα δεχόταν να παντρευτεί. Σκοπός μας είναι να καταφέρουμε να παντρέψουμε κάθε αγόρι με κάποιο κορίτσι από την λίστα του. Κάτω από ποιες συνθήκες μπορούμε να το πετύχουμε αυτό; (Το πρόβλημα αφορά μια ανδροκρατούμενη κοινωνία όπου τα κορίτσια δεν έχουν λόγο. Όσες θέλουν μπορούν να σκεφτούν το αντίστοιχο πρόβλημα μιας γυναικοκρατούμενης κοινωνίας.)