8
$\begingroup$

Let $P$ be a finite poset. Assign the following diagram to it - put the maximal element of $P$ on the first level, the maximal of the rest to the second level, etc. Assume that the diagram is connected, that is, that between each pair of elements in the diagram we have a chain connecting them.

Let $L_n=P\times P\times\cdots\times P$ ($n$-times) to be the product poset, that is, one element in $L_n$ is larger than another if we have all inequalities coordinate-wise. Is it true that there exists and $N=N(P)$ such that for $n>N$ the following is true:

In the diagram of L_n there is a perfect matching between all consecutive levels (from the one with smaller size to the one with larger size).

Note: due to the useful feedback of Andres Caicedo and David Speyer the question was altered.

$\endgroup$
3
  • 2
    $\begingroup$ There are some missing definitions here. I imagine $P$ is graded, as otherwise I don't know what you mean by level. I imagine your definition of a perfect matching is that you have a bipartite graph $G$, with more black vertices than white, and you are required to use all the white vertices but not required to use all the black? And when you say "from the smaller to the larger", you mean smaller in cardinality, not in the poset order? $\endgroup$ Sep 24, 2013 at 23:03
  • $\begingroup$ Sadly, once you answer these questions I still don't know the answer. But all of them should be spelled out to make a clear question. $\endgroup$ Sep 24, 2013 at 23:03
  • $\begingroup$ I am sorry for being obscure. Let me try to clarify. By using the term "level" I mean that we have the following layout of the poset: put all maximal elements on the top and then put the maximal elements in the leftover on the second level etc. By saying there is a perfect matching between the layers I mean than between any pair of consecutive layers you can math all elements of the smaller level (in the sense of cardinality) to all elements of the larger one. $\endgroup$
    – TOM
    Sep 25, 2013 at 3:25

2 Answers 2

4
+50
$\begingroup$

Here is a counterexample. Let $P$ be the poset on $\{ 1,2,3,4,5,6 \}$ whose only nontrivial relations are $1<2$, $1<3$, $4<6$, $5<6$. Let $Q$ be the subposet on $\{ 1,2,3 \}$ and let $R$ be the subposet on $\{ 4,5,6 \}$. I claim that there is no matching between levels $\ell$ and $\ell+1$ for $n/3 < \ell < 2n/3$. (The bounds here may not be quite right.)

Suppose the matching injects level $\ell$ into level $\ell+1$. But $P^n$ is a disjoint union of $2^n$ posets, one of which is $R^n$. And level $\ell$ of $R^n$ is larger than level $\ell+1$ for $n/3 < \ell$, a contradiction.

Similarly, suppose that matching injects level $\ell+1$ into level $\ell$. But level $\ell+1$ of $Q^n$ is larger than level $\ell$ for $\ell < 2n/3$. Again, we have a contradiction.

Maybe if you asked for the poset to be connected?

$\endgroup$
1
  • $\begingroup$ You are absolutely correct, without connectedness this makes no sense. I will edit the question. $\endgroup$
    – TOM
    Sep 25, 2013 at 4:04
6
$\begingroup$

The statement is still false when $P$ is connected and graded. It is even false if we add in addition that $P$ has a unique minimal and maximal element.

Theorem For any graded finite poset $P$, let $\rho(P)$ be the average of the ranks of the elements of $P$. Suppose that $Q$ is an upper ideal of $P$ and $\rho(Q) < \rho(P)$. (And, equivalently, $\rho(P) < \rho(P \setminus Q)$.) For all sufficiently large $n$, there is no perfect matching between levels of $P^n$ and $Q^n$.

Proof Let $P$ be graded with $p_i$ elements in grade $i$. Let $p(t) = \sum p_i t^i$. So $P^n$ is graded with corresponding polynomial $P(t)^n$. I'll write $P(t)^n = \sum p^n_i t^i$. Define $Q(t)$ similarly and $q^n_i$. Suppose that $p^n_i \leq p^n_{i+1}$ but $q^n_i > q^n_{i+1}$. Then there could be no matching between levels $i$ and $i+1$ of $P^n$. The first inequality would force the matching to be upwards (level $i$ injecting into level $i+1$), but the second inequality would imply that there were not enough elements to match level $i$ of $Q^n$ to.

Now, by a result of Odlyzko and Richmond, for sufficiently large $n$, the coefficients of $P(t)^n$ will be unimodal. Also, by the central limit theorem, the coefficient of $t^k$ in $P(t)^n$ will be much larger when $k$ is near $\rho(P) n$ then anywhere else. Combining these results, the coefficients of $P(t)$ increase up to $ (\rho(P) + o(1))n$ and then decrease down the other side.

Similarly, the coefficients of $Q(t)^n$ increase up to $(\rho(Q)+o(1)) n$ and then decrease. Since $\rho(Q) < \rho(P)$, this shows that the largest coefficient of $Q(t)^n$ occurs before the largest coefficient of $P(t)^n$ for $n$ large. Thus, for $n$ large, there is no matching at the levels between $(\rho(Q)+o(1)) n$ and $(\rho(P)+o(1)) n$. $\square$

Here is are explicit counterexamples. The poset $P$ has $6$ elements, denoted by the symbols $Q$ and $p$; the poset $Q$ is the $3$ elements labeled $Q$:

enter image description here

Then $P(t) = 3+3t$ and $P(t)^n$ has its largest coefficient at $t^{n/2}$, while $Q(t) = 2+t$ and has its largest coefficient at $t^{n/3}$. So, choosing $i$ between $n/3$ and $n/2$, there is no matching between level $i$ and level $i+1$.

Here is a similar example where $P$ has a maximal and minimal element.

enter image description here

We have $\rho(P) = 3/2=1.5$ and $\rho(Q) = (5/7) 1 + (1/7) 2 + (1/7) 3 = 10/7 \approx 1.4$ as desired.

$\endgroup$

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.