Sperner-Familie, die die Teilmengen einer Partition maximiert

Sei eine Menge der Größe und eine Menge der Größe für festes und und so, dass . Was ist die (oder eine) Sperner-Familie auf für die maximiert ist? $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}\}$

Ich brauche eigentlich nur eine Obergrenze für(möglicherweise etwas besseres als , was lose zu sein scheint, wenn ) $|\mathcal{F}_B|$ $2^\ell$ $2^k<\ell$

Jeder Hinweis oder Hinweis, wo diese Art von Informationen oder relevantem Material gefunden werden könnte, wäre sehr dankbar. Vielen Dank.

reference-request co.combinatorics Matteo
quelle

Antworten:

Die korrekte Obergrenze ist die Summe der zentralsten Binomialkoeffizienten: oder einfach wenn . Die Mengen sind Antichains. Durch die LYM-Ungleichung kann die Vereinigung von Antichains nicht größer sein als die Summe der größten Binomialkoeffizienten. Um die Grenze zu erreichen, sei und sei $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
quelle

Danke, Colin. Ich glaube, es ist die richtige Antwort, da wir das gleiche Ergebnis viel komplizierter erzielt haben.

Matteo