1. Μπορούμε να χρωματίσουμε τις ακμές του πλήρους γραφήματος $K_N$ με δύο χρώματα έτσι ώστε το πλήθος των μονοχρωματικών τριγώνων που προκύπτει να είναι $\le \frac14 \binom{N}{3}$ (δηλ. το πολύ το ένα τέταρτο όλων των τριγώνων). Σχετικά εδώ.
2. Για κάθε $N$ μοναδιαία διανύσματα $v_1, v_2, \ldots, v_N \in \RR^2$ μπορούμε να επιλέξουμε πρόσημα $\epsilon_j = \pm1$ τέτοια ώστε να ισχύει $$ \Abs{\epsilon_1 v_1 + \cdots + \epsilon_N v_N} \le \sqrt{N}. $$ Δείτε [AS, §2.4, Balancing Vectors].
3. Για κάθε 3CNF, δηλ. για κάθε λογικό τύπο που είναι μια σύζευξη (ΚΑΙ) από διαζεύξεις (Ή) τριών μεταβλητών ή αρνήσεών τους, π.χ., κάτι της μορφής $$ (x_1 \lor x_2 \lor \overline{x_4}) \land (\overline{x_1} \lor x_5 \lor \overline{x_{10}}) \land \cdots \land (x_2 \lor x_3 \lor x_7), $$ μπορούμε να βρούμε μια ανάθεση τιμών Αληθής ή Ψευδής για τις λογικές μεταβλητές $x_j$ που καθιστά τουλάχιστον τα 7/8 από τα clauses (οι παρενθέσεις παραπάνω) αληθή. Δείτε εδώ, έως σελ. 8.
4. Πώς μπορούμε γρήγορα να ελέγξουμε αν δύο πολυώνυμα $p(x)$ και $q(x)$ βαθμού $\le d$ είναι ίσα ή όχι; Τα πολυώνυμα αυτά μπορεί να μας δίνονται με πεπλεγμένο τρόπο, όχι δηλ. απαραίτητα στη συνηθισμένη μορφή $$ p(x) = p_d x^d + p_{d-1}x^{d-1}+\cdots+p_1 x + p_0 $$ έτσι ώστε πρακτικά το μόνο που μπορούμε να κάνουμε για καθένα από αυτά είναι να τα υπολογίζουμε σε κάποια σημεία και να ελέγχουμε αν βγάζουν το ίδιο αποτέλεσμα. Πόσοι έλεγχοι χρειάζονται να γίνουν; Διαβάστε από [MU, §1.1, Application: Verifying Polynomial Identities].

1. Ας είναι $A, B, C$ τρεις $N \times N$ πίνακες αριθμών. Θέλουμε να ελέγξουμε αν $A\cdot B =C$. Δε θέλουμε να υπολογίσουμε το γινόμενο $A \cdot B$ μια και αυτό απαιτεί περίπου $N^3$ πράξεις που είναι πολύ. Δώσαμε ένα πιθανοθεωρητικό αλγόριθμο που με πιθανότητα αποτυχίας $\le 1/2$ και μόνο με $\sim N^2$ πράξεις μας απαντά ΝΑΙ ή ΟΧΙ αν είναι σωστή η παραπάνω ισότητα. Αν πει ΟΧΙ τότε αυτό είναι σίγουρα σωστό ενώ υπάρχει πιθανότητα (το πολύ 1/2) να μας πει ΝΑΙ ενώ η σωστή απάντηση είναι ΟΧΙ. Αν επαναλάβουμε τον αλγόριθμο αυτό $k$ φορές και πούμε NAI αν και μόνο αν μας απαντήσει ΝΑΙ και τις $k$ φορές τότε η πιθανότητα αποτυχίας μειώνεται στο $1/2^k$, το πολύ.

   [MU, §1.3, Application: Verifying Matrix Multiplication]

2. Ένα σύνολο $A$ λέγεται sum-free αν η εξίσωση $$ x+y=z $$ δεν έχει λύση με $x, y, z \in A$. Για παράδειγμα το σύνολο όλων των περιττών ακεραίων είναι sum-free. Αποδείξαμε το παρακάτω θεώρημα του Erdős:

   Θεώρημα: Αν $A$ είναι ένα σύνολο ακεραίων με $N$ στοιχεία τότε το $A$ έχει sum-free υποσύνολο με $\ge N/3$ στοιχεία.

   [J, §18.2, Sum-free sets]

