Description
Abstract: Since there is no better program for this week, I will give a short, but at least trivial talk.
Sperner's theorem states that if more than ${n\choose \lfloor {n\over 2}\rfloor}$ distinct members are chosen from the subsets of an $n$-element set then there is a pair among them satisfying $A\subset B$. Suppose now, more generally that ${\cal F}$ is a family of subsets of the $n$-element set where $|{\cal F}|=m$ is fixed. There are some nice results determining the minimum number of pairs $A, B\in {\cal F} (A\not=B)$ such that $A\subset B$, as a function of $m$. Jianguo Qian, Konrad Engel and Wei Xu (2009) considered a modification of this problem. Allow repetition of the subsets. That is, the subsets have multiplicities and the sum of the multiplicities $m$ is fixed and we want to determine the minimum number of pairs $A, B\in {\cal F}$ such that $A\subset B$ where $A=B$ is also allowed. Their result says that the optimal construction is the following one: choose all sets of size $\lfloor {n\over 2}\rfloor$ with nearly equal multiplicities. Their proof uses the usual methods of extremal set theory, including e.g. "shifting".
As it often happens in mathematics, the problem becomes easier for a more general setting. Let $G$ be a simple graph with independence number $\alpha (G)$. Suppose that the vertices of $G$ have multiplicities and the sum of all multiplicities is a fixed $m$. Find the minimum number of pairs of vertices $u,v$ where either $u=v$ or they are adjacent. We prove that the best choice is to give nearly equal multiplicities to the vertices of a largest independent set. Some open problems are suggested.