List All Events

Download as iCal file

Applied and Computational Math Seminar

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.