16
$\begingroup$

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}}.$$

$\endgroup$
2
  • 1
    $\begingroup$ 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. :-) $\endgroup$ Aug 1, 2010 at 9:28
  • 2
    $\begingroup$ 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. $\endgroup$ Aug 1, 2010 at 12:38

1 Answer 1

4
$\begingroup$

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...

$\endgroup$
7
  • $\begingroup$ If there is no repeated entry in any row, then there are certainly no repeated columns. $\endgroup$
    – AVS
    Aug 1, 2010 at 12:20
  • $\begingroup$ You're right, that was a typo. $\endgroup$ Aug 1, 2010 at 12:30
  • 1
    $\begingroup$ 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. $\endgroup$
    – AVS
    Aug 1, 2010 at 13:37
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 1, 2010 at 14:51
  • 1
    $\begingroup$ Any matrix with a repeated row (column) contains a bad column (row), and thus does not contribute to either the LHS or the RHS. $\endgroup$
    – AVS
    Aug 1, 2010 at 16:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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