Família Sperner que maximiza os subconjuntos de uma partição

Deixe ser um conjunto de tamanho e ser um conjunto de tamanho , para fixa e , e de tal modo que . Qual é a (ou a) família Sperner em para a qual é maximizada? $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}\}$

Na verdade, eu só preciso de um limite superior para(possivelmente algo melhor que , que parece estar solto se ) $|\mathcal{F}_B|$ $2^\ell$ $2^k<\ell$

Qualquer sugestão ou referência em que esse tipo de informação ou material relevante possa ser encontrado seria muito apreciada. Obrigado.

reference-request co.combinatorics Matteo
fonte

Respostas:

O limite superior correto é a soma dos coeficientes binomiais mais centrais: ou apenas se . Os conjuntos são antichains. Pela desigualdade LYM, a união de antichains não pode ser maior que a soma dos maiores coeficientes binomiais de . Para atingir o limite, deixe e deixe $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 UMA \cup B ∣ ⌊ (ℓ + 2^{k}) / 2 ⌋ - \sum_{Eu : {uma}_{Eu} \in C} 2^{Eu} = | 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
fonte

Obrigado, Colin. Acredito que seja a resposta correta, pois obtivemos o mesmo resultado de uma maneira muito mais complicada.

Matteo