An identity in combinatorial extremal theory (Q917551): Difference between revisions

The paper deals with the following identity: For every family \({\mathcal A}\subset 2^{\Omega}\) of non-empty subsets of \(\Omega =\{1,2,...,n\}\) is \(\sum_{X\subset \Omega}W_{{\mathcal A}}(X)[| X| \left( \begin{matrix} n\\ X\end{matrix} \right)]^{-1}\equiv 1,\) where \(W_{{\mathcal A}}(X)=| \cap_{X\supset A\in {\mathcal A}}A|.\) It can be shown that the following identity is equivalent to the preceding one \[ \sum_{X}W_{{\mathcal A}}(X)[| X| \left( \begin{matrix} n\\ | X| \end{matrix} \right)]^{-1}=\sum^{n}_{i=1}W_{{\mathcal A}}^{(i)}[i\left( \begin{matrix} n\\ i\end{matrix} \right)]^{-1}, \] where \(W_{{\mathcal A}}^{(i)}=\sum_{X\in {\mathcal P}_ i}W_{{\mathcal A}}(X)\) and \({\mathcal P}_ i\) is the set of all i-element subsets of \(\Omega\). One of the most important results of this paper is Theorem 1: For every family \({\mathcal A}\) of non-empty subsets of \(\Omega =\{1,2,...,n\}\) is \(\sum^{n}_{i=1}W_{{\mathcal A}}^{(i)}[i\left( \begin{matrix} n\\ i\end{matrix} \right)]^{-1}=1.\) Further there are consequences for families of sets where there are considerations especially about new results for generalized antichains and about an extension to several families. In the section of geometric consequences occur investigations about n-dimensional unit-cube \(C^ n=\{0,1\}^ n\) with the usual \(n.2^{n-1}\) edges. The contents of the part of uniqueness proofs are some special cases as e.g. Spencer's case and other ones. The next section is dedicated to an identity for posets. In the end there are two further proofs of Theorem 1.