Non-containing subsets of two sizes

Let $\mathcal{A}$ be any collection of subsets of $\{1,\dots,m\}$ such that no subset in $\mathcal{A}$ is contained in another. Let $a_i$ be the number of $i$-element subsets in $\mathcal{A}$. A complete characterization of the sequences $(a_0,a_1,\dots)$ appears as Theorem 2.2 in https://pdfs.semanticscholar.org/da0b/1a3430e4be45119921b8b8a6578b355bb2f6.pdf. In principle it should be possible to use this result to answer your question, but I did not work out the details.


Like Richard Stanley, I also did not work out the details. I also can't say if you can prove it from Sperner's theorem. Here is why I think there is no larger $k$.

Split the bipartite graph into two based on whether they contain the element 1 or not. You will see the collection of n+1 sets fanout into the n-sets when they don't have the element 1, and the fanout goes the other way for the sets that do have 1. Your current solution shows the sets at the narrow end of each fanout. Suppose you want to improve upon it.

This means you will have to take (say) some sets from the n+1 camp, and replace them with even more sets in the other camp (and likewise for the n sets). But however you arrange the n+1 sets in the other camp, if they are all contained in a subset of size less than 2n+1, they will fan out to cover more subsets of size n than they replace, so whatever you choose has to cover the whole set of size 2n+1.

So now you have to pick j many subsets from 2n+1 elements of size n+1 that cover exactly j subsets of size n: this means each subset of size n has to be covered by n+1 subsets, which is all possible covers of that n set. This means any for any n set covered by one of your j cboices, you also need to cover another n set formed from this n set J by swapping any one element in J for another not in J. But now this closure condition means your j elements have to cover all n sets. That's too many. So it can't be done.

Gerhard "Look Ma, I Can Fly!" Paseman, 2019.05.22.


Here's another approach: Given families $\mathcal{A}$ and $\mathcal{B}$ of $n$-sets and $(n+1)$-sets (respectively) that obey the condition, replace $\mathcal{B}$ with the family $\mathcal{B}'$ of complements of sets in $\mathcal{B}$.

Now the condition that no set in $\mathcal{A}$ is contained in one in $\mathcal{B}$ becomes that every set in $\mathcal{A}$ intersects non-trivially with every set in $\mathcal{B}'$. Such a system is called cross-intersecting.

Now you can apply combinatorial shifting to $\mathcal{A}$ and $\mathcal{B}'$, and show that it preserves the intersection property. This reduces showing the proof of your inequality to shifted families, where it is likely to be much easier. (I haven't worked out all the details here.)

Tags:

Co.Combinatorics

Related

Integrate $1/(x_1x_2\cdots x_n)^k$ for $1\le x_i \le a$, where product of coordinates satisfies $ b\le x_1\cdots x_n\le c$ Is categoricity retained when reducing the language? If a (distance) metric on a connected Riemannian manifold locally agrees with the Riemannian metric, is it equal to the induced metric? Grade-school elementary algebra presented in an abstract-algebra style? Notion of linking between two general $p$ and $q$ manifolds embedded in a higher dimensional manifold Open mapping theorem for complete non-metrizable spaces? What is a tamely-ramified Weil-Deligne representation? Example of two exotic closed 4-manifolds s.t. SW(X)=0 Alexandrov's generalization of Cauchy's rigidity theorem Status of proof by contradiction and excluded middle throughout the history of mathematics? Matrix of cosecants appearing in equivariant index computations Rate of convergence of the prime zeta function P(2)

Recent Posts