most recent 30 from http://mathoverflow.net 2013-05-19T18:10:40Z http://mathoverflow.net/feeds/question/34082 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/34082/order-matters-when-choosing-sets Gil Kalai 2010-08-01T03:28:33Z 2010-08-01T12:29:16Z

<p>Warren Moors and Julia Novak in a paper entitled "<a href="http://www.math.auckland.ac.nz/~jnov002/Novak3.pdf" rel="nofollow">Order matters when choosing sets</a>" proved that if 1 &lt; w &lt; t &lt; 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]. </p> <h2>The question</h2> <p>(proposed by Steve Wilson in a problem session of <a href="https://sites.google.com/a/alaska.edu/kleegrunbaum/" rel="nofollow">this conference</a>)</p> <blockquote> <p>Find a combinatorial explanation for Moors and Novak's result.</p> </blockquote> <h3>Remark</h3> <p>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}}.$$</p>

http://mathoverflow.net/questions/34082/order-matters-when-choosing-sets/34097#34097 Dan Petersen 2010-08-01T10:41:08Z 2010-08-01T12:29:16Z

<p>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 <em>inj(A,B)</em> the set of injections from <em>A</em> to <em>B</em>, then the inequality says that </p> <p><em>|inj(T,inj(W,V))| > |inj(W,inj(T,V))|</em>.</p> <p>To see this, multiply both sides of the stronger inequality by <em>t!w!</em>. Of course, here <em>t = |T|, w = |W|</em> and <em>v = |V|</em>.</p> <p>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 <em>V</em>. 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.</p> <p>However, I don't see any nice way of producing a proof out of the above heuristic. Bijective proofs seem to get really complicated...</p>