Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Warren Moors and Julia Novak in a paper entitled "Order matters when choosing sets" proved that if 1 < w < t < v are integers then $${{{v}\choose {w}}\choose {t}} > {{{v}\choose {t}}\choose {w}}.$$ In words: the number of t-subsets from the family of w-subsets of [v]={1,2,...,v} is larger than the number of w-subsets from the family of t-subsets of [v].

The question

(proposed by Steve Wilson in a problem session of this conference)

Find a combinatorial explanation for Moors and Novak's result.

Remark

Moors and Warren give an elementary proof an even stronger inequality. $$(w!)^{t-1}{{{v}\choose {w}}\choose {t}} > (t!)^{w-1} {{{v}\choose {t}}\choose {w}}.$$

share|improve this question
1  
These smilies in the paper (which should replace qed-symbols) are scary. Usually I don't want to be smiled at when I read a proof. :-) –  Martin Brandenburg Aug 1 '10 at 9:28
2  
Yea. It reminds me of a student, years ago in a calculus course. At the end of a proof, always he would laugh... A nervous symptom I guess. –  Pietro Majer Aug 1 '10 at 12:38
add comment

1 Answer

This is not a full answer but I'm throwing some observations out. Note that the even stronger inequality also has a clear combinatorial interpretation. Namely, if one denotes by inj(A,B) the set of injections from A to B, then the inequality says that

|inj(T,inj(W,V))| > |inj(W,inj(T,V))|.

To see this, multiply both sides of the stronger inequality by t!w!. Of course, here t = |T|, w = |W| and v = |V|.

In this form, it is easy to believe the inequality. Consider a function $f : T \times W \to V$, thought of as a $t \times w$ matrix with entries in V. It defines an element of the left hand side if there is no repeated entry in any row, and there are no repeated entire rows. The right hand side counts the same thing with columns. We have assumed that the columns are longer than the rows. Then if the entries of the matrix are picked uniformly at random, it should fail to define an element of the right hand side with greater probability, since most functions that fail should do so because of repeated entries in a row/column rather than an entire repeated row/column, and it is more likely to be a repeated entry in a column than in a row.

However, I don't see any nice way of producing a proof out of the above heuristic. Bijective proofs seem to get really complicated...

share|improve this answer
    
If there is no repeated entry in any row, then there are certainly no repeated columns. –  AVS Aug 1 '10 at 12:20
    
You're right, that was a typo. –  Dan Petersen Aug 1 '10 at 12:30
1  
Actually, I think your heuristic argument gives an easy proof of the stronger inequality. Let $A$ be a $t\times w$ matrix with uniformly random entries in $V$, and let $B$ be the square matrix consisting of the top $w$ rows of $A$. The probability that $B$ contains a bad row (one with a repeated entry) is equal to the probability that it contains a bad column. Assuming $B$ has no bad columns, each remaining entry of $A$ is more likely to coincide with an element in its column than with an element in its row. Thus $A$ is more likely to contain a bad column than a bad row, hence LHS > RHS. –  AVS Aug 1 '10 at 13:37
1  
Sure, but now you're only computing the probability of having repeated entries in a single row, but you need to also take into account the probability of having an entire row repeated. –  Dan Petersen Aug 1 '10 at 14:51
1  
Any matrix with a repeated row (column) contains a bad column (row), and thus does not contribute to either the LHS or the RHS. –  AVS Aug 1 '10 at 16:26
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.