Questions tagged [order-theory]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
31 votes
5 answers
4k 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 ...
jkff's user avatar
  • 8,941
17 votes
4 answers
804 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 ...
Suresh Venkat's user avatar
16 votes
4 answers
450 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 ...
a3nm's user avatar
  • 9,269
15 votes
3 answers
1k views

Complexity of topological sort with constrained positions

I am given as input a DAG $G$ of $n$ vertices where each vertex $x$ is additionally labeled with some $S(x) \subseteq \{1, \ldots, n\}$. A topological sort of $G$ is a bijection $f$ from the vertices ...
a3nm's user avatar
  • 9,269
13 votes
2 answers
4k views

Lexicographically minimal topological sort of a labeled DAG

Consider the problem where we are given as input a directed acyclic graph $G = (V, E)$, a labeling function $\lambda$ from $V$ to some set $L$ with a total order $<_L$ (e.g., the integers), and ...
a3nm's user avatar
  • 9,269
13 votes
1 answer
442 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 ...
a3nm's user avatar
  • 9,269
13 votes
1 answer
272 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 ...
Suresh Venkat's user avatar
11 votes
2 answers
288 views

Determining what can be achieved by a permutation of elements of a noncommutative group

Fix a finite group $G$. I am interested in the following decision problem: the input is some elements of $G$ with a partial order on them, and the question is whether there is a permutation of the ...
a3nm's user avatar
  • 9,269
10 votes
2 answers
532 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 ...
Travis Service's user avatar
10 votes
1 answer
359 views

Lighting up all elements of a poset by toggling upsets

I consider the following game on a finite poset $(P, <)$. At each point of the game, I have a set of elements $S$ of the poset which are "on", and all others are "off". Initially $S = \emptyset$. ...
a3nm's user avatar
  • 9,269
10 votes
0 answers
138 views

Reconstructing labeled poset from linear extensions

Let $(P, <, \mu)$ be a labeled poset, that is, a partial order $(P, <)$ with a labeling function $\mu$ that maps the elements of $P$ to labels in an alphabet $\Sigma$. A label list (or word) is ...
a3nm's user avatar
  • 9,269
10 votes
0 answers
451 views

Illustrative Examples of Tarski's Fixed Point Theorems

I have come across many informal examples that provide a physical illustration for Brouwer's fixed point theorem (some due to Brouwer himself). A person walks from the bottom of a hill to the top. ...
Vijay D's user avatar
  • 12.6k
8 votes
2 answers
387 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 ...
zell's user avatar
  • 265
7 votes
1 answer
906 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 Poset-...
Fabrizio Silvestri's user avatar
6 votes
1 answer
118 views

Is every well-founded simplification order a well-partial order?

I'm contemplating the proof of Kruskal's Tree Theorem, as presented in the book "Term Rewriting and All That." They use it to prove that every simplification order is well-founded: first by showing ...
James Koppel's user avatar
5 votes
1 answer
989 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. ...
Arthur MILCHIOR's user avatar
5 votes
1 answer
100 views

If I naively generalize the homeomorphic embedding relation for labeled finite trees in this way, do I still have a wqo?

The homeomorphic embedding relation for trees as I understand it is a well-quasi-order (wqo) on trees when the label of a node determines the number of children of that node, and there are a finite ...
user's user avatar
  • 615
5 votes
0 answers
94 views

Series-parallel extension of a partial order respecting a given total order

Consider a partial order $P$, a series-parallel order $Q$ and a total order $R$, such that $P \subseteq Q \subseteq R$. Given $P$ and $R$, we are asked to find $Q$ of minimum length. An $O(n^3)$ ...
Alexander Tiskin's user avatar
5 votes
0 answers
205 views

Exact catchup point between SGH and FGH of ordinals?

An ordinal hierarchy is a way to assign a function $f_{\alpha} : \mathbb{N} \rightarrow \mathbb{N}$ to each (recursive) ordinal $\alpha$. The corresponding functions are expected to be monotone and ...
NisaiVloot's user avatar
  • 1,292
5 votes
0 answers
143 views

Structures admitting directed sums and directed products?

Some structures have a property of closure by a "sum" or "product" operation. Given a family of structures $(S_i)_{i \in I}$, we can then define a new structure denoted by $\sum_{i \in I} S_i$, resp. $...
NisaiVloot's user avatar
  • 1,292
4 votes
1 answer
306 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 ...
badroit's user avatar
  • 225
4 votes
0 answers
96 views

Residual for transitive hull

I work in the algebra $R$ of reflexive, transitive relations over some set $S$, ordered by subset inclusion. This is a complete lattice, with intersection as g.l.b. and transitive hull as l.u.b., i.e. ...
Uli Fahrenberg's user avatar
3 votes
0 answers
106 views

What conditions are necessary (and sufficient) for the order-dual of a Scott-Ershov domain to also be a domain?

That is, considering the underlying poset of a domain, when does the order-dual poset also comprise a domain? Below's a little, not strictly necessary, elaboration of that question. Usual ...
John Forkosh's user avatar
3 votes
0 answers
140 views

Convolution products in partial semigroups

A partial semigroup (or PSG) consists of a set $X$ and of a partial composition law $*$ defined over $X$, that is to say: (1) $x*y$ is not always defined, (2) if $(x*y)*z$ is defined, so is $x*(y*z)$...
NisaiVloot's user avatar
  • 1,292
3 votes
1 answer
133 views

Hook length formuli and their invariance properties?

Let $P = (V,\leq_P)$ be a poset, and for each $x \in V$ let $x^P = \{ y \in V : x \leq_P y \}$. A well-known property of certain posets (forests, Young diagrams) is the existence of a simple hook ...
NisaiVloot's user avatar
  • 1,292
2 votes
1 answer
59 views

Ordering sequences containing bitvectors for size-change termination

I'm working with the size-change termination principle to show program termination. In the system I work with, there is a so-called bit-vector ordering that goes as follows: Given two sequences of ...
user1868607's user avatar
  • 1,017
2 votes
1 answer
49 views

Two preorders with same glb

I have a set $S$ with two preorders $\mathord{\le}_1,\mathord{\le}_2\subseteq S\times S$ which a priori are unrelated. Let $\equiv_1$ and $\equiv_2$ be the induced equivalences (i.e., $x\equiv_1 y$ ...
Uli Fahrenberg's user avatar
2 votes
0 answers
108 views

Completeness of the quotient of the power set lattice of a partial order induced by the Hoare pre-order

Let $(P,\le)$ be a partially ordered set and $\preceq$ the Hoare pre-order on its subsets, i.e. for $X,Y\subseteq P$, $X\preceq Y$ iff $\forall x\in X:\exists y\in Y:x\le y$. Let $\sim$ be the ...
Uli Fahrenberg's user avatar
1 vote
1 answer
123 views

How to prove that Supremum preorder coincides with Hoare preorder?

Given a complete lattice $(L, \sqsubseteq)$ and a basis of completely $\sqcup$-irreducibles $B_L \subseteq L$, such that $\forall l \in L$, $l=\sqcup\{b \in B_L\ |\ b \sqsubseteq l\}$. I mean: Hoare ...
Denis Mazzucato's user avatar
1 vote
0 answers
123 views

Spectrum of a variety: a possible connection btw ordinals and structures?

Consider a variety of algebras $\mathbb{V} = \mathbb{V}(\sigma,\tau)$ which consists of the set of algebras defined over a fixed signature $\sigma$ and satisfying a set of identities $\tau$. We may ...
NisaiVloot's user avatar
  • 1,292
1 vote
0 answers
103 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 ...
DLaw's user avatar
  • 111