Grading a non-graded poset as squeezed as possible

2012-05-28T14:16:42Z

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.)

Answer by darij grinberg for Grading a non-graded poset as squeezed as possible

2012-06-15T21:26:10Z

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:

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.

Grading a non-graded poset as squeezed as possible - MathOverflow

Grading a non-graded poset as squeezed as possible

Answer by darij grinberg for Grading a non-graded poset as squeezed as possible