Keluarga Sperner yang memaksimalkan subset dari partisi

Mari menjadi satu set ukuran dan menjadi satu set ukuran , untuk tetap dan , dan sehingga . Berapakah (atau a) keluarga Sperner pada yang dimaksimalkan? $A$ $k$ $B$ $\ell$ $k$ $\ell$ $A\cap B=\emptyset$ $\mathcal{F}$ $A\cup B$ $\mathcal{F}_B=\{C\cap B ~:~ C\in\mathcal{F}\}$

Aku sebenarnya hanya butuh batas atas untuk (mungkin sesuatu yang lebih baik dari , yang tampaknya longgar jika ) $|\mathcal{F}_B|$ $2^\ell$ $2^k<\ell$

Setiap petunjuk atau referensi di mana informasi semacam ini atau materi yang relevan dapat ditemukan akan sangat dihargai. Terima kasih.

reference-request co.combinatorics Matteo
sumber

Jawaban:

Batas atas yang benar adalah jumlah dari koefisien binomial paling sentral: atau hanya jika . Set adalah antikristus. Dengan ketidaksetaraan LYM penyatuan antikain tidak bisa lebih besar dari jumlah koefisien binomial terbesar . Untuk mencapai batas, biarkan , dan biarkan $2^k$

| F_{B} | \leq (\binom{ℓ}{⌊ (ℓ - 2^{k}) / 2 + 1 ⌋}) + \dots + (\binom{ℓ}{⌊ (ℓ + 2^{k}) / 2 ⌋}),

$|\mathcal{F}_B|\leq\binom \ell {\lfloor (\ell - 2^k)/2+1\rfloor} + \dots + \binom \ell {\lfloor(\ell + 2^k)/2\rfloor},$

| F_{B} | \leq 2^{ℓ}

$|\mathcal{F}_B|\leq 2^\ell$

2^{k} \geq ℓ + 1

$2^k\geq \ell+1$

{B \cap C ∣ C \in F and A \cap C = A^{'}}

$\{B\cap C\mid C\in\mathcal F\text{ and }A\cap C=A'\}$

2^{k}

$2^k$

2^{k}

$2^k$

A = {a_{0}, \dots, a_{k - 1}}

$A=\{a_0,\dots,a_{k-1}\}$

F = {C \subseteq A \cup B ∣ ⌊ (ℓ + 2^{k}) / 2 ⌋ - \sum_{i : a_{i} \in C} 2^{i} = | C \cap B |} .

$\mathcal F=\left\{C\subseteq A\cup B \mid \lfloor(\ell + 2^k)/2\rfloor- \sum_{i\colon a_i\in C} 2^i=|C\cap B| \right\}.$

Colin McQuillan
sumber

Terima kasih, Colin. Saya percaya itu adalah jawaban yang benar, karena kami mendapatkan hasil yang sama dengan cara yang jauh lebih berbelit-belit.

Matteo