Questions tagged [partial-order]

The tag has no usage guidance.

57 questions
Filter by
Sorted by
Tagged with
547 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?
157 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 ...
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(... 1answer 112 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 ... 1answer 170 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$. ... 2answers 236 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.)$aR_1b$if and only if$a = ...
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 ...