current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 4 down vote favorite

Suppose we look at all sets in ${[n] \choose k}$, for some $k \leq n/2$, and place them in layers according to the sum of their elements. Then, we say that two sets $A$ and $B$ from consecutive layers are connected by an edge, if there is some $i \in [n-1]$ for which $(i,i+1)A = B$. That is, if $A \Delta B = \{i,i+1\}$. Is it true that any two consecutive layers have a perfect matching, in the sense that all the elements of the layer with less sets are matched? For instance, let's take $n=6$, $k=3$. And let's match the layer with sum $12$ to the layer with sum $11$:

$(\{6,5,1\}, \{6,4,1\}), (\{6,4,2\},\{6,3,2\}), (\{5,4,3\}, \{5,4,2\})$.

share|cite|improve this question
    
sum 13 only has 6,5,2 and 6,4,3 – JonMark Perry 21 hours ago
    
Yes, The goal is to match all sets of the layer with fewer sets. So, for instance, we can match all sets with sum $13$ to sets with sum $12$ like this: $(\{6,5,2\},\{6,5,1\}), (\{6,4,3\},\{5,4,3\})$. – karpasi 21 hours ago
    
I feel like you ought to be able to do some sort of induction on $n$. Idea: first match all the things with max element at most $n-1$. Then look at the things with max element $n$, and try to match these together (they look like sets with max element at most $n-1$ and with sum $n$ less than originally). The only problem here is that we need to preserve which layer has more elements in each of these, which in general doesn't even happen. – Pat Devlin 17 hours ago
up vote 7 down vote

You are looking at two consecutive ranks of the poset denoted $L(k,n-k)$. I proved the existence of a matching in http://math.mit.edu/~rstan/pubs/pubfiles/42.pdf. A more elementary proof based on linear algebra was later given by R. A. Proctor, Amer. Math. Monthly 89 (1982), 721-734. Another elementary proof based on linear algebra appears in my book Algebraic Combinatorics (built into the proof of Corollary 6.10). It is an open problem to find a combinatorial proof.

share|cite|improve this answer
    
Professor Stanley, I always thoroughly appreciate your contributions to this website [and of course to the development and exposition of combinatorics as a whole]. Just wanted to say thanks! --a current student of Jeff Kahn – Pat Devlin 3 hours ago
    
Thanks, Pat, and best of luck as a student of Jeff! – Richard Stanley 3 hours ago

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.