Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 33 for “"linear-extensions"”.
-
Linear extensions of ordered sets.
Abstract Not Available.
-
Inference for partial orders from random linear extensions
… Observed orders are modelled as random linear extensions of suborders of an unobserved partial order h(P) evolving according to a stochastic process, and inference on the partial order is of interest.</p> <p>Chapter 1 reviews some static random partial order models. Of particular …
-
Properties of Some Markov Chains on Linear Extensions of Posets
… can be computed exactly and its eigenvalues are linear in the transition probabilities. This result has been generalized in different ways by various people. In this work, we investigate three generalizations given by the extended promotion Markov chain on linear extensions of a poset introduced …
-
The weak discrepancy and linear extension diameter of grids and other posets
A linear extension of a partially ordered set is simply a total ordering of the poset that is consistent with the original ordering. The linear extension diameter is a measure of how different two linear extensions could be, that is, the number of pairs of elements that are ordered differently by …
-
Coroutine-based combinatorial generation
… order, the Varol-Rotem algorithm for generating linear extensions in Gray order, and the Pruesse-Ruskey algorithm for generating signed linear extensions of a poset in Gray order, are given.
-
Order Theory and Nonparametric Analysis for Interval Censored Data
… data. We propose a method by which the set of linear extensions of an interval order may be partitioned into sets of linear extensions of weak orders, using so-called marked configurations of the interval order. The technique relies heavily on the natural linear ordering of maximal antichains …
-
Connecting the two worlds: well-partial-orders and ordinal notation systems
… collapsing functions #i correspond to maximal linear extensions of these well-partial-orders T (W ), hence also that these collapsing functions correspond to maximal linear extensions of Friedman’s famous well-partial-orders.
-
Efficient computation of rank probabilities in posets
… the probability space consists of the set of all linear extensions of a given poset equipped with the uniform probability measure, in first instance we develop algorithms to explore this probability space efficiently. We consider in particular the problem of counting the number of linear …
-
Cones of Hyperplane Arrangements
… \item chambers within the cone correspond to linear extensions of the poset, \item the Whitney numbers of the cone interestingly refine the number of linear extensions of the poset. \end{itemize} We interpret this refinement explicitly for two families of posets: width two posets, and disjoint …
-
On non-linear network embedding methods
As a linear method, spectral clustering is the only network embedding algorithm that offers both a provably fast computation and an advanced theoretical understanding. The accuracy of spectral clustering depends on the Cheeger ratio defined as the ratio between the graph conductance and the 2nd …
-
Minimizing setups in precedence constrained scheduling
… same, this problem is equivalent to finding a linear extension of a partial order with minimum number of jumps. This problem is well known as the jump number problem. For general partial orders, the jump number problem was shown to be NP-hard by Pulleyblank in 1981. We show that the problem is …
-
The Quicksort algorithm and related topics
… we obtain an alternative bound on the number of linear extensions when the partially ordered set arises from a random graph, and discuss the possible application of Shellsort in merging chains.
-
A New Characterization of V-Posets
… of UT U proceeds without row swaps is a linear extension of P. Autonomous posets arise from the theory of pressing sequences in graphs, a problem with origins in phylogenetics. The pressing sequences of a graph can be partitioned into families corresponding to posets; because of the …
-
Cataland
… miracle is that there are the same number of linear extensions of the root poset as reduced words of the longest element (in certain types), while the second is that there are the same number of order ideals in the root poset as certain group elements (in more types). We place these miracles …
-
An Application of Dempster-Shafer Fusion Theory to Lithium-ion Battery Prognostics and Health Management
… traditional Kalman filter, along with its non-linear extensions, and the particle filter. Each technique has differing advantages. This thesis investigates the fusion of results from different techniques in order to achieve a more trustworthy probability of detection (PoD) during diagnosis and …
-
Existence and uniqueness of solutions to non-linear first order dynamic equations on time scales
… As such, much of the basic (yet very important) linear theory has been established, however the non-linear extensions are yet to be fully developed. This thesis aims to fill this gap by providing the foundational framework of non-linear results from which further lines of inquiry can be launched. …
-
Progress on the 1/3 - 2/3 conjecture
… elements of P correspond to [n] = {1,2,...,n}. A linear extension is an order-preserving total order x_1 < x_2 < ... < x_n on the elements of P, and more compactly, we can view this as the permutation x_1x_2 ... x_n in one-line notation. For distinct elements x,y in P, we define P(x < y) to be the …
Page 1 of 2