Μεγιστικὴ ὑποκλάση τοῦ δυναμοσυνόλου

Γ.-Σ. Σμυρλής · #1

ΠΡΟΒΛΗΜΑ. Ἔστω $\mathscr P$ τὸ δυναμοσύνολο τοῦ $\{1,2,\ldots,n\}$ καὶ $\mathcal S\subset\mathscr P$ , μὲ τὴν ἰδιότητα
$\displaystyle{ A,B\in \mathcal S\quad\Longrightarrow\quad A\cap B\ne\varnothing. }$
Ἄν τὸ $\mathcal S$ εἶναι μεγιστικὸ μὲ αὐτὴ τὴν ἰδιότητα, δείξατε ὅτι $|\mathcal S|=2^{n-1}$ .

ΣΗΜΕΙΩΣΗ. Τὸ $\mathcal S$ εἶναι μεγιστικὸ μὲ αὐτὴ τὴν ἰδιότητα σημαίνει ὅτι, ἄν $\mathcal S\subsetneqq \mathcal T\subset \mathscr P$ , τότε ὑπάρχουν $A,B\in \mathcal T$ , ὥστε $A\cap B=\varnothing$ .

ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ · #2

Γ.-Σ. Σμυρλής έγραψε:ΠΡΟΒΛΗΜΑ. Ἔστω $\mathscr P$ τὸ δυναμοσύνολο τοῦ $\{1,2,\ldots,n\}$ καὶ $\mathcal S\subset\mathscr P$ , μὲ τὴν ἰδιότητα
$\displaystyle{ A,B\in \mathcal S\quad\Longrightarrow\quad A\cap B\ne\varnothing. }$
Ἄν τὸ $\mathcal S$ εἶναι μεγιστικὸ μὲ αὐτὴ τὴν ἰδιότητα, δείξατε ὅτι $|\mathcal S|=2^{n-1}$ .

ΣΗΜΕΙΩΣΗ. Τὸ $\mathcal S$ εἶναι μεγιστικὸ μὲ αὐτὴ τὴν ἰδιότητα σημαίνει ὅτι, ἄν $\mathcal S\subsetneqq \mathcal T\subset \mathscr P$ , τότε ὑπάρχουν $A,B\in \mathcal T$ , ὥστε $A\cap B=\varnothing$ .

Νομίζω ότι είναι απλό.

θα δείξουμε ότι σε ένα μεγιστικό θα ανήκει ένα ακριβώς από τα

,

.

Είναι προφανές ότι και τα δύο δεν ανήκουν συγχρόνως.

Αν υποθέσουμε ότι και τα δύο δεν ανήκουν τότε υπάρχουν στο μεγιστικό K,L

με

$A\cap K=0,(X-A)\cap L=0$ που οδηγεί σε άτοπο γιατί $K\cap L\neq 0$

Αρα ακριβώς ένα από τα

,

ανήκει στο μεγιστικό οπότε έχει τα μισά υποσύνολα του συνόλου.

Ζητώ προκαταβολικά συγνώμμη για την εμφάνηση αλλά γράφω από μικρό υπολογιστή.

Γ.-Σ. Σμυρλής · #3

Σωστά

ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ · #4

Γ.-Σ. Σμυρλής έγραψε:Σωστά

Για αυτό ήμουν σχεδόν σίγουρος. Η αλήθεια είναι ότι το έλυσα χωρίς να καταλάβω.
Νομίζω ότι έχει ενδιαφέρον τι δομή έχουν αυτές.
Θα γράψω κάποια πράγματα όταν βρεθώ σε κανονικό υπολογιστή.
Από που προέρχεται το πρόβλημα;

#5

ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ έγραψε: Νομίζω ότι έχει ενδιαφέρον τι δομή έχουν αυτές.

Είναι τα λεγόμενα ultrafilers. Στις Τοπολογίες χρησιμοποιούν συνήθως δίκτυα (nets)
για την σύγκλιση αλλά αραιά και που εργάζονται στην θέση τους με filters και ultrafilters.
Αν θυμάμαι καλά, η Toπολογία του Bourbaki εργάζεται με filters και ultrafilters.
To κλασικό βιβλίο Ultafilters είναι βέβαια των Νεγρεπόντη, Comfort.

ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ · #6

Mihalis_Lambrou έγραψε:
ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ έγραψε: Νομίζω ότι έχει ενδιαφέρον τι δομή έχουν αυτές.
Είναι τα λεγόμενα ultrafilers. Στις Τοπολογίες χρησιμοποιούν συνήθως δίκτυα (nets)
για την σύγκλιση αλλά αραιά και που εργάζονται στην θέση τους με filters και ultrafilters.
Αν θυμάμαι καλά, η Toπολογία του Bourbaki εργάζεται με filters και ultrafilters.
To κλασικό βιβλίο Ultafilters είναι βέβαια των Νεγρεπόντη, Comfort.

Καλησπέρα Μιχάλη. Δεν νομίζω,
https://en.wikipedia.org/wiki/Ultrafilter

Αν πάρουμε ένα σύνολο με 2n+1

στοιχεία τα υποσύνολά του που έχουν περισσότερα από

στοιχεία αποτελουν ένα μεγιστικό όπως όρισε ο Γιώργος αλλά δεν είναι filters η ultrafilters.
Βέβαια αν πάρουμε ένα σύνολο με

στοιχεία και όλα τα υποσύνολά του που περιέχουν ένα συγκεκριμένο στοιχείο τότε αυτό είναι μεγιστικό και αν δεν κάνω λάθος ultrafilters.

