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

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

Γενικά έστω ότι έχουμε ένα σύνολο X και μια οικογένεια υποσυνόλων \mathcal{A} του X. Για κάθε συνάρτηση \chi:X \to \{-1,1\} και κάθε A \in \mathcal{A} ορίζουμε την ασυμφωνία του A σε σχέση με το \chi ως

\displaystyle{\mathrm{disc}_{\chi}(A) = \mathrm{disc}(A) = \left|\sum_{x \in A} \chi(x)\right|.}

Δηλαδή αν αντιστοιχίσουμε στην συνάρτηση \chi ένα χρωματισμό όπου τα στοιχεία x με \chi(x) = 1 χρωματίζονται άσπρα και αυτά με \chi(x) = -1 χρωματίζονται μαύρα, τότε η ασυμφωνία του A ισούται με την διαφορά σε απόλυτη τιμή μεταξύ των άσπρων και μαύρων στοιχείων του A.

Η ασυμφωνία της οικογένειας \mathcal{A} σε σχέση με τον χρωματισμό \chi ορίζεται ως

\displaystyle{\mathrm{disc}(\mathcal{A};\chi) = \max_{A \in \mathcal{A}} \mathrm{disc}_{\chi}(A).}

Δηλαδή κοιτάμε τις ασυμφωνίες για κάθε A \in \mathcal{A} και παίρνουμε την μέγιστη ασυμφωνία.

Τέλος η ασυμφωνία της οικογένειας \mathcal{A} είναι η

\displaystyle{\mathrm{disc}(A) = \min_{\chi:X \to \{-1,1\}}{\mathrm{disc(A;\chi)}} = \min_{\chi:X \to \{-1,1\}}\max_{A \in \mathcal{A}}\left|\sum_{x \in A} \chi(x)\right|.}

Τώρα έχουμε όλες τις απαραίτητες έννοιες ώστε να μπορούμε να διατυπώσουμε το θεώρημα Beck-Fiala.

Θεώρημα (Beck-Fiala): Έστω ένα πεπερασμένο σύνολο X και μια οικογένεια υποσυνόλων \mathcal{A} του X έτσι ώστε για κάθε x\in X υπάρχουν το πολύ t υποσύνολα A \in \mathcal{A} με x \in A. Τότε \mathrm{disc}(\mathcal{A}) \leqslant 2t-1.

Η σπουδαιότητα του θεωρήματος επαφίεται στο ότι το φράγμα είναι ανεξάρτητο τόσο του μεγέθους του X όσο και του μεγέθους του \mathcal{A}. Δυστυχώς όμως το θεώρημα δεν μας λέει όλα όσα θα θέλαμε να ξέρουμε υπό αυτές τις περιστάσεις. Το θεώρημα αποδείχθηκε το 1981 από τους József Beck και Tibor Fiala οι οποίοι στο ίδιο άρθρο διατύπωσαν την εικασία ότι υπάρχει σταθερά C ώστε \mathrm{disc}(\mathcal{A}) \leqslant C \sqrt{t}. Η εικασία είναι ακόμη εντελώς ανοικτή. Αυτήν την στιγμή το καλύτερο αποτέλεσμα προς αυτήν την κατεύθυνση (αλλά ακόμη πολύ μακριά από την εικασία) είναι του Boris Bukh ο οποίος απέδειξε ότι

\displaystyle{\mathrm{disc}(\mathcal{A}) \leqslant 2t-\log_2^{\ast}(t).}

Το \log^{\ast}(t) ορίζεται ο μικρότερος θετικός ακέραιος k ώστε \log_2(\log_2(\cdots \log_2(t))) \leqslant 1 όπου εφαρμόσαμε k λογαρίθμους.

Προχωράμε τώρα στην απόδειξη του θεωρήματος.

Θα ξεκινήσουμε από την συνάρτηση \chi_0 που είναι ταυτοτικά 0 στο X. Θα τροποποιούμε την συνάρτηση βήμα βήμα μέχρι να καταλήξουμε σε μια συνάρτηση \chi:X \to \{-1,1\} με τις ιδιότητες που θέλουμε.

