Questions tagged [order-theory]
The order-theory tag has no usage guidance.
644
questions
5
votes
0
answers
177
views
Additional examples of classes of networks whose Hasse diagram of the poset is a perfect graph
This question is very important for my research, which is why I ask it here.
I do not have a formal background in graph theory so please excuse me if I state a term incorrectly (and feel free to ...
4
votes
1
answer
143
views
Maximal order of an order-preserving map
Let $X$ be a finite partially ordered set, let $f\colon X\to X$ be an order-preserving map [edit: meaning $x\le y\implies f(x)\le f(y)$], and let $x_0$ be an initial point. Define $x_n = f(x_{n-1})$ ...
25
votes
1
answer
1k
views
Expected height of a poset?
I am interested in any known results/empirical studies done on the average height of a poset with $N$ elements. Obviously this would depend on how that poset relation was randomly defined, however, at ...
10
votes
1
answer
381
views
Generalising the union-closed sets conjecture from lattice to a larger class of posets
(edit: I decided to simplify the question and only pose it for bounded posets first)
The Union-closed sets conjecture is equivalent for lattices P to:
There exists a join-irreducible element $a$ with ...
3
votes
0
answers
254
views
Poset of antichains of given cardinality
Throughout all posets will be finite.
Let $P$ be a poset, and let $\mathcal{A}(P)$ denote the set of antichains of $P$. We give $\mathcal{A}(P)$ a partial order whereby $A \leq A'$ iff for all $x \in ...
14
votes
1
answer
348
views
Comparing sizes of sets of integers
Is there a total preorder $\lesssim$ on the power set of $\mathbb Z$ such that:
$A<B$ if $A\subset B$ (proper subsets are smaller)
$1+A\lesssim 1+B$ iff $A\lesssim B$ (where $1+C = \{1+c:c\in C\})...
1
vote
0
answers
99
views
About a type of permutations
How many permutations are there on the set $\{1,2, \cdots, n\}$ ($n\geq 3$), such that any three elements are not in increasing or decreasing order? For example, for $n=3$ we have $(1,3,2), (2,1,3), (...
7
votes
0
answers
179
views
On thinking of spacetime as a local Scott domain
An observation of Martin and Panangaden links the study of Lorentzian manifolds and the semantics of programming languages via the theory of Scott domains.
Background:
Recall that if $M$ is a time-...
2
votes
0
answers
66
views
Convex hull of prefix sum of $n$ ordered random points
Suppose we have $n$ ordered realizations of a random variable uniformly distributed over the unit cube $P = (p_1, p_2, \cdots, p_n), p_i \in [0,1]^d $. And we obtain the prefix sum $S = (p_1, p_1+p_2, ...
3
votes
1
answer
154
views
How to construct a lattice having a subset of a given relations?
I am given a (smallish, say $n=14$ element) set $X$, and a set $R$ of (a few hundred) quadruples of elements $(a, b, c, d)$ with $a,b,c, d\in X$.
I want to construct lattices on $X$, such that for all ...
2
votes
2
answers
483
views
Is there a name for order-preserving functions $f$ where “$a\le b$ if and only if $f(a) \le f(b)$”? [closed]
This is something only slightly stronger than monotonicity. I think that in category theory this would be a fully faithful functor, but I’m not sure if there is a standard name for this in order ...
4
votes
1
answer
229
views
Measurable total order
Under what conditions on a metric space $X$, equipped with the Borel $\sigma$-algebra, does there exist a measurable total ordering of the elements of $X$?
By "measurable total ordering" we ...
11
votes
11
answers
1k
views
Lattices on classical combinatorial families
I am asking for examples of lattices defined on classical combinatorial families, such as Permutations, Catalan objects, set partitions or integer partitions, graphs.
I am mosty interested in lattices ...
10
votes
1
answer
484
views
is there a ‘nice’ lattice on the set of unlabelled graphs with $n$ vertices?
It is easy to endow the set of vertex-labelled graphs with $n$ vertices with a lattice structure: take the union and the intersection of the edge set as meet and join respectively.
However, I wonder ...
2
votes
0
answers
95
views
Non-commutative version of the order dimension of a poset
I view the order dimension of a poset $P$ as an inherently commutative notion. On the one hand, it can be defined via realizers, which I find fairly intuitive from an order-theoretic viewpoint. On the ...
1
vote
0
answers
36
views
Does a total preorder on lotteries that preserves countable mixtures preserve arbitrary mixtures?
Let $X$ be a countable set. A lottery on $X$ is a function $\lambda: X \to [0,1]$ such that $\sum_x \lambda(x) = 1$. Let $\Delta X$ be the set of lotteries on $X$.
A total preorder $\preceq$ on $\...
6
votes
1
answer
238
views
A monotone countably unbounded function from $\omega^\omega$ to $\omega^{\omega_1}$
For a set $X$ we endow the set $\omega^X$ of all functions from $X$ to $\omega$ with the natural partial order $\le$ defined by $f\le g$ iff $f(x)\le g(x)$ for all $x\in X$. A function $\mu:\omega^\...
11
votes
1
answer
408
views
A monotone countably cofinal function from $\omega^\omega$ to $\omega^{\omega_1}$
For a set $X$ we endow the set $\omega^X$ of all functions from $X$ to $\omega$ with the natural partial order $\le$ defined by $f\le g$ iff $f(x)\le g(x)$ for all $x\in X$.
A function $f:\omega^\...
1
vote
0
answers
36
views
Posets which extend centered sets to filters
(Post cross-posted from math.se.)
Suppose $(\mathcal O, \leq)$ is an arbitrary poset. Let us say that $\mathcal O$ is compact if every $\mathcal C\subseteq\mathcal O$ which is centered (any finite ...
10
votes
2
answers
425
views
Class of lattices that excludes $M_3$?
It is well known that a lattice is distributive iff it excludes as a sublattice $N_5$ (the pentagon) and $M_3$ (three unordered elements with a top and bottom). Further, a lattice that only excludes $...
5
votes
1
answer
163
views
Preserve unbounded sets between different cofinality
Working in ZFC, let $\kappa,λ$ be cardinals with $\kappa>λ$, and assume that $\kappa$ is regular.
We say that a function $F:\kappa^n→λ$, for some finite $n$, is preserving unbound, if for all $a⊆\...
17
votes
1
answer
1k
views
Has the exponentiation of ordinals a nice geometric model?
It is well known that the sum $\alpha+\beta$ of two ordinals $\alpha,\beta$ can be defined "geometrically" as the order type of the sum $(\{0\}\times \alpha)\cup(\{1\}\times\beta)$ endowed ...
0
votes
2
answers
484
views
The union of two cuts is a cut?
Every poset $\langle P, \leq \rangle$ has a Dedekind-MacNeille completion, a complete lattice that embeds $\langle P, \leq \rangle$.
For $A \subseteq P$, the upset $U(A) = \{p \in P\ |\ \forall a \in ...
5
votes
0
answers
100
views
Reference request: a survey of (linear) Krein-Rutman theory
I'm looking for a survey article or book chapter where a rather exhaustive treatment of the Krein-Rutman theory of positive linear operators an ordered Banach spaces is given.
Motivation. Some ...
3
votes
2
answers
121
views
Explicit lifting characterization of complete lattices among posets?
It's well-known that the complete lattices are characterized among all posets as the regular-injectives. That is, a poset $L$ is a complete lattice if and only if $L$ has the right lifting property ...
2
votes
1
answer
85
views
Dubious matrix monotonicity
Coming from a problem in game theory, I arose at some dubious monotonicity like property for matrices of the following art. Let $H=\lbrace h\in\mathbb{R}^{n}\colon h_{1}+\dots+h_{n}=0\rbrace$. I'm ...
0
votes
2
answers
97
views
Is this ordering on the set of all covers of $\omega$ a (complete) lattice?
Let ${\frak C} \subseteq {\cal P}({\cal P}(\omega))$ be the collection of all covers of $\omega$ (that is, ${\cal C} \in {\frak C}$ iff $\bigcup {\cal C} = \omega$.)
We define the following binary ...
5
votes
1
answer
352
views
Calculate the $\downarrow$, $\downarrow\uparrow$ and $\uparrow\downarrow$ cofinalities of the poset of nontrivial finitary partitions of $\omega$
Let $(P,\le)$ be a poset. For a point $x\in P$ let
$${\downarrow}x=\{p\in P:p\le x\}\quad\text{and}\quad{\uparrow}x=\{p\in P:x\le p\}$$be the lower and upper sets of the point $x$, and for a subset $...
1
vote
1
answer
134
views
Thinning directed sets ${\frak P}$ of partitions of $\omega$ with no ${\frak P}$-discrete subsets
This question branches from Taras Banakh's recent question on a cardinal characteristic connected to families of partitions that are directed in the ordering of partition refinement.
A partition $\...
4
votes
1
answer
277
views
Does the lattice of partitions map onto the lattice of subsets?
Let $X\neq \emptyset$ be a set and let $X^X$ denote the collection of all functions $f:X\to X$. We put a binary relation (reflexive and transitive), the composition preorder on $X^X$ by setting for $f,...
6
votes
1
answer
182
views
Self-embeddings of uncountable total orders, 2
Let $S = (\Omega,\leq)$ be an uncountable dense total order, such that for all positive integers $m$ and all finite ordered sequences $a_1 < a_2 < \ldots < a_m$ and $b_1 < b_2 < \ldots &...
10
votes
1
answer
737
views
How can you order a free group?
A left order on a (discrete) group $G$ is a total order on $G$ satisfying $\forall g,h,k \in G: g < h \implies kg < kh$. A right order is defined symmetrically, and a biorder is an order that is ...
1
vote
0
answers
85
views
Name for partial orders which are total on connected components
In my context, I encounter a lot of partial orders with the distinguished property that the order is total on connected components. Equivalently, they satisfy the condition
$$x \le y,z \enspace \lor \...
10
votes
1
answer
245
views
Is there a relation between type (maximum linearization) of a computable WQO and the ordinal strength of a theory needed to prove it?
Background:
Given a well partial order $X$ (more commonly studied with antisymmetry dropped as well-quasi-orders, but I'm going to say well partial order to make this definition simpler, obviously ...
8
votes
1
answer
1k
views
Wikipedia article on forbidden graph substructures
I apologies if this is too trivial a question or if I am over complicating anything here. But I was hoping for some clarification in an article I was reading about forbidden graph substructures on ...
2
votes
3
answers
531
views
Consistency of embedding cardinals in linear orderings
Background
The fact that there is no suborder of $\mathbb R$ which is of type $\omega_1$ suggests (to me) that the continuum $c$ cannot be very far from $\omega_1$: How could $c$ be far away from $\...
1
vote
0
answers
43
views
Linear maps that increase majorization order
Let $x$ a vector in $d$ dimensions with positive entries summing to one (a probability distribution). Is there a characterization of the linear operators $T:R^{d}_{+}\to R^{d}_{+}$ such that:
$$
x\...
2
votes
1
answer
181
views
Explicit calculation of the width of a product of chains (i.e. maximal rank size)
Given a poset $P$, I am interested in the width (size of the maximal antichain) of $\mathcal{O}(P)$, i.e. the poset of downsets in $P$, ordered by inclusion.
As this is rather difficult, I'm starting ...
26
votes
3
answers
2k
views
When does a graph underlie the Hasse diagram of a poset?
For any finite poset $P=(X,\leq)$ there is a graph $G$ underlying its Hasse diagram $H=(X,\lessdot)$, so that $V(G)=X$ and $E(G)=\{\{u,v\}:u\lessdot v\}$. With that said, is it possible to ...
0
votes
0
answers
36
views
Majorization for vector valued function: looking for literature
Let $x,y\in R^{d}$. A function $f:R^{d}\to R$ is called Schur convex if
$$
x\prec y\;\;\rightarrow\;\;f(x)\leq f(y).
$$
I am interested in functions $g:R^{d}\to R^{d}$ such that
$$
x\prec y\;\;\...
14
votes
1
answer
581
views
On certain order-automorphisms of the rationals
Consider the rationals $\mathbb{Q}$ with the usual order $\leq$. Now let $A$ be a subset of $\mathbb{Q}$, such that foreseen with the induced order $\leq$, $(A,\leq)$ is a dense linear order.
...
1
vote
1
answer
96
views
Are non-trivial interval-isomorphic posets lattices?
We say that a partially ordered set $(P,\leq)$ is interval-isomorphic if for all $a<b \in P$ we have $P \cong [a,b]$, where $[a,b]=\{x\in P:a\leq x\leq b\}$.
Suppose $(P,\leq)$ is interval-...
6
votes
1
answer
206
views
Pairwise non-isomorphic interval-isomorphic lattices
Let us call a lattice $(L,\leq)$ interval-isomorphic if for all $a<b \in L$ we have $L \cong [a,b]$, where $[a,b]=\{x\in L:a\leq x\leq b\}$.
Are there $2^{\aleph_0}$ pairwise non-isomorphic ...
2
votes
0
answers
75
views
$\sigma$-fields as closure systems
Let $(\Omega,\mathcal A, P)$ be a probability space and let $\Sigma(\mathcal A) \subset 2^{\mathcal A}$ be the collection of all sub-$\sigma$-fields of $\mathcal A$. Then, $\Sigma(\mathcal A)$ is ...
2
votes
1
answer
391
views
Generalizing König's Lemma
In some recent work, I need a strengthening of König's Lemma to "trees" of arbitrary ordinal heights. Trees, in this context, are really just well-founded partially ordered sets. See, for instance, ...
1
vote
2
answers
234
views
Mapping of subcubes of a $(d+k)$-hypercube onto subcubes of a $d$-hypercube
Denote by $Q_n$ the $n$-dimensional hypercube. A vertex of $Q_n$ is represented by a vector of $n$ $\{0,1\}$-bits. An edge corresponding to two vertices whose vectors differ in one coordinate is ...
6
votes
0
answers
173
views
Generalized graph-minor theorem?
Consider the following generalized graph-minor theorem:
GM($κ,λ$): Given any collection $S$ of $κ$ simple undirected graphs each with less than $λ$ vertices, there are distinct graphs $G,H$ in $S$ ...
1
vote
1
answer
183
views
Can we order random variables in a measurable way in a general setup?
Let
$(\Omega,\mathcal A,\operatorname P)$ be a probability space
$(E,\mathcal E)$ be a measurable space
$n\in\mathbb N$
$X_1,\ldots,X_n$ be $(E,\mathcal E)$-valued random variables on $(\Omega,\...
1
vote
2
answers
184
views
Reference request: lower sets of a preorder form a lattice
Consider a set $S$ with a preorder $\preceq$ (a preorder is a reflexive and transitive relation). A lower set $A$ of $S$ is defined as a subset of $S$ such that for all $x \in S$ and $y \in A$, if $...
0
votes
0
answers
58
views
Rewriting a set of integers to get rid of repetition but keeping subset sum ordering
Say, I have a set of 6 +ve integers sorted in ascending order:
$A = \{2,4,4,4,5,7\}$
Now to make it easier to deal with (Minimum one starts with 1) I deducted one from all of them:
$\therefore B= ...