The order-theory tag has no wiki summary.
4
votes
1answer
182 views
Efficient representation of set of partial order
I guess that notions I describe are already well known, may be by combinatorician, but I do not know their name or any book/article about them. So if you have a link/title I would love to read it.
...
13
votes
4answers
285 views
Worst number of questions needed to learn a monotonic predicate over a poset
Consider $(X, \leq)$ a finite poset over $n$ items, and $P$ an unknown monotonic predicate over $X$ (i.e., for any $x$, $y \in X$, if $P(x)$ and $x \leq y$ then $P(y)$). I can evaluate $P$ by ...
11
votes
1answer
207 views
Minimal elements of a monotonic predicate over the powerset $2^{|n|}$
Consider a monotonic predicate $P$ over the powerset $2^{|n|}$ (ordered by inclusion). By "monotonic" I mean: $\forall x, y \in 2^{|n|}$ such that $x \subset y$, if $P(x)$ then $P(y)$. I am looking ...
10
votes
1answer
180 views
A question on linear extensions of partial orders
If you're given a collection of partial orders, topological sort will tell you if there's an extension of the collection to a total order (an extension in this case is a total order consistent with ...
8
votes
2answers
138 views
Sufficient conditions to guarantee unique fixpoint (not unique least/greatest fixpoint) for monotone functions on complete lattice
Tarski's fixpoint theorem states, that the fixpoints of a monotone operator on a complete lattice is a complete lattice. By consequence, we have a unique greatest fixpoint and unique least fixpoint ...
1
vote
0answers
91 views
What effect would using different types of orders have on a binary search tree?
Recently, I was coding a comparator function for use in a set backed by a binary search tree, and the set kept saying that it didn't contain elements that I had previously added to it. I eventually ...
21
votes
5answers
3k views
Binary search generalizations for posets?
Suppose I have a poset "S" and a monotonic predicate "P" on S.
I want to find one or all maximal elements of S satisfying P.
EDIT: I'm interested in minimizing the number of evaluations of P.
What ...
6
votes
1answer
241 views
On finding a chain decomposition of a Partial Order
I am reading a paper by Daskalakis et al. entitled "Sorting and Selection in Posets". http://arxiv.org/abs/0707.1532
In that paper it is presented an enhancement to the algorithm ...
9
votes
1answer
292 views
Lattice problems
There has been a fair amount of work on computational problems for partial orders (e.g., recognition, jump number, comparability graph recognition, etc...).
I am curious what work specific to ...
4
votes
1answer
100 views
Measures of “correlation” between two orderings
An easy question perhaps?
Taking a (fictional) concrete example, let's say I have two ranking methods for HTML documents: PageRank and HITS. I derive an ordered list over the same set of documents ...
15
votes
4answers
481 views
Applications of metric structures on posets/lattices in theoryCS
Since the term is overloaded, a brief definition first. A poset is a set $X$ endowed with a partial order $\le$. Given two elements $a,b \in X$, we can define $x \vee y$ (join) as their least upper ...