Στο βήμα k θα έχουμε μια συνάρτηση \chi_k:X \to [-1,1]. Αν για κάποιο x\in X έχουμε \chi_k(x) = -1 ή \chi_k(x) = 1 θα ονομάζουμε αυτό το σημείο σταθερό. Η διαδικασία που θα ακολουθήσουμε δεν θα αλλάζει ποτέ την τιμή της \chi στα σταθερά σημεία. Δηλαδή αν \chi_k(x) = -1 ή \chi_k(x) = 1 τότε \chi_{\ell}(x) = \chi_k(x) για κάθε \ell \geqslant k.

Σε κάθε βήμα, θα ονομάζουμε ένα σύνολο A \in \mathcal{A} ασφαλές αν έχει το πολύ t σταθερά σημεία. Αλλιώς θα το ονομάζουμε μεταβλητό. Έστω ένα σύνολο A \in \mathcal{A} και έστω ότι το A έγινε από μεταβλητό ασφαλές στο βήμα k. Η διαδικασία που θα κάνουμε θα εξασφαλίζει ότι \sum_{x\in A} \chi_{\ell}(x) =0 για κάθε \ell \leqslant k+1. Αυτή η απαίτηση εξασφαλίζεται αρχικά αφού ξεκινάμε με την συνάρτηση που είναι ταυτοτικά 0.

Στο βήμα k θα πάρουμε (αν υπάρχει) ένα μεταβλητό σύνολο και θα τροποποιήσουμε την \chi_k στην \chi_{k+1} ώστε τουλάχιστον ένα επιπλέον σημείο του συνόλου να γίνει σταθερό.

Πριν να περιγράψουμε πως κάνουμε την τροποποίηση θα δείξουμε ότι αν όντως καταφέρουμε να εξασφαλίσουμε τις απαιτήσεις μας τότε \mathrm{disc}(\mathcal{A}) \leqslant 2t-1. Πράγματι εφόσον σε κάθε βήμα ο αριθμός των σταθερών σημείων αυξάνεται σε κάποια φάση η διαδικασία θα τελειώσει. Πιθανώς ακόμη να μην είναι όλα τα σημεία σταθερά. Για κάθε μη σταθερό σημείο απλά τροποποιούμε την συνάρτηση κατά το δοκούν ώστε να πάρουμε μια συνάρτηση \chi από το X στο \{-1,1\}. Έστω τώρα ένα σύνολο A \in \mathcal{A} το οποίο έγινε ασφαλές στο βήμα k. Από τις πιο πάνω συνθήκες έχουμε \sum_{x\in A} \chi_{k+1}(x) =0. Από κει και πέρα δεν μπορούμε να ελέγξουμε τις αλλαγές που έγιναν στα μη σταθερά σημεία του x\in A. Γνωρίζουμε όμως πως αφού το A είναι ασφαλές, τότε έχει το πολύ t μη σταθερά σημεία. Για κάθε τέτοιο σημείο είχαμε \chi_{k+1}(x) \in (-1,1) οπότε |\chi_{k+1}(x) - \chi(x)| < 2. Συνολικά λοιπόν παίρνουμε

\displaystyle{\sum_{x\in A}|\chi_{k+1}(x) - \chi(x)| < 2t}

οπότε είναι και \mathrm{disc}_{\chi}(A) < 2t. Επιπλέον αφού η ασυμφωνία είναι ακέραιος έχουμε \mathrm{disc}_{\chi}(A) \leqslant 2t-1. Αυτό όμως ισχύει για κάθε A \in \mathcal{A} οπότε είναι και \mathrm{disc}(\mathcal{A};\chi) \leqslant 2t-1 και άρα και \mathrm{disc}(\mathcal{A}) \leqslant 2t-1.

Μένει λοιπόν να δείξουμε ότι όντως μπορούμε να προχωρήσουμε την διαδικασία όπως ισχυριστήκαμε. Έστω ότι έχουμε ήδη ορίσει την \chi_k και έστω A_1,\ldots,A_r τα μεταβλητά σύνολα. Έστω επίσης x_1,\ldots,x_s τα μη σταθερά σημεία. Επειδή κάθε A_i (αφού είναι μεταβλητό) περιέχει τουλάχιστον t+1 μη σταθερά σημεία x_j και επειδή κάθε x_j περιέχεται στο πολύ t σύνολα A_i λαμβάνουμε ότι r < s. Για κάθε A_i κοιτάζουμε την γραμμική εξίσωση

