Grading a non-graded poset as squeezed as possible - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T08:39:54Z http://mathoverflow.net/feeds/question/98193 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/98193/grading-a-non-graded-poset-as-squeezed-as-possible Grading a non-graded poset as squeezed as possible darij grinberg 2012-05-28T14:16:42Z 2012-06-16T16:31:55Z <p>Here is a curiosity question (motivated by the recent revamp of ranked-poset routines in Sage).</p> <p>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</p> <p>$a_i-a_j\geq 1$ for every pair $\left(i,j\right)\in P\times P$ satisfying $i > j$.</p> <p>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</p> <p>$a_{p_1} - 1 = a_{p_2} - 2 = ... = a_{p_n} - n$ ?</p> <p>(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</p> <p>$a_i = \text{length of the maximal strictly increasing chain ending at }i$</p> <p>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.)</p> http://mathoverflow.net/questions/98193/grading-a-non-graded-poset-as-squeezed-as-possible/99748#99748 Answer by darij grinberg for Grading a non-graded poset as squeezed as possible darij grinberg 2012-06-15T21:26:10Z 2012-06-16T16:31:55Z <p>The conjecture is wrong. Sorry, Patricia, for the waste of your time.</p> <p>Code to verify a counterexample:</p> <pre><code># 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])] &gt; vert[elements.index(maxchain[i])] + 1: print "Witnessing chain: ", maxchain print "Witnessing vertex: ", vert return False return True </code></pre> <p>Counterexample:</p> <pre><code>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]]]) </code></pre> <p>Sage 5.0 output:</p> <pre><code>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 </code></pre> <p>Here is a picture of Q with the bad vertex:</p> <p><img src="http://mit.edu/~darij/www/poset.png" alt="alt text"></p> <p>Or, for a counterexample with global min and max:</p> <pre><code>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]]]) </code></pre> <p>Output:</p> <pre><code>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 </code></pre> <p>This R is just the Q with a global min and a global max added.</p> <p>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 <em>tight</em> 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.</p>