Questions tagged [order-theory]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...
mathlyfe's user avatar
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})$ ...
grok's user avatar
  • 2,489
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 ...
AspiringMat's user avatar
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 ...
Mare's user avatar
  • 25.7k
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 ...
Sam Hopkins's user avatar
  • 22.5k
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\})...
Alexander Pruss's user avatar
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), (...
cl4y70n____'s user avatar
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-...
Tim Campion's user avatar
  • 60.5k
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, ...
yupbank's user avatar
  • 183
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 ...
Martin Rubey's user avatar
  • 5,513
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 ...
Mitchell Buckley's user avatar
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 ...
Aryeh Kontorovich's user avatar
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 ...
Martin Rubey's user avatar
  • 5,513
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 ...
Martin Rubey's user avatar
  • 5,513
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 ...
Rene's user avatar
  • 51
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 $\...
aduh's user avatar
  • 839
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^\...
Taras Banakh's user avatar
  • 40.7k
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^\...
Taras Banakh's user avatar
  • 40.7k
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 ...
tomasz's user avatar
  • 1,184
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 $...
Gershom B's user avatar
  • 123
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⊆\...
Holo's user avatar
  • 1,533
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 ...
Taras Banakh's user avatar
  • 40.7k
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 ...
gnarizard's user avatar
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 ...
Jochen Glueck's user avatar
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 ...
Tim Campion's user avatar
  • 60.5k
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 ...
Tobsn's user avatar
  • 289
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 ...
Dominic van der Zypen's user avatar
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 $...
Taras Banakh's user avatar
  • 40.7k
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 $\...
Dominic van der Zypen's user avatar
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,...
Dominic van der Zypen's user avatar
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 &...
THC's user avatar
  • 4,313
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 ...
Ville Salo's user avatar
  • 6,337
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 \...
Tobias Fritz's user avatar
  • 5,775
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 ...
Harry Altman's user avatar
  • 2,535
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 ...
Ethan Splaver's user avatar
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 $\...
Rodrigo Freire's user avatar
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\...
Fabio's user avatar
  • 329
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 ...
Gershom B's user avatar
  • 123
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 ...
Ethan Splaver's user avatar
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\;\;\...
Fabio's user avatar
  • 329
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. ...
THC's user avatar
  • 4,313
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-...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
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 ...
passerby51's user avatar
  • 1,639
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, ...
Pace Nielsen's user avatar
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 ...
Evgeny Kuznetsov's user avatar
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$ ...
user21820's user avatar
  • 2,734
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,\...
0xbadf00d's user avatar
  • 161
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 $...
Artemy's user avatar
  • 650
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= ...
Moni's user avatar
  • 11

1 2 3
4
5
13