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

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

Συνήθως, η απάντηση στο πιο πάνω ερώτημα είναι συναρτήσει του μεγέθους του X. Για αυτόν το λόγο, συνηθίζεται να παίρνουμε ως X το σύνολο \{1,2,\ldots,n\}, το οποίο συνηθίζεται να γράφεται εν συντομία ως [n]. Επιπλέον, συχνά θα θέλουμε να μιλούμε για το σύνολο \{A_1,\ldots,A_k\}. Επειδή τα στοιχεία του είναι και αυτά σύνολα, για να μην μιλάμε για σύνολα συνόλων προτιμάμε να ονομάζουμε το  \{A_1,\ldots,A_k\} οικογένεια συνόλων. Mια οικογένεια με το ελάχιστο ή μέγιστο δυνατό πλήθος στοιχείων ονομάζεται ανάλογα ελάχιστη ή μέγιστη. Ονομάζεται επίσης και ακρότατη. Τέλος, είθισται να συμβολίσουμε τα στοιχεία του X με μικρά γράμματα, τα υποσύνολα του X με κεφαλαία γράμματα, και τις οικογένειες υποσυνόλων του X με καλλιγραφικά γράμματα.

Ας προχωρήσουμε τώρα σε ένα απλό πρόβλημα ακρότατης συνολοθεωρίας: Έστω ότι έχουμε μια οικογένεια \mathcal{A} υποσυνόλων του [n]. Θα ονομάζουμε αυτήν την οικογένεια αυτοτεμνόμενη (intersecting) αν για κάθε A,B \in \mathcal{A} ισχύει ότι A \cap B \neq \emptyset. Το ερώτημα είναι ποιο είναι το μέγιστο μέγεθος μια τέτοιας οικογένειας. Σας προτρέπω να το σκεφτείτε προτού διαβάσετε παρακάτω καθώς είναι ένα αρκετά απλό πρόβλημα ακρότατης συνολοθεωρίας. Η απάντηση δίνεται από το πιο κάτω το θεώρημα. 

Θεώρημα: Έστω μια αυτοτεμνόμενη οικογένεια υποσυνόλων \mathcal{A} του [n]. Τότε |\mathcal{A}| \leqslant 2^{n-1}. Επιπλέον αν |\mathcal{A}| < 2^{n-1} τότε υπάρχει αυτοτεμνόμενη οικογένεια υποσυνόλων \mathcal{B} του [n] με \mathcal{A} \subseteq \mathcal{B} και |\mathcal{B}| = 2^{n-1}.

Απόδειξη: Υπάρχουν ακριβώς 2^n υποσύνολα του [n] τα οποία μπορούμε να τα χωρίσουμε σε 2^{n-1} ζεύγη της μορφής \{A,A^{\mathsf{c}}\} όπου A^{\mathsf{c}} = [n] \setminus A. Αφού όμως A \cap A^{\mathsf{c}} = \emptyset, από κάθε τέτοιο ζεύγος η \mathcal{A} μπορεί να περιέχει το πολύ ένα στοιχείο. Άρα όντως |\mathcal{A}| \leqslant 2^{n-1}.

Αν τώρα  |\mathcal{A}| < 2^{n-1} τότε από τα πιο πάνω πρέπει να υπάρχει υποσύνολο A του [n] ώστε A,A^{\mathsf{c}} \notin \mathcal{A}. Ισχυρίζομαι ότι τουλάχιστον μία από τις οικογένειες \mathcal{A} \cup \{A\} και \mathcal{A} \cup\{A^{\mathsf{c}}\} είναι αυτοτεμνόμενη. Πράγματι αν καμία δεν είναι αυτοτεμνόμενη, τότε υπάρχουν B,C \in \mathcal{A} ώστε B \cap A = \emptyset και C \cap A^{\mathsf{c}} = \emptyset. Τότε όμως είναι B \subseteq A^{\mathsf{c}} και C \subseteq A οπότε B \cap C = \emptyset. Αυτό όμως είναι άτοπο αφού η \mathcal{A} είναι αυτοτεμνόμενη. Ο δεύτερος ισχυρισμός έπεται πλέον επαγωγικά. \square

Το πιο πάνω θεώρημα όχι μόνο μας λέει το μέγεθος μιας ακρότατης οικεγένειας, αλλά μας δείχνει και πως μπορούμε (επαγωγικά) να κατασκευάσουμε κάθε ακρότατη οικογένεια. Δυστυχώς όμως δεν μας λέει τα πάντα. Στην ακρότατη συνδυαστική συνήθως μας ενδιαφέρει επιπλέον και το πόσες ακρότατες οικογένειες υπάρχουν.  Έστω a(n) ο αριθμός των μέγιστων αυτοτεμνόμενων οικογενειών υποσυνόλων του [n]. Δυστυχώς ο υπολογισμός του a(n) είναι ένα πολύ δύσκολο πρόβλημα. Είναι απλό ότι a(1)=1,a(2)=2,a(3)=4,a(4)=12 και a(5)=81. Ο υπολογισμός του a(n) δυσκολεύει απότομα από δω και πέρα με το a(9) να έχει υπολογιστεί μόλις το 2012 και το a(10) να μην έχει υπολογιστεί ακόμη επακριβώς.

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

\displaystyle a(n) = 2^{\displaystyle{(1+o(1))\frac{2^n}{\sqrt{2\pi n}}}}.

Advertisements

About Δημήτρης Χριστοφίδης

Course Leader in Mathematics at UCLan Cyprus.
This entry was posted in 05D05 - Extremal Set Theory and tagged , . Bookmark the permalink.

Σχολιάστε

Εισάγετε τα παρακάτω στοιχεία ή επιλέξτε ένα εικονίδιο για να συνδεθείτε:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση / Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση / Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση / Αλλαγή )

Φωτογραφία Google+

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google+. Αποσύνδεση / Αλλαγή )

Σύνδεση με %s