# Questions tagged [order-theory]

The tag has no usage guidance.

539 questions
Filter by
Sorted by
Tagged with
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 ...
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....
124 views

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
263 views

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 ...
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$ ...
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 ...
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 ...
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 ...
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{...
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 ...
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 ...
123 views

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$. ...
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 ...
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 ...
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 $... 1answer 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 ... 2answers 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? 1answer 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 ... 3answers 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. ... 1answer 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 yand \begin{align*} x_{i(x,y)} > y_{i(x,y)... 0answers 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$. ... 0answers 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 ... 0answers 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 ... 1answer 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})$... 1answer 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 ... 1answer 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 ... 0answers 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 ...
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\})...