← All problems

Complete equality condition for the Kahn–Saks inequality

5 years old · traced to

Let P=(X,≺)P=(X,\prec) be a finite poset with n=∣X∣n=|X|, and let x,y∈Xx,y\in X be distinct. Denote by F⁡(k)\operatorname{F}(k) the number of linear extensions L∈E⁡(P)L\in\operatorname{\mathcal{E}}(P) such that L(y)−L(x)=kL(y)-L(x)=k. A pair (x,y)(x,y) satisfies the kk-midway property when the conditions specified in the paper hold, and the dual kk-midway property is defined by reversing the order. Suppose that k∈{2,…,n−2}k\in\{2,\ldots,n-2\} and F⁡(k)>0\operatorname{F}(k)>0. Complete equality condition for the Kahn–Saks inequality. The following are equivalent: (a) F⁡(k)=F⁡(k+1)=F⁡(k−1)\operatorname{F}(k)=\operatorname{F}(k+1)=\operatorname{F}(k-1); (b) there is an element z∈{x,y}z\in\{x,y\} such that, for every L∈E⁡(P)L\in\operatorname{\mathcal{E}}(P) with L(y)−L(x)=kL(y)-L(x)=k, there are elements u,v∈Xu,v\in X incomparable with zz and satisfying L(u)+1=L(z)=L(v)−1L(u)+1=L(z)=L(v)-1; and (c) (x,y)(x,y) satisfies either the kk-midway property or the dual kk-midway property. This gives a characterization of equality in the Kahn–Saks inequality under the stated hypotheses; the surrounding discussion presents it as a partial result toward complete equality conditions for general posets.

References
  1. Swee Hong Chan, Igor Pak and Greta Panova, “Extensions of the Kahn–Saks inequality for posets of width two”, arXiv:2106.07133 (2022).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.