Computing linear extensions for polynomial posets subject to algebraic constraints

S. Kepley; K. Mischaikow; L. Zhang

doi:10.1137/20M1343208

Computing linear extensions for polynomial posets subject to algebraic constraints

S. Kepley, K. Mischaikow, L. Zhang

Research output: Contribution to Journal › Article › Academic › peer-review

Abstract

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 language	English
Pages (from-to)	388-416
Journal	SIAM Journal on Applied Algebra and Geometry
Volume	5
Issue number	2
DOIs	https://doi.org/10.1137/20M1343208
Publication status	Published - 2021
Externally published	Yes

Funding

\ast Received by the editors June 5, 2020; accepted for publication (in revised form) March 16, 2021; published electronically June 28, 2021. https://doi.org/10.1137/20M1343208 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 ([email protected], [email protected], [email protected]).

Funders	Funder number
National Science Foundation	CCF-1934924, DMS-1622401, DMS-1839294, DMS-1521771
National Institutes of Health	R01 GM126555-01
Defense Advanced Research Projects Agency	FA8750-17-C-0054, HR0011-16-2-0033

Access to Document

10.1137/20M1343208

Persistent URL (handle)

Persistent link

Cite this

@article{2cf0bf47a40e46369c2c6e496326db87,

title = "Computing linear extensions for polynomial posets subject to algebraic constraints",

abstract = "Copyright {\textcopyright} 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.",

author = "S. Kepley and K. Mischaikow and L. Zhang",

year = "2021",

doi = "10.1137/20M1343208",

language = "English",

volume = "5",

pages = "388--416",

journal = "SIAM Journal on Applied Algebra and Geometry",

issn = "2470-6566",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "2",

}

TY - JOUR

T1 - Computing linear extensions for polynomial posets subject to algebraic constraints

AU - Kepley, S.

AU - Mischaikow, K.

AU - Zhang, L.

PY - 2021

Y1 - 2021

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

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

U2 - 10.1137/20M1343208

DO - 10.1137/20M1343208

M3 - Article

SN - 2470-6566

VL - 5

SP - 388

EP - 416

JO - SIAM Journal on Applied Algebra and Geometry

JF - SIAM Journal on Applied Algebra and Geometry

IS - 2

ER -

Computing linear extensions for polynomial posets subject to algebraic constraints

Abstract

Funding

Access to Document

Persistent URL (handle)

Fingerprint

Cite this