\displaystyle{\sum_{j:x_j \in A_i}y_j = 0.}

Έχουμε συνολικά r γραμμικές εξισώσεις σε s > r αγνώστους. Οπότε θα υπάρχουν y_1,\ldots,y_s όχι όλα 0 που να είναι λύση του συστήματος. Για κάθε \lambda \in \mathbb{R} αν ορίσουμε

\displaystyle{\chi_{k+1}(x_j) = y_j + \lambda \chi_k(x_j)}

τότε ισχύει ότι

\displaystyle{\sum_{j:x_j \in A_i}\chi_{k+1}(x_j) = \sum_{j:x_j \in A_i}\chi_{k}(x_j).}

Για οποιοδήποτε \lambda αυτό μας εξασφαλίζει ότι για κάθε μεταβλητό σύνολο A_i είναι \sum_{x\in A_i} \chi_{k+1}(x) = 0. Το μόνο που πρέπει να ελεγχθεί είναι ότι \chi_{k+1}(x) \in [-1,1] για κάθε x και επιπλέον τουλάχιστον ένα σημείο έχει γίνει σταθερό. Υπάρχει όμως ελάχιστη τιμή του \lambda η οποία το επιτυγχάνει αυτό οπότε η απόδειξη ολοκληρώθηκε. \square

Με παρόμοιες ιδέες το φράγμα μπορεί να βελτιωθεί σε \mathrm{disc}(\mathcal{A}) \leqslant 2t-3 για t \geqslant 3. (Αυτό διατυπώθηκε ρητά από τους Bednarchak και Helm το 1997 αν και ουσιαστικά μπορεί να διαβαστεί και από το άρθρο των Beck και Fiala.)

Οι αναγκαίες τροποποιήσεις είναι οι εξής: Ένα σύνολο θα είναι ασφαλές αν έχει το πολύ t-1 μη σταθερά σημεία. Θα είναι μεταβλητό αν έχει τουλάχιστον t+1 μη σταθερά σημεία. Ακολουθούμε τώρα ακριβώς την ίδια διαδικασία μέχρι να μην μείνει κανένα μεταβλητό σύνολο. Με τον ίδιο τρόπο μπορούμε να εξασφαλίσουμε ότι την πρώτη φορά που ένα σύνολο A θα γίνει ασφαλές θα ισχύει ότι \sum_{x\in A}\chi(x) = 0. Στο τέλος για κάθε ασφαλές σύνολο θα έχουμε \sum_{x\in A}\chi(x) < 2t-2 και άρα \sum_{x\in A}\chi(x) \leqslant 2t-3. Τα μόνα άλλα σύνολα για τα οποία πρέπει να ελέγξουμε τι γίνεται είναι αυτά τα οποία δεν είναι ούτε ασφαλή, ούτε μεταβλητά. Έχουν δηλαδή ακριβώς t μη σταθερά σημεία. Στο τελευταίο όμως βήμα, αντί να κάνουμε την τροποποίηση των τιμών μη σταθερών x κατά το δοκούν ορίζουμε \chi(x) να ισούται με 1 προηγουμένως η τιμή του ήταν θετική και -1 αν ήταν μη αρνητική. Έτσι για τα σύνολα που δεν είναι ούτε ασφαλή ούτε μεταβλητέ θα έχουμε |\sum_{x\in A}\chi(x)| \leqslant t \leqslant 2t-3 όπως θέλαμε να δείξουμε.

Advertisements

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

Course Leader in Mathematics at UCLan Cyprus.
This entry was posted in 05D99 - None of the above, but in this section, 11K38 - Irregularities of distribution, discrepancy and tagged , . Bookmark the permalink.

Σχολιάστε

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

Λογότυπο WordPress.com

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

Φωτογραφία Twitter

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

Φωτογραφία Facebook

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

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

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

Σύνδεση με %s