The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
1answer
57 views

Pairs distance to ordering?

Thanks to anon for contributing this wording: Every permutation $\pi:\{1,\cdots,n\}\to\{1,\cdots,n\}$ induces an $n\times n$ array $A(\pi)$ of the absolute differences, whose $ij$ entry is ...
1
vote
2answers
90 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 ...
1
vote
0answers
9 views

Algorithm for partial order width [duplicate]

I want to compute the partial order width i.e. the size of the maximum antichain in a given partial order. By Dilworth's Theorem this is the same as minimal chains required to decompose the graph, ...
1
vote
0answers
12 views

Complete Partial Order of Partial Functions with Different Outputs

Since a partial function can be seen as a set of tuples, there is a trivial CPO defined by the subset relation on partial functions of the same (co-)domain. However, this is not really useful. What ...
3
votes
1answer
200 views

What is the name of the property where $f(A) \supseteq f(B)$ when $A\supseteq B$?

Suppose I have a function $f$ on sets. What is the property of $f$ called when, for all sets $x$, $y$: $f(x)$ is a superset of $f(y)$ when $x$ is a superset of $y$ i.e. $$\forall x,y : ...
1
vote
1answer
50 views

What kind of order is binary tree ancestry?

Let isAncestor be a relation on binary tree nodes such that isAncestor x y means y can be ...
2
votes
2answers
127 views

Search in a partial ordering defined by tuples of numbers

This is a graph theory and partial ordering problem. Consider a set of triples {(di,ai,ci)}i=1...N, which specify edges between two nodes A and B, d denotes a departure time, a an arrival time and c a ...
5
votes
1answer
135 views

What does Tarski's Fixed-Point theorem give us that that Y-Combinator does't

I'm taking a graduate course on the theory of functional programming, based on Paul Taylor's "Practical Foundations of Mathematics." I understand the statement of Tarski's theorem about how for any ...
2
votes
2answers
179 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, ...
-1
votes
1answer
106 views

How to prove substring is a partial order

u is defined to be a substring of a string v if v = xuy for some string x and y. Either or both possibly empty. How to you prove that a substring relation on any set of strings is a partial order?
0
votes
1answer
95 views

trouble with bijection definition [closed]

I have a bijection problem that I cannot get my head around. It goes like this: let f: A -> B and g: B -> C be functions such that g o f is a bijection. Prove that f must be one-to-one and that g ...
5
votes
3answers
1k 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 ...
4
votes
1answer
71 views

Extracting the set of chains from a partial order

Given a partial ordered set (poset) $S$, is there a known procedure or algorithm to find the set of chains (i.e. subsets of $S$ where every two elements are comparable)? Note: I am asking here ...
3
votes
1answer
130 views

Is there an efficient method to store large DAGs?

I have a DAG representing strict partial order where each node is an assignment of variables $V$ to their values $v$. Each arc $(u,w)$ represents a change in one variable value such that $u\succ w$. ...
1
vote
2answers
136 views

Are these two relations on integers partial orders?

Are the following relations $R_1$ and $R_2$ defined on the set $\mathbb{Z}$ of integers partial orders? (A partial order is reflexive, antisymmetric and transitive.) $a$ $R_1$ $b$ if and only if $a ...
3
votes
2answers
161 views

Given many partial orders, check them for consistency and report any that are not consistent

Inputs. I am given a finite set $S$ of symbols. I know there should exist some total order $<$ on $S$, but I'm not given this ordering and it could be anything. I am also given a collection of ...