10
$\begingroup$

Let's start from a classical inequality:

If $0\le a_1\le\cdots\le a_k$ and $0\le b_1\le\cdots\le b_k$ then $(a_1+\cdots+a_k)(b_1+\cdots+b_k)\le k(a_1b_1+\cdots+a_k b_k)$.

It can be written also in the form of averages: $Av(\{a_i\})Av(\{b_i\})\le Av(\{a_ib_i\})$ (expressing convexity and many other properties)

I need the following generalization for finite partially ordered sets. Let $S$ be such a set, consider non-decreasing functions, i.e. $f:S\rightarrow\Bbb{R}_{\ge0}$, satisfying: if $a\ge b$ then $f(a)\ge f(b)$.

I need: $\underline{\text{ if $f,g$ are non-decreasing functions then } Av_S(f)Av_S(g)\le Av_S(fg).}$

If $S$ is totally ordered, then one gets the classical version.

The inequality does not hold for arbitrary partial ordered sets (with obvious counterexamples). I guess a necessary condition is that $S$ has minimal and maximal elements. Even this is not enough (with obvious counterexamples).

In my particular case $S$ is the set of lattice points on a simplex, i.e.: $S_{n,r}:=\{(k_1,\dots,k_r)|\ k_1+\cdots+k_r=n,\ k_1,\dots,k_r\ge0\}$. (One can think about this as the set of monomials in r variables of total degree n.) The order is induced by recursive application of the rule $x^2_i\ge x_ix_j$. (So, e.g. $x^n_i\ge x^{n-1}_ix_j\ge x^{n-2}_ix_jx_k\ge\cdots$.) And the considered functions are symmetric (i.e. invariant w.r.t. to the permutation group $\Xi_r$, that acts on $S_{n,r}$.)

Alternatively, one can consider the quotient $S_{n,r}/\Xi_r$. (This set is partially ordered, with minimal and maximal elements.)

Probably in this particular case the inequality is well known? I guess, a necessary condition on a partially ordered set to satisfy such an inequality (for any non-decreasing functions) is that $S$ is "ordered enough". Can this be made precise? Are there some sufficient conditions known?

For bookkeeping: in a very particular case (here) we proved this bound by terrible brute force.

upd: we have proved this inequality (for $S_{n,r}$) arXiv:1412.8200.

$\endgroup$
  • $\begingroup$ indeed, in my case the functions on $S_{n,r}$ are symmetric. (I corrected the question.) $\endgroup$ – Dmitry Kerner Dec 6 '13 at 13:00
  • $\begingroup$ Slight quibble: I think you are using maximal/minimal elements when you meant maximum/minimum elements. They are not the same thing. $\endgroup$ – Willie Wong Dec 6 '13 at 13:05
  • 1
    $\begingroup$ I am not too hopeful of a general theorem: (a) the reason that the classical totally ordered case works is the rearrangement inequality, which gives the absolute maximum arrangement. The statement made naively analogously for the poset case is false. (b) Whether the statement holds is very sensitive to the shape of the poset. The poset with $\{0,1\}$ and $\{a,b\}$ such that $0 < a < 1$ and $0 < b < 1$ satisfies your inequality. But if you make the middle step three elements big instead of two it fails. $\endgroup$ – Willie Wong Dec 6 '13 at 13:09
  • $\begingroup$ I agree that for most posets the inequality dos not hold. Well, I'll be happy to see the proof at least for $S_{n,r}/\Xi_r$. This poset is not totally ordered (as is seen already for r=3 and high enough n). $\endgroup$ – Dmitry Kerner Dec 6 '13 at 14:21
  • $\begingroup$ And you are right that the averages are weighted now (i.e. the averages come from $S_{n,r}$). $\endgroup$ – Dmitry Kerner Dec 6 '13 at 14:21
13
$\begingroup$

The natural generalization for your inequality is the setting of distributive lattices. The inequality is then known as the Fortuin–Kasteleyn–Ginibre (FKG) inequality, and has a long history. See for example Graham's article "Applications of the FKG inequality and its relatives". A generalization of the FKG inequality is the Ahlswede-Daykin inequality. For the appropriate specialisations, the FKG inequality implies $$|A|\cdot |B|\le |A\cap B|\cdot |P|$$ for all up sets $A,B$ as mentioned in domotorp's answer, and I don't know how this extends to lattices that are not distributive. The AD inequality, however specializes to $$|A|\cdot|B|\le |A\wedge B|\cdot|A\vee B|$$ which is always false when the lattice is not distributive.

Your Poset $S_{n,r}/\Xi_r$ is the lattice of partitions of $n$ with at most $r$ parts, with the dominance (majorization) ordering. This is always a lattice, however it is not distributive in general. For example $S_{n,n}/\Xi_n$ is not distributive for $n\geq 7$. It might still be worth investigating whether the FKG inequality holds for this lattice, even though we don't have distributivity, since it has other nice properties (for example the Mobius function is nice).

$\endgroup$
  • $\begingroup$ Wow, thanks. I'm so faraway from this field. At least, can you give some ranges of n,r for which $S_{n,r}/\Xi_r$ is distributive? (the lattice of Young's diagrams is distributive. I thought that $S_{n,r}/\Xi_r$ is precisely this lattice. In my case I have a restriction: $n\ge r+3$.) $\endgroup$ – Dmitry Kerner Dec 8 '13 at 16:22
4
$\begingroup$

This is not an answer, just a reformulation of the question, which, imho, has nothing to do with functions. Just notice that if some $f_1, g$ and $f_2, g$ pairs satisfy your condition, then so does $f_1+f_2, g$, which implies that it is enough to consider 0-1 functions, which correspond to sets. So a reformulation would be:

In a given poset $P$, is it true that for any $A$ and $B$ upwards closed subsets $|A|\cdot |B|\le |A\cap B|\cdot |P|$ holds?

As you have noted, it is necessary but not sufficient for $P$ to have a largest and smallest element. Unfortunately, I don't know whether the inequality is true or not for your poset.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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