# finding permutations which fulfills given conditions

Let $K$ be an ordered finite set. Consider some function $g:K^2 \rightarrow R$ such that

$g(k1,k1') + g(k2,k2') \ge g(k1,k2') + g(k2,k1')$

where $k1 > k2$ (in order A1) and $k1' > k2'$ (in order A2) (*)

Is there exists some effective algorithm which for given function can find such orders A1,A2 where the function fulfill the property (*) or verify that such orders A1,A2 doesn't exists.

REFORMULATION:

Let $K$ be a finite set. Let $g\colon K^2 \rightarrow \mathbb{R}$.

We want to define the orders $>_1$ and $>_2$ on $K$ such that $$s \, >_1 \,\, t \text{ and } x \, >_2 \,\, y$$ if and only if $$g(s,x) + g(t,y) \ge g(s,y) + g(t,x).$$

Is there an efficient algorithm to prove the existence or non-existence of the two orders?

• I have submitted an edit of the question so it is clearer (the way I understood it). If that was not the initial meaning of the question you can delete it: I have left your question untouched. – Gopi Oct 19 '11 at 17:53
• It's worth noting that in the lattice induced by the product order of $A_1$ and $A_2$, the point $(k_2, k'_2)$ is the meet of $(k_1, k'_2), (k_2, k'_1)$ and the point $(k_1, k'_1)$ is the join. So actually your condition is merely the definition of supermodularity for $g$. So rephrased, your question is: Is there a way, for any function $g$, to construct a product lattice from two total orders so that $g$ is supermodular ? – Suresh Venkat Oct 19 '11 at 22:33
• I'm concerned with "if and only if" in the REFORMULATION. For example, if g is a constant function, g is supermodular. But the condition in the REFORMULATION is not satisfied because for all 4-tuples (k1,k2,k1',k2') the inequality is satisfied (with equality). – Yoshio Okamoto Oct 19 '11 at 23:05
• Another interpretation might be this: can we permute the rows and columns of a matrix to make it "supermodular"? (Again, assuming that the "if and only if" part is wrong.) – Jukka Suomela Oct 19 '11 at 23:35
• @KostiaAntoniuk: I see. but to be honest, your first question was very cryptic. This one makes more sense :) – Suresh Venkat Oct 20 '11 at 6:50