3
$\begingroup$

Here is a curiosity question (motivated by the recent revamp of ranked-poset routines in Sage).

Let $P$ be a finite poset. We look for a family $\left(a_p\right)_{p\in P}$ of real numbers summing up to $0$ such that

$a_i-a_j\geq 1$ for every pair $\left(i,j\right)\in P\times P$ satisfying $i > j$.

The solution set to this problem is clearly a convex polyhedron (by which I mean a convex polyhedron not necessarily bounded). Is it true that every vertex (i. e., every $0$-dimensional face) $\left(a_p\right)_{p\in P}$ of this polyhedron has the property that, for every maximal-length strictly increasing chain $\left(p_1,p_2,...,p_n\right)$ of $P$, we have

$a_{p_1} - 1 = a_{p_2} - 2 = ... = a_{p_n} - n$ ?

(What I can prove is that there exists at least one solution $\left(a_p\right)_{p\in P}$ with this property. It is obtained by setting

$a_i = \text{length of the maximal strictly increasing chain ending at }i$

for every $i\in P$, and then adding a constant to all $a_i$ in order to ensure that the $a_i$ sum up to $0$. This property feels like it would be a reasonable thing to expect from vertices of the polyhedron, because if a solution is "optimal" it "should not waste space by having too much room between adjacent points in a maximal chain", but this is just an intuition and doesn't give rise to a formal proof.)

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

The conjecture is wrong. Sorry, Patricia, for the waste of your time.

Code to verify a counterexample:

# This code is for checking my conjecture in MathOverflow question #98193
# ( http://mathoverflow.net/questions/98193 ). Runs with Sage 5.0.

# In the following, the "MO98193" polyhedron of a finite poset will mean the
# polyhedron defined in MO question 98193.

def mo98193polyhedron(P, elements='None'):
    # INPUT:
    # P: finite poset.
    # Optional argument elements: a list of the elements of P.
    # OUTPUT:
    # MO98193 polyhedron of P.
    if elements == 'None':
        elements = P.list()
    n = len(elements) + 1
    inequalities = []
    for cover in P.cover_relations_iterator():
        a = elements.index(cover[0])
        b = elements.index(cover[1])
        c = [0] * n
        c[0] = -1
        c[a + 1] = -1
        c[b + 1] = 1
        inequalities.append(c)
    equality = [1] * n
    equality[0] = 0
    return Polyhedron(ieqs = inequalities, eqns = [equality])

def testconjecture(P):
    # INPUT:
    # P: finite poset.
    # OUTPUT:
    # True if the MO98193 conjecture is valid for poset P.
    # Else, the maximal chain and the vertex of the polyhedron that
    # witness the invalidity of the conjecture.
    elements = P.list()
    poly = mo98193polyhedron(P, elements=elements)
    verts = poly.vertices()
    chains = P.maximal_chains()
    u = max([len(c) for c in chains])
    maxchains = filter(lambda c: len(c) == u, chains)
    print "Order of vertices of poset chosen: ", elements
    print "Maximal chains: ", maxchains
    print "Vertices of the polyhedron: ", verts
    for maxchain in maxchains:
        for vert in poly.vertices():
            for i in range(u-1):
                if vert[elements.index(maxchain[i + 1])] > vert[elements.index(maxchain[i])] + 1:
                    print "Witnessing chain: ", maxchain
                    print "Witnessing vertex: ", vert
                    return False
    return True

Counterexample:

Q = Poset([[1,2,3,4,5,6,7,8,9],[[1,2],[2,3],[3,4],[2,5],[6,5],[6,7],[7,8],[9,8],[9,3]]])

Sage 5.0 output:

sage: testconjecture(Q)
Order of vertices of poset chosen:  [9, 6, 7, 8, 1, 2, 3, 4, 5]
Maximal chains:  [[1, 2, 3, 4]]
Vertices of the polyhedron:  [[-2/3, -2/3, 1/3, 4/3, -5/3, -2/3, 1/3, 4/3, 1/3], [0, -1, 0, 1, -2, -1, 1, 2, 0], [-1/3, -4/3, -1/3, 2/3, -4/3, -1/3, 2/3, 5/3, 2/3]]
Witnessing chain:  [1, 2, 3, 4]
Witnessing vertex:  [0, -1, 0, 1, -2, -1, 1, 2, 0]
False

Here is a picture of Q with the bad vertex:

alt text http://mit.edu/~darij/www/poset.png

Or, for a counterexample with global min and max:

R = Poset([[1,2,3,4,5,6,7,8,9,0,10],[[1,2],[2,3],[3,4],[2,5],[6,5],[6,7],[7,8],[9,8],[9,3],[0,1],[0,6],[8,10],[4,10],[5,10],[0,9]]])

Output:

sage: testconjecture(R)
Order of vertices of poset chosen:  [0, 1, 2, 6, 5, 7, 9, 3, 4, 8, 10]
Maximal chains:  [[0, 1, 2, 3, 4, 10]]
Vertices of the polyhedron:  [[-29/11, -18/11, -7/11, -7/11, 4/11, 4/11, -7/11, 4/11, 15/11, 15/11, 26/11], [-27/11, -16/11, -5/11, -16/11, 17/11, -5/11, -16/11, 6/11, 17/11, 17/11, 28/11], [-28/11, -17/11, -6/11, -6/11, 5/11, 5/11, -17/11, 5/11, 16/11, 16/11, 27/11], [-28/11, -17/11, -6/11, -17/11, 16/11, 5/11, -17/11, 5/11, 16/11, 16/11, 27/11], [-27/11, -16/11, -5/11, -16/11, 6/11, 6/11, -16/11, 6/11, 17/11, 17/11, 28/11], [-26/11, -15/11, -4/11, -15/11, 7/11, -4/11, -15/11, 7/11, 18/11, 18/11, 29/11], [-30/11, -19/11, -8/11, -8/11, 14/11, 3/11, -8/11, 3/11, 14/11, 14/11, 25/11], [-28/11, -17/11, -6/11, -17/11, 16/11, -6/11, -6/11, 5/11, 16/11, 16/11, 27/11], [-3, -2, -1, -1, 0, 0, 0, 1, 2, 1, 3], [-28/11, -17/11, -6/11, -17/11, 5/11, 5/11, -6/11, 5/11, 16/11, 16/11, 27/11], [-25/11, -14/11, -3/11, -14/11, 8/11, -3/11, -14/11, 8/11, 19/11, 8/11, 30/11], [-29/11, -18/11, -7/11, -18/11, 15/11, 4/11, -7/11, 4/11, 15/11, 15/11, 26/11], [-26/11, -15/11, -4/11, -15/11, 7/11, -4/11, -4/11, 7/11, 18/11, 7/11, 29/11], [-27/11, -16/11, -5/11, -16/11, 6/11, -5/11, -5/11, 6/11, 17/11, 17/11, 28/11], [-27/11, -16/11, -5/11, -16/11, 17/11, -5/11, -5/11, 6/11, 17/11, 6/11, 28/11], [-26/11, -15/11, -4/11, -15/11, 18/11, -4/11, -15/11, 7/11, 18/11, 7/11, 29/11], [-29/11, -18/11, -7/11, -7/11, 15/11, 4/11, -18/11, 4/11, 15/11, 15/11, 26/11]]
Witnessing chain:  [0, 1, 2, 3, 4, 10]
Witnessing vertex:  [-3, -2, -1, -1, 0, 0, 0, 1, 2, 1, 3]
False

This R is just the Q with a global min and a global max added.

Note that there is a quick way to see whether a family $\left(a_p\right)_{p\in P}$ is a vertex of our polyhedron: A pair $\left(i, j\right)$ of elements of $P$ is called tight if $j$ covers $i$ and $a_j-a_i=1$. Consider the non-directed graph whose edges are $\left\lbrace i,j\right\rbrace$ for all tight pairs $\left(i,j\right)$. Then, $\left(a_p\right)_{p\in P}$ is a vertex if and only if this graph is connected.

Improve this answer
$\endgroup$
7
  • $\begingroup$ I don't have time now to go through your counterexample, but good luck with this stuff. I tend to think something along these lines should be true, and it might be a matter of finding the right statement. $\endgroup$
    – Patricia Hersh
    Commented Jun 16, 2012 at 13:04
  • $\begingroup$ One more comment: I would suggest you take some time to digest your counterexample (if you haven't already) and add to your answer an explanation for what issue it reveals that is making your conjecture false. This will make it much easier for people to quickly understand the counterexample and perhaps give you further suggestions. $\endgroup$
    – Patricia Hersh
    Commented Jun 16, 2012 at 14:34
  • $\begingroup$ Yes, I have done already; I was just too lazy to draw it. (Sage's drawing routine broke the symmetry and made it useless.) $\endgroup$
    – darij grinberg
    Commented Jun 16, 2012 at 16:32
  • $\begingroup$ Ok, thanks for drawing it. That's an interesting example. $\endgroup$
    – Patricia Hersh
    Commented Jun 16, 2012 at 19:34
  • $\begingroup$ By the way, I deleted my answer since it was incorrect. Thanks again for the example that helped me see my mistake. $\endgroup$
    – Patricia Hersh
    Commented Aug 14, 2012 at 13:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .