# Questions tagged [order-theory]

The order-theory tag has no usage guidance.

539
questions

**3**

votes

**2**answers

172 views

### "Pseudo-Boolean" lattice (almost every element has several complements)

If $(L,\leq)$ is a lattice with bottom element $0$ and top element $1$ and $x\in L$ we say that $y$ is a complement of $x$ if $x\vee y = 1$ and $x\wedge y = 0$.
Is there a lattice $(L,\leq)$ with more ...

**3**

votes

**1**answer

87 views

### A closed subset of a Dedekind-complete order has subspace topology equal to order topology

Here's a fairly easy fact from point-set topology that I'm having trouble finding a reference for. Say $X$ is a total order satisfying the least-upper bound property, and $S$ is a closed subset of it....

**2**

votes

**1**answer

124 views

### Is the set of "endomorphisms" of a directed set again a directed set?

Let $(I,\leq)$ be a directed set, that is $\leq$ is reflexive and transitive and for every $a,b\in I$ we find $c\in I$ such that $a,b\leq c$. Now consider the set $M$ consisting of all maps $\sigma:I\...

**2**

votes

**0**answers

93 views

### In a constructive order/lattice theory are the arbitrary join and the weak suprema the same?

For a poset $X$ we define an upperbound $w \in X$ of a subset $S \subseteq X$ to be a weak-supremum if
$(\forall a \in S (a \leq b)) \implies w \leq b$.
While a supremum is defined more carefully (in ...

**6**

votes

**0**answers

146 views

### A representation of a partial order by a slowly changing sequence of linear orders

We study visualizations of attractors, which occur in chaotic dynamic systems, and for a few years trying to prove or refute Conjecture [3]. It has an equivalent formulation in terms of order theory, ...

**1**

vote

**1**answer

84 views

### Density and compactness of Boolean embeddings

Let A and B be Boolean algebras and $h:A\rightarrow B$ a
Boolean embedding.
If every element of $B$ can be expressed both as a join
of meets and as a meet of joins of elements in $h(A)$, then the ...

**4**

votes

**0**answers

95 views

### Chains of length $2^\kappa$ in ${\cal P}(\kappa)$ [duplicate]

It is a fact that continues to boggle my mind: There is a set ${\cal C}\subseteq {\cal P}(\omega)$ such that $|{\cal C}|=\frak{c}=2^{\aleph_0}$ and for all $A,B\in{\cal C}$ we have $A\subseteq B$ or $...

**1**

vote

**0**answers

131 views

### Is there an algorithm to merge $d$ chains into $\left\lceil\frac{d}{k}\right\rceil$ chains?

I've come up with a problem as follow:
Given an integer $k > 1$, a queue $Q$ as a permutation of integers $1$ to $N$. You can apply an operation to the queue as follows:
split the queue into no ...

**1**

vote

**1**answer

50 views

### inequivalent vertex weights on finite poset

Let $m\geq1$ and $P$ be an arbitrary poset with vertex set $V=\{v_1,\dots,v_n\}$, edge set $E,$ and set $O$ of orbits under $\text{Aut}(P).$ Can we efficiently generate all inequivalent nonnegative ...

**4**

votes

**0**answers

93 views

### What do you call such a relation between subsets in a poset

Consider a poset $(X, \geq)$. Let's define a new relation $\succsim$ on subsets of $X$: for $A, B\subseteq X$, say $A\succsim B$ if for any $a\in A$ and any $b\in B$, we have $a\geq b$.
Does such a ...

**3**

votes

**1**answer

151 views

### Obtaining an antichain from affine subspace

Suppose $a\in \{0,1\}^n$ and $S \subseteq \mathbb{F}_2^n$ is a subspace of dimension $d$. Define an affine subspace $S_a$ as follows:
$$S_a=\{a+x \mid x\in S\}.$$
What is the largest possible size of ...

**3**

votes

**0**answers

82 views

### When is it possible to extend several linear orders defined "locally" into a single linear order defined "globally"?

This is a somewhat fuzzy question, so I will try my best to give a formulation which includes everything relevant while excluding everything else. I would like to find out if anyone else has studied ...

**8**

votes

**1**answer

623 views

### What is the theory of the random poset?

$\DeclareMathOperator\Th{Th}$The random poset is the Fraisse limit of the class of finite posets, just like the random graph is the Fraisse limit of the class of finite graphs? That is, the random ...

**6**

votes

**1**answer

171 views

### Maximal independent sets in MAD families

We call ${\cal A}\subseteq {\cal P}(\omega)$ almost disjoint if ${\cal A}\neq \varnothing$, every member of ${\cal A}$ is infinite, and for $A_1\neq A_2\in {\cal A}$ we have that $A_1\cap A_2$ is ...

**6**

votes

**1**answer

101 views

### Tameable hypergraphs

Let $H=(V,E)$ be a hypergraph. We say that $I\subseteq V$ is an independent set if $e\not\subseteq I$ for all $e\in E$.
We say that $H$ is tameable if every independent set is contained in a maximal ...

**9**

votes

**1**answer

263 views

### Origin and context of adjunctions inducing equivalences between full subcategories

The following is well-known.
Theorem. Let $F\dashv U$ be a pair of adjoint functors
$$F\colon \mathcal C\to \mathcal D, \qquad U\colon \mathcal D\to\mathcal C$$
with unit $(\eta_A\colon A\to U(F(A)))_{...

**1**

vote

**0**answers

61 views

### Monoids with three or more "natural" partial orders

For any given monoid $M$ there may exist lots and lots of compatible pre-orders $\leq$. Only few of these are usually any interesting though. I can find some examples of monoids that have two non-...

**1**

vote

**0**answers

71 views

### Strongly graded rings

In Theorem 3.1 of Graded rings over arithmetical orders, the authors prove that for a strongly $\mathbb{Z}$-graded ring $R$, if $R_0$ is left and right Goldie and a maximal order in its (classical) ...

**3**

votes

**1**answer

108 views

### Well-foundedness of divisibility vs well-foundedness of right- and left-divisibility

Say that a preorder (i.e., a reflexive and transitive binary relation) $\preceq$ on a set $X$ is
artinian if there is no sequence $(x_n)_{n \ge 1}$ of elements of $X$ with $x_{n+1} \prec x_n$ for ...

**4**

votes

**0**answers

109 views

### Cofinality without choice: can this coarse definition suffer badly?

This is a rephrased version of a question previously asked at MSE without success.
Working in $\mathsf{ZF}$, it is no longer possible in general to give every linear order an ordinal cofinality. For ...

**4**

votes

**0**answers

132 views

### Does every finite lattice embed into a finite Eulerian lattice?

A finite Boolean lattice is a lattice isomorphic to the subset lattice of a finite set. Every Boolean lattice is Eulerian, namely, a graded lattice $L$ such that $\mu(a,b) = (-1)^{|b|-|a|}$ for all $a,...

**0**

votes

**0**answers

54 views

### Is it true that the structure of a commutative ordered semiring is unique on a commutative ordered monoid?

Is it true that the structure of a commutative ordered semiring with identity is unique on a commutative ordered monoid (i.e., the structure of the monoid and the order are consistent)? I am not ...

**3**

votes

**1**answer

151 views

### ${\frak b}$ and ${\frak d}$ in the Rudin-Keisler preordering

If $(Q,\leq)$ is any preordered set (that is, $\leq$ is a reflexive and transitive, but not necessarily anti-symmetric relation), then we say that $S\subseteq Q$ is
unbounded if for all $q\in Q$ ...

**2**

votes

**0**answers

49 views

### closure operator on a complete lattice arising from adjunction on lattice itself

Define a closure operator on a complete lattice $L$ as a function $f:L \to L$ which is order preserving and idempotent and satisfies $x \leq fx$.
Every closure operator arises from an adjunction ...

**0**

votes

**1**answer

40 views

### Countable sup property of extended measurable functions

Let $(S,\Sigma,\mu)$ a $\mu$-finite measure space. Denote by $\bar{L}^0(\Sigma)$ the set of extended-real valued $\Sigma$-measurable functions. Does this set have the countable sup property when ...

**1**

vote

**1**answer

80 views

### Minimizing the set of monochromatic edges

For sets $A, B$ we write $B^A$ for the set of all functions $f:A\to B$.
Let $H = (V,E)$ be a hypergraph such that $V,E\neq\varnothing$ and $|e| \geq 2$ for all $e\in E$. Let $\kappa>1$ be a ...

**6**

votes

**1**answer

172 views

### Sum of order polynomials of a set of posets

Let $n\in \mathbb{Z}_{>0}$. For every subset $S\subseteq \left[ n-1\right]$ we define a poset $P_S=\left([n],\le_{P_S}\right)$ given by the covering relation $\lessdot$ which is defined as
\begin{...

**5**

votes

**1**answer

216 views

### Can one characterize maximal antichains in terms of distributive lattices?

This is inspired by the recent question Verification of a maximal antichain
The celebrated duality between finite posets and finite distributive lattices has several nice formulations. One of them ...

**8**

votes

**1**answer

243 views

### Verification of a maximal antichain

In order theory, an antichain (Sperner family/clutter) is a subset of a partially-ordered set, with the property that no two elements are comparable with each other. A maximal antichain is the ...

**1**

vote

**1**answer

123 views

### Is the Rudin-Keisler ordering a continuous relation?

If $X, Y$ are topological, and $R\subseteq X\times Y$ we say that $R$ is continuous (from $X$ to $Y$) if for every $V\subseteq Y$ with $V$ open, we have $$R^{-1}(V) = \{u\in U: \exists v\in V:(u,v)\...

**3**

votes

**1**answer

118 views

### Is there an explicit linear extension for the subsequence partial order?

Consider the set of finite sequences (of bounded length $\leq k$, if necessary) whose elements are taken from some finite alphabet $\Sigma$. We define a partial order on this set so that
$X = (X_1,...,...

**1**

vote

**1**answer

80 views

### A diffuse probability distribution in high dimensions with order constraints

Consider the following subset of the unit cube in $\mathbb R^n$:
$$
\mathcal D = \{ p = (p_1,p_2,\dots,p_n) \in [0,1]^n:\; p_1 \le p_2 \le \cdots \le p_n\}.
$$
We would like to construct a probability ...

**7**

votes

**2**answers

134 views

### Constructing a $0/1$ polytope from an abstract simplicial complex

Let us fix $\Delta$ a finite simplicial complex, and label the vertices of $\Delta$ as $\{1,2,\ldots,n\}$. For each $F\in \Delta$ let us consider the point in $\mathbb{R}^n$ given by:
$$e_F := \sum_{i\...

**0**

votes

**1**answer

81 views

### Ordering preserved by an inverse frame homomorphism

Recall that a frame homomorphism $h:L\to M$ is called ($L$ and $M$ are frames):
Dense if, for any $x ∈ L$, $h(x) = 0$ implies $x = 0$.
Codense if, for any $x ∈ L$, $h(x) = 1$ implies $x = 1$.
...

**16**

votes

**1**answer

644 views

### Suprema of directed sets

Let $(X, \le)$ be a partially ordered set. We call a subset $S \subseteq X$...
... a chain if each two elements in $S$ are comparable with respect to $\le$ (in other words, $S$ is linearly ordered ...

**0**

votes

**0**answers

19 views

### When is a frame isomorphic to its downset completion?

The downset completion $DX$ of a semi-lattice $X$ is a functor from meet semilattices to frames, with a right adjoint given by the forgetful functor. This adjunction induces a monad on frames (let's ...

**8**

votes

**2**answers

184 views

### Euler characteristic of the simplicial complex of sets of elements in a semilattice with non-zero meet

In a combinatorial computation, I came across the following quantity:
Consider a finite meet semilattice $L$, that is, a finite poset which is closed under $\min$. Denote the least element of $L$ by $...

**14**

votes

**1**answer

730 views

### Does there exist an ordering-functor?

This sounds like a very silly question which should have have a negative answer but I don't see an argument. The precise question is this:
Does there exist a covariant functor $ord$ from the category ...

**5**

votes

**2**answers

340 views

### Non-homeomorphic connected $T_2$-spaces with isomorphic topology poset

What are examples of non-homeomorphic connected $T_2$-spaces $(X_i,\tau_i)$ for $i=1,2$ such that the posets $(\tau_1, \subseteq)$ and $(\tau_2,\subseteq)$ are order-isomorphic?

**5**

votes

**1**answer

249 views

### Complete Boolean algebras of subsets of $\mathbb N$

Let $\mathfrak A$ be a subset of $\mathrm{Pow}(\mathbb N)$, the powerset of $\mathbb N$. Assume that $\mathfrak A$ is a complete Boolean algebra in the induced order, i.e., the inclusion order. Does ...

**18**

votes

**3**answers

645 views

### What is the minimum size of a partial order containing all partial orders of size 5?

This earlier MO question asks to find the minimum size of a partial order that is universal for all partial orders of size $n$, i.e. any partial order of size $n$ embeds into it, preserving the order. ...

**4**

votes

**1**answer

292 views

### How to define a function that has these specific properties?

Suppose $x = (x_1,x_2,\dots,x_K) \in \mathbb{Z}^K_{\geq 0}$. For $x,y \in \mathbb{Z}^K_{\geq 0}$, we write $x \succ y$ or $y \prec x$ if $x \neq y$ and
\begin{align*}
x_{i(x,y)} > y_{i(x,y)...

**11**

votes

**0**answers

213 views

### Existence of a strong antichain

Call an antichain (set of pairwise incomparable elements) $A$ of a poset $P$ strong if for every $p,q \in P$ with $p \leq q$ there exists an $a\in A$ which is comparable with both $p$ and $q$.
...

**11**

votes

**0**answers

211 views

### Does every finite poset have a rigid endomorphism?

Crossposted on Mathematics.
In this post, an order-preserving self-map of a poset $X$ will be called an endomorphism of $X$, and such an endomorphism $f$ will be called rigid if the only automorphism ...

**5**

votes

**0**answers

116 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

137 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})$ ...

**23**

votes

**1**answer

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

**8**

votes

**1**answer

305 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

193 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

306 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\})...