# Questions tagged [order-theory]

Questions about orders and their usage within formal contexts. This includes questions about both specific orders and orders in general.

35 questions
Filter by
Sorted by
Tagged with
50 views

1 vote
305 views

### The sorting problem for partially ordered sets

I have two questions about sorting for posets, one easy and one hard: Easy: Suppose we have a set of objects and a partial order. Given any two objects such that $a \leq b$, we want to delete $b$ ...
1k views

### Testing if a given DAG is a lattice

I am given a directed acyclic graph (DAG) with a unique source and sink. Is there an efficient way to test whether the partial order represented by this graph is a lattice? In other words, I need to ...
1k views

### Why is it that any graph traversal method can be described as pre-order, in-order, or post-order? What do those terms mean?

There are several graph traversal algorithms in computer science ( vis. depth first, breadth first, etc. ). Furthermore, each of these algorithms can be implemented in pre-order, in-order, and post-...
50 views

### Maximal Elements in a Lower Set

I have a collection of objects, and a feasibility property for sets of objects which is slow to compute. If a set is feasible then so is any subset. For example, it could be whether the set of things ...
146 views

### Scott/Lawson topology for function space domain

Given two domains, $D_1$, $D_2$, already equipped with Scott (or Lawson) topology, the product domain $D=D_1\times D_2$ has the Tychonoff product topology, e.g., Mathematical Theory of Domains, ...
44 views

### Original proof that orders eliminate deadlocks?

A well-known approach to eliminate the possibility of a deadlock when accessing exclusive ressources is enforcing a partial (or total) order in which the ressources may be requested. Which ...
1 vote
530 views

### Path optimization in a DAG: maximizing number of least cost arcs

I've got the following problem. I've a graph $G=(V,E)$ as in the picture and I have to calculate the optimal path from $R$ to $S$. The optimal path has to maximize the number of least cost arcs. In ...
71 views

### Total ordering of sets of fixed size

I'm curious if there is a name for this way of ordering finite sets of natural numbers (shown here for the case 3 elements, but can be extended to any number of them): ...
2k views

### Prove that any directed cycle in the graph of a partial order must only involve one node

So I have the question: Prove that any directed cycle in the graph of a partial order must only involve one node. So I know that a partial order must be transitive, antisymmetric, and reflective, ...
6k views

### Maintaining an efficient ordering where you can insert elements "in between" any two other elements in the ordering?

Imagine I have an ordering on a bunch of elements like so: Where an arrow $X \leftarrow Y$ means $X < Y$. It is also transitive: \$\left(X < Y\right) \wedge \left(Y < Z\right) \implies \left(...
10k views

### What are lattices used for?

Wikipedia says: Complete lattices appear in many applications in mathematics and computer science Is it just referring to the fact that the standard Boolean algebra used in computation is a ...