3. Ξεκινήσαμε επίσης να περιγράφουμε τον πιθανοθεωρητικό αλγόριθμο για εύρεσης ελάχιστης τομής (min-cut) σε ένα γράφημα, που περιγράφεται στο [MU, §1.5, Application: A Randomized Min-Cut Algorithm], αλλά δεν προλάβαμε να κάνουμε την ανάλυση της μεθόδου και θα τα πούμε την επόμενη φορά.

1. Τελειώσαμε σήμερα την απόδειξη για τον αλγόριθμο εύρεσης min-cut σε γράφημα που είχαμε ξεκινήσει την προηγούμενη φορά.

   [MU, § 1.5, Application: A Randomized Min-Cut Algorithm]

2. Δείξαμε ότι για κάθε $n$ υπάρχει ένας προσανατολισμός των ακμών του γραφήματος $K_n$ (πλήρες γράφημα με $n$ κορυφές -- ένας τέτοιος προσανατολισμός ονομάζεται συνήθως tournament) τέτοιος ώστε να υπάρχει τουλάχιστον $\frac{n!}{2^{n-1}}$ διαφορετικές μεταθέσεις του $\Set{1, 2, \ldots, n}$ που να είναι συμβατές με τον προσανατολισμό (αυτό σημαίνει ότι η ακμή από κάθε στοιχείο της μετάθεσης στο επόμενό του έχει τον προσανατολισμό αυτό).

   [J, §18.1, Hamilton paths in tournaments]

3. Μιλήσαμε για αρκετή ώρα γενικά περί εύρεσης πρώτων, αλγόριθμους για έλεγχο πρώτων αριθμών, πιστοποίηση πρώτων αριθμών, και γενικότερα είπαμε κάποια βασικά πράγματα για υπολογιστική πολυπλοκότητα (περιγράψαμε, π.χ., τις κλάσεις P και NP).

   [Wikipedia, Primality test]

1. Δείξαμε τη μέθοδο coupling δύο ΤΜ, που μας επιτρέπει να λύνουμε κάποια προβλήματα υλοποιώντας δύο ΤΜ πάνω στο ίδιο πείραμα. Δείτε π.χ. στο [σημείο αυτό.]

2. Είδαμε τη μέθοδο reservoir sampling. Δείτε π.χ. [εδώ] ή [εδώ].

3. Ξεκινήσαμε να βλέπουμε την πιθανότητα ύπαρξης ενός $K_4$ (4 κορυφές που συνδέονται όλες με όλες) στο τυχαίο γράφημα $G(n, p)$ ($n$ κορυφές όπου κάθε δυνατή ακμή υπάρχει με πιθανότητα $p$, ανεξάρτητα από τις άλλες ακμές). Είδαμε ότι η κρίσιμη τιμή είναι η $p=n^{-2/3}$ και αυτό σημαίνει ότι αν το $p$ είναι έστω "λίγο" μεγαλύτερο από αυτό τότε θα υπάρχουν με μεγάλη πιθανότητα κάποια $K_4$ στο γράφημά μας ενώ αν το $p$ είναι έστω "λίγο" μικρότερο τότε με μεγάλη πιθανότητα δε θα υπάρχει κανένα αντίγραφο του $K_4$ στο γράφημά μας. Το τελευταίο το αποδείξαμε με την ανισότητα του Markov αλλά δεν τελειώσαμε την απόδειξη του πρώτου που απαιτεί χρήση της ανισότητας Chebyshev και άρα κάποιο υπολογισμό μιας διασποράς που είναι σχετικά πολύπλοκος (θα το τελειώσουμε την επόμενη φορά).

   [J, §1.5]

1. Συνεχίσαμε από την προηγούμενη φορά και τελειώσαμε τη μελέτη της ύπαρξης ύπαρξης ενός $K_4$ (4 κορυφές που συνδέονται όλες με όλες) στο τυχαίο γράφημα $G(n, p)$ ($n$ κορυφές όπου κάθε δυνατή ακμή υπάρχει με πιθανότητα $p$, ανεξάρτητα από τις άλλες ακμές). Είδαμε ότι η κρίσιμη τιμή είναι η $p=n^{-2/3}$ και αυτό σημαίνει ότι αν το $p$ είναι έστω "λίγο" μεγαλύτερο από αυτό τότε θα υπάρχουν με μεγάλη πιθανότητα κάποια $K_4$ στο γράφημά μας ενώ αν το $p$ είναι έστω "λίγο" μικρότερο τότε με μεγάλη πιθανότητα δε θα υπάρχει κανένα αντίγραφο του $K_4$ στο γράφημά μας. Το τελευταίο το αποδείξαμε με την ανισότητα του Markov και τελειώσαμε την απόδειξη του πρώτου που απαιτεί χρήση της ανισότητας Chebyshev και άρα κάποιο υπολογισμό μιας διασποράς που είναι σχετικά πολύπλοκος.

   [J, §21.5]