Γ.-Σ. Σμυρλής · #7

Τα ὑπερφίλτρα πράγματι ἔχουν τὴν μεγιστικότητα ποὺ ἀπαιτεῖ ἡ ἄσκηση. Ὅμως, ἐνδέχεται ἕνα μεγιστικὸ σύνολο ποὺ ἱκανοποιεῖ τὰ δεδομένα τῆς ἀσκήσεως νὰ μὴν εἶναι ὑπερφίλτρο.

Παράδειγμα: n=3

, $\,\,\mathcal S=\big\{\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\big\}$ .

#8

Η αρχική άσκηση είναι μια από τις πρώτες ασκήσεις που συναντάει κανείς σε ένα τομέα της συνδυαστικής που ονομάζεται extremal set theory. Σε αυτό τον τομέα οι ερωτήσεις που συναντάμε είναι της μορφής: «Ποιο είναι το μεγαλύτερο μέγεθος μιας οικογένειας υποσυνόλων του $\{1,2,\ldots,n\}$ η οποία να έχει μια συγκεκριμένη ιδιότητα;»

Ακόμη όμως και από αυτήν την απλή ερώτηση πηγάζουν δύσκολα ερωτήματα. Π.χ. αφού βρήκαμε ότι το μέγιστο μέγεθος είναι $2^{n-1}$ και μάλιστα αποδείξαμε το πιο ισχυρό ότι κάθε μεγιστική οικογένεια είναι μέγιστη, η επόμενη ερώτηση είναι να περιγράψουμε όλες αυτές τις μέγιστες οικογένειες και αν είναι δυνατόν να τις μετρήσουμε.

Αυτά τα δύο ερωτήματα στην συγκεκριμένη περίπτωση είναι ανοικτά. Ένα πράγμα που γνωρίζουμε είναι το εξής:

Ας πάρουμε την περίπτωση n = 2m

άρτιος. Μια μέγιστη οικογένεια είναι να πάρουμε όλα τα σύνολα με τουλάχιστον m+1

στοιχεία μαζί με ένα σύνολο από κάθε ζεύγος συμπληρωματικών συνόλων μεγέθους

. Είναι εύκολο να δειχθεί ότι αυτή είναι μέγιστη οικογένεια και ότι υπάρχουν $2^{\frac{1}{2}\binom{2m}{m}}$ τέτοιες οικογένειες.

Έχει αποδειχθεί ότι ασυμπτωτικά υπάρχουν $2^{\frac{(1+o(1))}{2}\binom{2m}{m}}$ μέγιστες οικογένειες. Δηλαδή υπό μια έννοια οι πλείστες μέγιστες οικογένειες μοιάζουν με αυτήν την πιο πάνω παραγράφου. (Αν και αυτό δεν είναι ακριβώς σωστό αφού το (1+o(1))

είναι στον εκθέτη.)

Είχα γράψει κάποια πράγματα για αυτό το πρόβλημα εδώ τον καιρό που ασχολούμουν με το blog μου.

ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ · #9

Να δώσω ακόμα μια μορφή τέτοιου συνόλου.

Εστω σύνολο

με $\left | A \right |=n$

Παίρνουμε υποσύνολο του

με $\left | B \right |=2k+1< n$

Παίρνουμε όλα τα υποσύνολα του

που έχουν περισσότερα από

στοιχεία.

Τα σύνολα είναι $S\cup D$

όπου $S\subset B$ με περισσότερα από

στοιχεία και $D\subseteq A-B$

BAGGP93 · #10

Μπορούμε να γενικεύσουμε το αρχικό πρόβλημα.

Έστω $\displaystyle{\left(R,+,\cdot\right)}$ πεπερασμένος μεταθετικός δακτύλιος του Boole ( $\displaystyle{\,\,\,x^2=x\,,\forall\,x\in R}$ ) με μονάδα

και $\displaystyle{S\subseteq R}$ με την ιδιότητα $\displaystyle{x\in S\,\,\land\,\,y\in S\implies x\,y\neq 0}$ που είναι μεγιστικό ως

προς αυτή την ιδιότητα, δηλαδή αν $\displaystyle{S\subset T\subseteq R}$ , τότε υπάρχουν $\displaystyle{x\,,y\in T}$ με $\displaystyle{x\,y=0}$

Τότε, $\displaystyle{2\,|S|=|R|}$ .

Μεγιστικὴ ὑποκλάση τοῦ δυναμοσυνόλου

Μεγιστικὴ ὑποκλάση τοῦ δυναμοσυνόλου

Re: Μεγιστικὴ ὑποκλάση τοῦ δυναμοσυνόλου

Re: Μεγιστικὴ ὑποκλάση τοῦ δυναμοσυνόλου

Re: Μεγιστικὴ ὑποκλάση τοῦ δυναμοσυνόλου

Re: Μεγιστικὴ ὑποκλάση τοῦ δυναμοσυνόλου

Re: Μεγιστικὴ ὑποκλάση τοῦ δυναμοσυνόλου

Re: Μεγιστικὴ ὑποκλάση τοῦ δυναμοσυνόλου

Re: Μεγιστικὴ ὑποκλάση τοῦ δυναμοσυνόλου

Re: Μεγιστικὴ ὑποκλάση τοῦ δυναμοσυνόλου

Re: Μεγιστικὴ ὑποκλάση τοῦ δυναμοσυνόλου

Μέλη σε σύνδεση