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

Ιουλίου 21, 2009

Τομές συνόλων

Filed under: Λυμένα Προβλήματα,Με υπόδειξη — Mihalis Kolountzakis @ 10:03 πμ

Ας είναι A_j \subseteq X,\ j=1,2,\ldots,N, κάποια σύνολα μεγέθους k το καθένα, τέτοια ώστε η τομή οποιωνδήποτε k+1 από τα σύνολα A_j είναι μη κενή.

Τότε και η τομή όλων των A_j είναι μη κενή.

Advertisements

3 Σχόλια »

  1. Υπόδειξη:

    Ας είναι A_1 = \{x_1, x_2, \ldots, x_k\}. Μπορεί το x_i, i=1,2,\ldots,k, να ανήκει και σε όλα τα άλλα A_j, j=2,3,\ldots,N;

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Ιουλίου 29, 2009 @ 9:47 πμ

  2. δεν γνωρίζω latex και απλά θα περιγράψω
    δεχόμαστε οτι η τομή όλων είναι κενή.Τότε θα υπάρχει τουλάχιστον ενα σύνολο απο τα υπόλοιπα που δεν θα περιέχει το χ1 του Α1,τουλάχιστον ενα σύνολο που δε θα περιέχει το χ2 του Α1 κλπ ,τουλάχιστον ένα σύνολο που δεν θα περιέχει το χκ του Α1.
    Αν το ελάχιστο πλήθος αυτών των συνόλων είναι κ ,τότε αυτά με το Α1 είναι μια κ+1αδα που προφανώς θα είναι κενή ,άτοπο
    Αν πάλι είναι μικρότερο του κ ,τότε μπορούμε να επιλέξουμε μια κ+1αδα που είναι κενή άτοπο
    π.χ Αν όλα τα στοιχεία του Α1 έκτός του χκ δεν ανήκουν στο Α2 και το χκ δεν ανήκει στο Α3,τότε μια οποιαδήποτε κ+1αδα που περιέχει τα Α1,Α2,Α3 θα είναι κενή πράγμα άτοπο

    Μου αρέσει!

    Σχόλιο από mt58 — Αύγουστος 26, 2009 @ 4:51 μμ

  3. Πολύ ωραία, αυτή είναι η λύση.

    Παρατηρείστε επίσης ότι δεν είναι απαραίτητο όλα τα σύνολα A_j να είναι μεγέθους k, αλλά αρκεί ένα από αυτά να είναι (αυτό που θα παίξει το ρόλο του A_1 στην απόδειξη).

    Ιδιότητες αυτού του τύπου λέγονται «τύπου Helly», από το κλασικό θεώρημα του Helly για κυρτά σύνολα που λέει ότι αν έχουμε μια οικογένεια κυρτων συνόλων στο {\mathbb R}^d κάθε d+1 από τα οποία έχουν μη κενή τομή τότε η τομή όλων είναι μη κενή.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Αύγουστος 26, 2009 @ 7:06 μμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

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

Λογότυπο WordPress.com

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

Φωτογραφία Twitter

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

Φωτογραφία Facebook

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

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

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

Σύνδεση με %s

Δημιουργήστε ένα δωρεάν ιστότοπο ή ιστολόγιο στο WordPress.com.

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