Προβλήματα Μαθηματικών

Ιουλίου 24, 2009

Τομές συνόλων όλες ίδιες

Filed under: Λυμένα Προβλήματα — Mihalis Kolountzakis @ 10:04 μμ

Έστω {1 \le k \le n} και σύνολα A_1,\ldots,A_m \subseteq \{1,2,\ldots,n\} με την ιδιότητα ότι

|A_i \cap A_j| = k για κάθε i \neq j.

Τότε m \le n.

Advertisements

6 Σχόλια »

  1. Μήπως πρέπει να προστεθεί και η συνθήκη ότι τα A_1,A_2,\ldots ,A_m είναι ανά δύο διαφορετικά μεταξύ τους;

    Μου αρέσει!

    Σχόλιο από stedes — Ιουλίου 27, 2009 @ 12:37 μμ

  2. Προφανώς.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Ιουλίου 27, 2009 @ 12:39 μμ

  3. Προσπάθησα να το δω συνδυαστικά το συγκεκριμένο πρόβλημα αλλά μια φυσική απόδειξη (κατά τη γνώμη μου) βασίζεται στην οπτική γωνία του να δούμε τα σύνολα ως διανύσματα και να ψάξουμε για γραμμική ανεξαρτησία. Πιο συγκεκριμένα (αν δεν κάνω κάπου λάθος):

    Έστω για το σύνολο A_i το χαρακτηριστικό του διάνυσμα x_i , που έχει στην θέση j 1 αν το στοιχείο j περιέχεται στο σύνολο A_i ειδάλλως x_j=0. Από τη στιγμή που έχουμε m τέτοια σύνολα, για να δείξουμε το επιθυμητό αρκεί να αποδείξουμε οτι είναι γραμμικώς ανεξάρτητα αυτά τα διανύσματα. Ο λόγος είναι το από επιχείρημα από τη γραμμική άλγεβρα οτι αν έχουμε m γραμμικώς ανεξάρτητα διανύσματα σε ένα n-διάστατο διανυσματικό χώρο (το σώμα μας εδώ είναι το Galois Field {\cal F}_2) τότε m \leq n.

    Ας θεωρήσουμε λοιπόν οτι δεν είναι ανεξάρτητα. Τότε σημαίνει οτι υπάρχουν συντελεστες a_i τ.ώ να ισχύει η εξίσωση \sum_{i=1}^m a_ix_i=0 και ταυτόχρονα να μην είναι όλα τα a_i 0. Υψώνοντας τη σχέση αυτή στο τετράγωνο και αναπτύσσοντας το, παίρνουμε το εξής:

    (\sum_i a_i x_i)^2=0 \rightarrow \sum_i \sum_{j \neq i} a_i a_j x_i^T x_j = \sum_{i=1}^m a_i^2 x_i^Tx_i + \sum_i \sum_j a_i a_j x_i^T x_j  = \sum_{i=1}^m a_i^2 |A_i| +\sum_i \sum_{j \neq i} a_i a_j k = \sum_{i=1}^m a_i^2 ( |A_i| - k) + k (\sum_i a_i)^2=0

    H τελευταία εξίσωση μας δίνει οτι τα a_i‘s είναι 0, δεδομένου οτι |A_i| \geq k. Επίσης με βάση το επεξηγηματικό σας σχόλιο «προφανώς» προκύπτει οτι το πολύ ένα A_i θα μπορούσε να έχει μέγεθος ίσο με k, ειδάλλως θα είχαμε 2 ίδια σύνολα. Και λίγα επεξηγηματικά σχόλια για το κάθε βήμα παραπάνω: x_i^Tx_i=|A_i| και x_i^Tx_j=k για i \neq j (αφού έχουμε 0,1 στο x_i). Τέλος προσέθεσα και αφαίρεσα τα απαιτούμενα για να συμπληρώσω το τετράγωνο (\sum_i a_i)^2.

    Μου αρέσει!

    Σχόλιο από Charalampos Tsourakakis — Αύγουστος 5, 2009 @ 2:54 μμ

  4. Διορθώσεις typos:
    1) «από επιχείρημα» \rightarrow απλό
    2) Eπίσης μετά το βέλος ο όρος στην αριστερή μεριά της εξίσωσης και ο δεξιός όρος στην δεξιά μεριά (πριν το τελευταίο = στην ίδια γραμμή) πρέπει να αλλάξουν θέση.

    Μου αρέσει!

    Σχόλιο από Charalampos Tsourakakis — Αύγουστος 5, 2009 @ 3:00 μμ

  5. Σωστά. Όμως όχι πάνω από το σώμα {\mathbb F}_2 αλλά πάνω από τους πραγματικούς ή τους ρητούς, αφού θέλεις να χρησιμοποιήσεις ότι μερικά πράγματα είναι θετικά.

    Πληροφοριακά, αυτή ονομάζεται ανισότητα του Fisher.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Αύγουστος 5, 2009 @ 4:47 μμ

  6. Αν και σε όσα βιβλία έχω δει την λένε Fisher’s inequality, κανονικά θα έπρεπε να λέγεται Majumdar’s Inequality. Ο Fisher απέδειξε την ανισότητα μόνο στην περίπτωση που τα σύνολα A_i έχουν όλα τον ίδιο αριθμό στοιχείων. (Η περίπτωση k=1 της ανισότητας είναι των de Bruijn και Erdos.)

    Μια διαφορετική απόδειξη, πάλι χρησιμοποιώντας γραμμική άλγεβρα, είναι να υποθέσουμε πως m > n και να κοιτάξουμε τον m \times m πίνακα Β που ορίζεται ως B_{ij} = 1 αν x_i \in A_j και B_{ij} = 0 διαφορετικά. Εξ’ ορισμού οι τελευταίες m-n σειρές του πίνακα είναι τα μηδενικά διανύσματα. Τότε έχουμε

    \displaystyle B^TB = \begin{pmatrix} |A_1| & k & \cdots & k \\ k & |A_2| & \cdots & k \\ \vdots & \vdots & \ddots & \vdots \\ k & k & \cdots & |A_m|  \end{pmatrix}.

    Επειδή ο πίνακας Β έχει ορίζουσα 0 (αφού έχει τουλάχιστον μια μηδενική σειρά) τότε και ο πίνακας B^TB πρέπει να έχει ορίζουσα 0. Αλλά μπορούμε να υπολογίσουμε ότι η ορίζουσα ισούται με

    \displaystyle (|A_1| - k) \cdots (|A_m| - k) \left( \frac{k}{|A_1|-k} \cdots + \frac{k}{|A_m|-k} + 1 \right) > 0.

    (Μπορούμε να υποθέσουμε όπως εξηγεί και ο Χαράλαμπος ότι |A_i| \geqslant k και το πολύ ένα από τα |A_i| έχει μέγεθος k. Αν π.χ. |A_m| = k, τότε η ορίζουσα ισούται με \displaystyle k(|A_1| - k) \cdots (|A_{m-1}| - k) > 0.)

    Για τον υπολογισμό της ορίζουσας: Αφαίρεσα την τελευταία σειρά από όλες τις υπόλοιπες και μετά αφαίρεσα από την τελευταία στήλη κατάλληλα γινόμενα κάθε άλλης στήλης ώστε ο πίνακας να γίνει κάτω τριγωνικός.

    Μου αρέσει!

    Σχόλιο από Δημήτρης — Αύγουστος 10, 2009 @ 6:08 μμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Συνδεθείτε για να δημοσιεύσετε το σχόλιο σας:

Λογότυπο WordPress.com

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

Φωτογραφία Twitter

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

Φωτογραφία Facebook

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

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

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

Σύνδεση με %s

Blog στο WordPress.com.

Αρέσει σε %d bloggers: