List All Events
Computing linear extensions of partial orders subject to algebraic constraints
Shane Kepley, Rutgers University
Location: Hill 425
Date & time: Friday, 13 September 2019 at 12:00PM - 1:00PM
Abstract: Switching systems have been extensively used for modeling the dynamics of gene regulation. This is partially due to the natural decomposition of phase space into rectangles on which the dynamics can be completely understood. Recent work has shown that the parameter space can also be decomposed into ``nice'' subsets. However, computing these subsets, or even determining if they are empty turns out to be a difficult problem.
We will show that computing a parameter space decomposition is equivalent to computing all linear extensions of a certain poset. The elements of this poset are polynomials and this structure induces additional algebraic constraints on the allowable linear extensions. We will describe an algorithm for efficiently solving this problem when the polynomials are linear. A more general class of polynomials can also be handled efficiently through a transformation which reduces to the linear case. Finally, we present several open problems and conjectures which arise when one generalizes this problem to subsets of arbitrary polynomial rings.