2. Ας είναι $k$ το μέγιστο μέγεθος ενός συνόλου ακεραίων $A\subseteq \Set{1, 2, \ldots, N}$ που υπάρχει τέτοιο ώστε όλα τα αθροίσματα που μπορούμε να φτιάξουμε χρησιμοποιώντας τα στοιχεία του $A$ το πολύ μια φορά το καθένα να είναι διαφορετικά: $$ \sum_{s \in S} s,\ \ \text{ για $S \subseteq A$, είναι όλα διαφορετικά}. $$ Είναι σχετικά εύκολο να δείξει κανείς ότι $$ k \le \log_2 N + \log_2 \log_2 N + C,\ \ \text{ όπου $C$ μια σταθερά.} $$ Χρησιμοποιώντας κατάλληλα την ανισότητα Chebyshev βελτιώσαμε την παραπάνω ανισότητα όσον αφορά το δεύτερο μεγαλύτερο όρο της: $$ k \le \log_2 N + \frac12 \log_2 \log_2 N + C,\ \ \text{ όπου $C$ μια σταθερά.} $$

   [AS, §4.6]

3. Ξεκινήσαμε να βλέπουμε τις ανισότητες απόκλισης τύπου Chernoff. Είδαμε χωρίς απόδειξη την ανισότητα που εμφανίζεται στο [MU, Corollary 4.6] και την εφαρμόσαμε μαζί με τις ανισότητες Markov και Chebyshev στον τυχαία μεταβλητή $X$ που μετράει πόσες κορώνες φέραμε όταν ρίξαμε ένα τίμιο νόμισμα $N$ φορές. Είδαμε ότι η ανισότητα Chernoff δίνει δραματικά καλύτερα άνω φράγματα για την ανισότητα απόκλισης $$ \Prob{ \Abs{X-\Mean{X}} \ge \lambda N }, $$ για μεγάλες τιμές του $N$.

1. Είδαμε τις βασικές ανισότητες απόκλισης τύπου Chernoff για αθροίσματα ανεξαρτήτων ΤΜ που παίρνουν τιμές 0 ή 1 (ή και $\pm 1$ με ίση πιθανότητα) και το πώς αποδεικνύονται. Αρχίσαμε να αναφέρουμε κάποιες εφαρμογές και ορίσαμε δύο έννοιες πυκνότητας για υποσύνολα των ακεραίων (τις πυκνότητες που είναι αναλλοίωτες κατά μεταφορές και τις κεντραρισμένες πυκνότητες). Είδαμε διάφορα παραδείγματα για συγκεκριμένα σύνολα. Τέλος είδαμε πώς ένα τυχαίο σύνολο ακεραίων (όπου κάθε ακέραιος είναι ή όχι μέσα στο σύνολο, ανεξάρτητα από τους άλλους ακεραίους, και την πιθανότητα που εμείς επιθυμούμε) μπορεί να μας δώσει ένα υποσύνολο ακεραίων με (κεντραρισμένη) πυκνότητα αυτή που θέλουμε.

   [MU, §4.2]

1. Είδαμε ξανά την απόδειξη που είχαμε δει και την προηγούμενη φορά, ότι ένα τυχαίο σύνολο ακεραίων $A$ με πιθανότητα $\Prob{k \in A}=p$ για κάθε ακέραιο $k$ θα έχει σχεδόν σίγουρα ασυμπτωτική πυκνότητα ίση με $p$. Αυτό είναι μια εύκολη εφαρμογή της ανισότητας Chernoff για αθροίσματα ανεξαρτήτων δεικτριών (δηλ. με τιμές 0 ή 1) τυχαίων μεταβλητών. Είδαμε επίσης ότι αν μας ενδιαφέρει η ομοιόμορφη ή Banach πυκνότητα τότε το σύνολο $$ \Set{\Floor{k \frac{1}{p}}:\ k \in \ZZ} $$ έχει ομοιόμορφη πυκνότητα $p$.

2. Είδαμε πώς μπορούμε να χρωματίσουμε ένα σύνολο από $n$ σημεία με δύο χρώματα έτσι ώστε κάθε ένα από $m$ δεδομένα υποσύνολα αυτού έχουν μικρό "ανισοχρωματισμό", μικρή δηλ. διαφορά των δύο χρωμάτων. Ο τυχαίος χρωματισμός το πετυχαίνει αυτό [MU, §4.4].

3. Ξεκινήσαμε να βλέπουμε την απόδειξη του παρακάτω θεωρήματος του Erdos:

   Θεώρημα Υπάρχει σύνολο $E \subseteq \NN$ τέτοιο ώστε για $n$ αρκετά μεγάλο να ισχύει $$ C_1 \log n \le r_E(n) \le C_2 \log n, $$ για δύο σταθερές $C_1, C_2$, όπου $$ r_E(n) = \Set{(a, b) \in E \times E: a \le b \ \&\ n = a+b}, $$ είναι το πλήθος των αναπαραστάσεων του φυσικού αριθμού $n$ ως άθροισμα δύο στοιχείων του $E$ [K, §1.2.1].

1. Τελειώσαμε σήμερα την απόδειξη του θεωρήματος του Erdos για ασυμπτωτικές προσθετικές βάσεις που είχαμε ξεκινήσει την προηγούμενη φορά [K, §1.2.1].

2. Είδαμε τη μέθοδο των υπό συνθήκη πιθανοτήτων (ή υπό συνθήκη μέσων τιμών) για μετατροπή μιας πιθανοθεωρητικής απόδειξης (ή ενός πιθανοθεωρητικού αλγορίθμου) σε ντετερμινιστική κατασκευή. Η μέθοδος αυτή συνίσταται στη βήμα προς βήμα επιλογή των τιμών των ΤΜ που υπάρχουν στην απόδειξη που θέλουμε να μετατρέψουμε φροντίζοντας κάθε φορά να μη μειώνουμε τις πιθανότητες επιτυχίας με τις τιμές που επιλέγουμε. Είδαμε τη μέθοδο ακριβώς όπως παρουσιάζεται στο [Κ, §1.3].

1. Είδαμε ένα ακόμη παράδειγμα της μεθόδου των υπό συνθήκη πιθανοτήτων για derandomization [MU, §6.3].
2. Είδαμε πώς σε μερικές πιθανοθεωρητικές κατασκευές (ή αποδείξεις) τα αντικείμενα που κατασκευάζονται με τυχαίο τρόπο δεν\ έχουν όλες τις ιδιότητες που ζητάμε και χρειάζεται έπειτα το τυχαίο αντικείμενο αυτό να τροποποιηθεί (συνήθως με ντετερμινιστικό τρόπο) για να έχει τις ιδιότητες που θέλουμε. Αυτή η τροποποίηση πρέπει να αναλυθεί με πιθανοθεωρητικό τρόπο για να αποδειχθεί ότι δουλεύει. Είδαμε τα εξής δύο παραδείγματα [MU, §6.4]: (α) κατασκευή ενός μεγάλου ανεξάρτητου συνόλου κορυφών σε ένα γράφημα και (β) κατασκευή γραφημάτων με μεγάλο girth (μήκος του ελάχιστου κύκλου).
3. Κάναμε μια σύντομη εισαγωγή στην έννοια της εντροπίας μιας κατανομής [MU, §10.1].

Ορίσαμε την έννοια της εντροπίας και είδαμε διάφορες στοιχειώδεις (και πολύ διαισθητικές) ιδιότητές της. Έπειτα χρησιμοποιήσαμε αυτά για να αποδείξουμε δύο προτάσεις στη συνδυαστική και στη γεωμετρία [G, §1, 2, 3.1, 3.3].

1. Είδαμε ότι η εντροπία μιας κατανομής είναι ένα μέτρο της "πληροφορίας" που παίρνουμε από την πηγή αυτή με την εξής έννοια [MU, Theorem 10.6]: αν μια πηγή μας παράγει ανεξάρτητα δείγματα μιας Bernoulli ΤΜ με τιμές 0 και 1 και πιθανότητα του 1 να είναι $p>1/2$ τότε η πληροφορία που χρειάζεται να μεταδώσουμε για να μεταφέρουμε ακριβώς ένα "σήμα" $X_1, X_2, \ldots, X_n$ είναι $\sim H(p) n$.
2. Μιλήσαμε για prefix κώδικες και αποδείξαμε την ανισότητα του Kraft (δείτε [MU, Exercise 10.15] και εδώ).