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

13 Οκτωβρίου, 2013

Διασπάσεις

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

venn

Ας είναι {\mathcal F} μια πεπερασμένη οικογένεια από υποσύνολα ενός συνόλου X. Αν είναι E \subseteq X ένα πεπερασμένο σύνολο μεγέθους k, λέμε ότι η οικογένεια {\mathcal F} διασπά το σύνολο E αν ο αριθμός των διαφορετικών συνόλων

F\cap E, όπου F \in {\mathcal F},

ισούται με 2^k. Όλα δηλ. τα υποσύνολα του E «φτιάχνονται» από τα σύνολα της {\mathcal F} περιορισμένα στο E.

Δείξτε ότι κάθε οικογένεια {\mathcal F} μεγέθους N=|{\mathcal F}| διασπά τουλάχιστον N διαφορετικά υποσύνολα του X.

4 Σχόλια »

  1. Με τις ομολογουμένως περιορισμένες γνώσεις μου από extremal set theory combinatorics ,έχω την εντύπωση πως το ζητούμενο είναι ταυτόσημο με το λήμμα : http://en.wikipedia.org/wiki/Sauer%E2%80%93Shelah_lemma
    Στην περίπτωσή μας για το σύνολο K ={1,2,…,k} ,για να διασπάσουμε ένα σύνολο μεγέθους k ,χρειαζόμαστε τουλάχιστον 2^k σύνολα. Αλλά ,πόσα σύνολα μας εγγυώνται τη διάσπαση ενός συνόλου με k στοιχεία; Την απάντηση (και στο δικό μας πρόβλημα επομένως) δίνει το θεώρημα Sauer-Shelah:
    Aν |F| >C(n,0)+C(n,1)+…+C(n,k) , τότε υπάρχει ένα σύνολο S με |S| =k+1 έτσι ώστε το F να διασπά το S.

    Πέρα από την απόδειξη-βάσει Επαγωγής- που υπάρχει στο άρθρο της Βικιπαίδειας, παραθέτω τη δικιά μου «μπακάλικη» σκέψη: Αν κάθε οικογένεια διασπά τουλάχιστον τόσα σύνολα όσα το μέγεθός της, τότε μια οικογένεια που ικανοποιεί την :|F| >C(n,0)+C(n,1)+…+C(n,k) διασπά ΠΕΡΙΣΣΟΤΕΡΑ σύνολα απότι αυτό το άθροισμα! Αλλά τότε, θα έπρεπε να διασπά ένα σύνολο με μέγεθος μεγαλύτερο από k, επειδή δεν υπάρχουν αρκετά υποσύνολα του {1,2,…,n} με μέγεθος το πολύ k.

    Στο σχετικό γνωστικό πεδίο ανήκει και το θεώρημα Eρντος -Κο-Ράντο , που έχω την αίσθηση πως συνδέεται (ίσως να είναι και το «κλειδί») στο ωραίο πρόβλημα της «πεθεράς» (?) 🙂
    Γιώργος Ριζόπουλος
    Δρ.Πολιτικός Μηχανικός

    Μου αρέσει!

    Σχόλιο από Rizopoulos Georgios — 6 Νοεμβρίου, 2013 @ 5:07 μμ

  2. Το ζητούμενο συνεπάγεται το λήμμα Sauer-Shelah με την απόδειξη που αναφέρεις στη 2ή σου παράγραφο. Δε βλέπω άμεσα γιατί το λήμμα Sauer-Shelah συνεπάγεται το ζητούμενο. Η επαγωγική απόδειξη που υπάρχει στο άρθρο της Wikipedia είναι βεβαίως σωστή, και εύκολη.

    Για την πεθερά ίσως να έχεις δίκιο.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — 6 Νοεμβρίου, 2013 @ 8:48 μμ

  3. Ναι, όντως το ζητούμενο είναι «ισχυρότερο» του Λήμματος Ζάουερ-Σέλα. Νομίζω ότι μπορούμε να χρησιμοποιήσουμε το στάνταρ «κολπάκι» της επαγωγής ,δηλαδή να θεωρήσουμε τα σύνολα που περιέχουν το ‘1’ και αυτά που δεν περιέχουν το «1» και να εφαρμόσουμε επαγωγικά επιχειρήματα. (αυτό νομίζω κάνει ουσιαστικά και η Wiki σε τροποποιημένη μορφή), οπότε μ’αυτόν τον μπούσουλα:
    Πρέπει να δείξουμε ότι κάθε οικογένεια F διασπά τουλάχιστον τόσα υποσύνολα όσα το | F |. Ας θεωρήσουμε την υποοικογένεια (ελπίζω να είναι δόκιμη η ορολογία μου ,εννοώ subfamily) έστω F0, της οικογένειας F ,τα σύνολα που δεν περιέχουν το ‘1’ . Eπαγωγή (by Induction) : η F0 διασπά τουλάχιστον τόσα υποσύνολα του Κ’={2,3,4,…,κ} όσα και η | F0 |. Κατόπιν θεωρούμε το F1 = {S ανήκει στο F: 1 ανήκει στο S}, και {F’1 = {S\{1}: S ανήκει στο F}, 1 ανήκει στο S }. Eπαγωγή: η F’1 διασπά τόσα υποσύνολα του {2,3,…,k} όσος και ο πληθάριθμός της (cardinality)
    Τα υποσύνολοα του Κ’ που διασπώνται από τις F και F’ έχουν άθροισμα κατ’ελάχιστον : |F| . ( |F0| + |F’1|= |F| ), kai κάθε υποσύνολο του Κ’ που διασπάται από το F’1 ,διασπάται και από το » F1 υποσύνολο του F».
    ΥΓ. Αν υποτεθεί ότι μπορέι να υπάρχουν Ε υποσύνολα του Κ’ που να διασπώνται από τα F0 KAI F’1, παρατηρούμε ότι σ’αυτή την περίπτωση και το Ε και «Ε ένωση {1}» διασπώνται απο το F . Oπότε ,είμαστε Ο.Κ. (ελπίζω…)

    Μου αρέσει!

    Σχόλιο από Rizopoulos Georgios — 6 Νοεμβρίου, 2013 @ 10:51 μμ

  4. Ναι, έτσι είναι. Το πιο λεπτό σημείο της απόδειξης είναι η τελευταία πρόταση που έχεις ως υστερόγραφο.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — 9 Νοεμβρίου, 2013 @ 11:34 πμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Blog στο WordPress.com.