# Questions tagged [order-theory]

The order-theory tag has no usage guidance.

481
questions

**0**

votes

**0**answers

29 views

### Embedding of Coxeter groups into product of trees - Relationship between partial orders

Let $(W,S)$ be a Coxeter system. A result by Ranishnikov and Januszkiewicz (see Every Coxeter group acts amenably on a compact space for the construction) states that $W$ can be isometrically embedded ...

**5**

votes

**0**answers

99 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

26 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 ...

**6**

votes

**2**answers

286 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

108 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⊆\...

**16**

votes

**1**answer

616 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 with the ...

**0**

votes

**2**answers

110 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

44 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

100 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

74 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 ...

**1**

vote

**2**answers

71 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

302 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 $...

**0**

votes

**0**answers

59 views

### Closed set in product topology implies convergence of monotonic sequences

Let $(X,\succsim)$ be a metrizable and connected, totally ordered topological space with the order topology. Let $\succeq$ be another order relation on $X \times X$ such that the two orders are ...

**1**

vote

**1**answer

70 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

220 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

164 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 &...

**4**

votes

**0**answers

188 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

74 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

164 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

992 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

485 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 $\...

**0**

votes

**0**answers

27 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

120 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 ...

**24**

votes

**3**answers

1k 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

24 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\;\;\...

**11**

votes

**1**answer

272 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.
...

**0**

votes

**0**answers

23 views

### Entrywise matrix functions that preserve matrix majorization order

I am a beginner of majorization theory, reading the Olkin's book.
Let $A,B\in R^{d\times k}$. By befinition $A\prec B$ iff there exists $D$ doubly stochastic such that $A=BD$. In this case $B$ is ...

**1**

vote

**1**answer

76 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

194 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 ...

**1**

vote

**0**answers

44 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

216 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

167 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

136 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

99 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

97 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

46 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= ...

**2**

votes

**0**answers

459 views

### Braided lobsters

If $(X,m)$ is a median algebra, then for each $x\in X$, define an operation $\wedge_{x}$ by letting $y\wedge_{x}z=m(x,y,z)$. Then $(X,\wedge_{x})$ is a meet-semilattice with least element $x$. Define ...

**1**

vote

**0**answers

78 views

### A question about pdfs with likelihood ratio order

Suppose $f_1,f_2,\dots$ are pdfs of absolutely continuous random variables with the same support (say an interval). Assume that $\{f_i\}$ are strictly positive in their support. Furthermore, $\frac{...

**1**

vote

**1**answer

127 views

### Self-embeddings of uncountable total orders

A nice theorem of Dushnik and Miller (from 1940) states that if $(\Omega,\leq)$ is a countable total order, then either
there is an element $\omega \in \Omega$ such that $(\Omega \setminus \{\omega\}...

**5**

votes

**0**answers

145 views

### Infinitely many initial ideals for non-Artinian monomial orders?

Consider the polynomial ring $R=\mathbb Z[x_1,\ldots,x_n]$ and an ideal $I\subset R$. Let $<$ be a monomial order, i.e. a total order on the set of monomials in $R$ such that for any monomials $a$, ...

**2**

votes

**2**answers

176 views

### Is the intersection of Boolean sublattices a Boolean sublattice?

Let $L$ be a boolean lattice, $A$ and $B$ sublattices of $L$ that are
themselves boolean lattices, and suppose that $I = A \cap B$ is
nonempty.
Is $I$ a boolean sublattice of $L$? Is it a ...

**2**

votes

**2**answers

281 views

### (Types of) induction on infinite chains

This question may be trivial, or overly optimistic. I do not know (but I guess the latter...). I am a group theorist by trade, and the set-up I describe cropped up in something I want to prove. So ...

**1**

vote

**1**answer

130 views

### Countable union of well ordered sets [closed]

Assume I have a sequence $(A_i)_{i<\omega}$ of well-ordered subsets of an ordered set $S$. Assume that $A:=\underset{i<\omega}{\cup}A_i$ is also well-ordered. Let $\alpha$ be an ordinal upper ...

**4**

votes

**1**answer

701 views

### Is this lemma equivalent to the axiom of choice?

Given any pre-ordering $\preceq$ of an arbitrary set $X$ is the following lemma:
$$\text{There exists an inclusion minimal set }S\text{ satisfying }\{a\preceq b:b\in S\}=X\\\iff \text{ Every chain in ...

**1**

vote

**0**answers

82 views

### Generalization of the linear extension theorem to directed acyclic graphs

Using Zorn's lemma one can prove a generalization of the order extension theorem, that states any acyclic digraph is always contained in another acyclic unilaterally connected digraph on the same ...

**0**

votes

**1**answer

41 views

### Minimizing the set of “faulty” edges in a map between the vertex sets of $2$ graphs

The starting point of this question is the fact that for some simple, undirected graphs $G, H$ there is no graph homomorphism $f:G\to H$. This is the case for instance if $\chi(G)>\chi(H)$.
...

**1**

vote

**1**answer

122 views

### Basis or subbasis for Scott topology

Let $X$ be a partially ordered set. A subset $S\subseteq X$ is called Scott-open if and only if it is:
Upward-closed: $x\in S$ and $x\le y$ implies $y\in S$;
Inaccessible by directed suprema: if $D\...

**2**

votes

**1**answer

60 views

### Is the Scott topology generated by the ideals as the closed sets?

Let $X$ be a directed-complete partial order, or even a complete lattice. A subset $S\subseteq X$ is called Scott-closed if and only if it is:
Downward-closed: $y\in S$ and $x\le y$ implies $x\in S$;
...

**32**

votes

**11**answers

3k views

### Open questions about posets

Partially ordered sets (posets) are important objects in combinatorics (with basic connections to extremal combinatorics and to algebraic combinatorics) and also in other areas of mathematics. They ...

**6**

votes

**2**answers

344 views

### Poset dimension and width (Dilworth's theorem)

For a given poset $P$, let $\mathrm{dim}(P)$ denote the least cardinal $\kappa$ such that there exists a $\kappa$-sized collection of linear extensions of $P$, say $\mathcal{L}$, such that $\leq_P = \...