Pregunta combinatoria sobre downsets

Question

Demostrar que si $\mathcal{A}$ es un downset entonces el tamaño medio de los sistemas en $\mathcal{A}$ es a más $\frac{n}{2}$

($\mathcal{A} ⊂ \mathcal{P}(n)$ es un downset si cada $A∈\mathcal{A}$, cada subconjunto de $A$ pertenece a $\mathcal{A}$)

Han intentado usar inducción pero consiguió pegado en el paso inductivo. Cualquier ayuda mucho apreció!

Answer 1

Este podría ser el uso de un cañón para matar una mosca, pero...

Se puede demostrar que es posible partición de $\mathcal{P}(n)$ en simétrica de las cadenas. Aquí, y de la cadena de $A_1,A_2,\dots, A_k$ es una secuencia de conjuntos tales que a $A_1 \subsetneq A_2 \subsetneq \dots$, y es simétrica si $\# A_i + \# A_{k+1-i} = n $ cualquier $i$. El reclamo no es extremadamente difícil, y usted puede hacerlo por inducción en $n$. [Para una prueba de ello, véase, por ejemplo, estas notas, p.78, Thm 8.3]

Sabiendo esto, la solución es fácil. Considere la posibilidad de cualquier cadena de $A_1,A_2,\dots, A_k$. Debido a $\mathcal{A}$ se supone que es un downset, siempre que $A_l \in \mathcal{A}$ también $A_i \in \mathcal{A}$$i < l$. Por lo tanto, hay algo de $l$ de manera tal que los conjuntos de la cadena, que pertenecen a $\mathcal{A}$ son, precisamente,$A_1,A_2,\dots, A_l$. Emparejamiento $A_i$ $A_{l+1-i}$ vemos que, en promedio, $A_i \in \mathcal{A} $ tienen en la mayoría de $n/2$ elementos. Promediando esta encima de todas las cadenas en la partición (y usando el hecho de que las cadenas son disjuntos), llegamos a la conclusión de que el tamaño promedio de $A \in \mathcal{A} $ es en la mayoría de las $n/2$.