Computing linear extensions for polynomial posets subject to algebraic constraints

S. Kepley, K. Mischaikow, L. Zhang

Research output: Contribution to JournalArticleAcademicpeer-review


Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.In this paper we consider the classical problem of computing linear extensions of a given poset which is well known to be a difficult problem. However, in our setting the elements of the poset are multivariate polynomials, and only a small "admissible"" subset of these linear extensions, determined implicitly by the evaluation map, are of interest. This seemingly novel problem arises in the study of global dynamics of gene regulatory networks in which case the poset is a Boolean lattice. We provide an algorithm for solving this problem using linear programming for arbitrary partial orders of linear polynomials. This algorithm exploits this additional algebraic structure inherited from the polynomials to efficiently compute the admissible linear extensions. The biologically relevant problem involves multilinear polynomials, and we provide a construction for embedding it into an instance of the linear problem.
Original languageEnglish
Pages (from-to)388-416
JournalSIAM Journal on Applied Algebra and Geometry
Issue number2
Publication statusPublished - 2021
Externally publishedYes


\ast Received by the editors June 5, 2020; accepted for publication (in revised form) March 16, 2021; published electronically June 28, 2021. Funding: The authors acknowledge support from NSF DMS-1521771, DMS-1622401, DMS-1839294, the NSF HDR TRIPODS award CCF-1934924, DARPA contracts HR0011-16-2-0033 and FA8750-17-C-0054, and NIH grant R01 GM126555-01. \dagger Department of Mathematics, Rutgers University, Piscataway, NJ 08854 USA (,,

FundersFunder number
National Science FoundationCCF-1934924, DMS-1622401, DMS-1839294, DMS-1521771
National Institutes of HealthR01 GM126555-01
Defense Advanced Research Projects AgencyFA8750-17-C-0054, HR0011-16-2-0033


    Dive into the research topics of 'Computing linear extensions for polynomial posets subject to algebraic constraints'. Together they form a unique fingerprint.

    Cite this