All Questions
Tagged with order-theory reference-request
69 questions
18
votes
2
answers
1k
views
Can all $\aleph_2$-dense subsets of $\mathbb{R}$ be isomorphic?
Let $\kappa$ be an infinite cardinal. For a subset $A \subseteq \mathbb{R}$, we say that $A$ is $\kappa$-dense if $|A \cap (a, b)| = \kappa$ for every interval $(a, b)$. By Cantor, any two $\aleph_0$-...
- 1,618
13
votes
2
answers
1k
views
What's the deal with De Morgan algebras and Kleene algebras?
The notion of Boolean algebras, and the corresponding classical propositional logic, is very standard, and it is easy to find information about them (for example, among many other such works, there is ...
- 32.5k
12
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 ...
- 5,822
12
votes
1
answer
949
views
Discrete version of Nullstellensatz?
Hi. I was reading the paper "On the foundations of combinatorial theory (VI): The idea of a generating function" by Doubilet, Rota and Stanley, and there is a relation treated which is very ...
- 902
11
votes
2
answers
682
views
On Applications of Forcing in Domain Theory
An interesting feature of domain theory is to use partial orders in order to provide a mathematical model for the computational approximation in a potentially infinite computational process (e.g. ...
11
votes
2
answers
570
views
Extending a partial order while preserving an automorphism
It is well known that if $(P, \leq)$ is a partial order then $\leq$ can always be extended to a linear order. This is sometimes called Szpilrajn´s theorem although it had been previously proved by ...
- 11.5k
10
votes
1
answer
396
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 ...
- 26.5k
10
votes
1
answer
492
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 ...
- 5,822
9
votes
2
answers
1k
views
Given a cardinal k, what's the biggest dense linear order with a dense subset of size k?
It's not hard to show that for any cardinal $\kappa$, there is no dense linear order without endpoints (DLO) of size greater than $2^{\kappa}$ that has a dense subset of size $\kappa$. But one can ...
- 3,982
9
votes
1
answer
542
views
Reference request: number of antichains of a partially ordered set
Let $\mathbb{N}$ denote the set of all positive integers. For each $n \in \mathbb{N}$, define the set $$ P_n = \{ (a,b) \in \mathbb{N} \times \mathbb{N} : 1 \leq a \leq b \leq n \} $$ and consider the ...
- 563
9
votes
0
answers
205
views
Reference for sparseness of incomparability graphs implying sparseness of covering graphs
If a partial order on $n$ elements has $m$ incomparable pairs, then its covering graph (aka Hasse diagram aka transitive reduction, the graph of pairs of elements that are comparable but are not the ...
- 18.6k
9
votes
0
answers
309
views
Higher-order dimension in posets: a reference request
Let $P = (X, \le)$ be a partially-ordered set. Then the dimension of $P$ is the minimum number of total orders over $X$ whose intersection yields $P$. Alternately, the dimension of $P$ is the minimum ...
- 4,462
8
votes
2
answers
483
views
Posets obtained from a semigroup by the definition $x \leq y \iff x \cdot y = x$
A po-groupoid is a groupoid $\langle A,\cdot\rangle $ such that the relation
defined by
$$
x \leq y \text{ if and only if } x \cdot y = x
$$
is a partial order on $A$, the order related to $\langle ...
- 1,124
8
votes
0
answers
227
views
Is there a 'local' version of Near Coherence of Filters?
The axiom Near Coherence of Filters (NCF) is known to be independent of ZFC.
Axiom (NCF I): For any two free ultrafilters $\mathcal D$ and $\mathcal E$ on $\mathbb N$, there exist finite-to-one ...
- 1,955
7
votes
3
answers
355
views
Extracting countable chains from linear orders
There is a well-known fact in infinite combinatorics asserting that for each infinite linear order $P$ there is a countable subset $R\subseteq P$ of order type either $\omega$ or $\omega^{*}$
(by $\...
- 11.3k
7
votes
5
answers
2k
views
Visualizing large posets
does somebody know if there is any software for visualizing very large posets? (like those in page 27 of this notes of Guenter Ziegler). They may arise (as in that text) by considering the face ...
7
votes
1
answer
579
views
Progress on determining which partial orders embed into the rationals
The following result is relatively well-known: (for example in Math StackExchange answer #37161)
For every countable linear order $(R,\prec)$, there is an $X\subseteq\mathbb Q$ such that $(R,\prec)$ ...
- 2,031
7
votes
0
answers
118
views
Dimension of a union of downsets
We have established the following result regarding the Dushnik–Miller dimension of posets.
Let $P$ be a poset with downsets $C, D \subseteq P$. If the dimensions of $C$ and $D$ are $m$ and $n$, ...
- 316
6
votes
2
answers
412
views
Characterising subsets of the reals as ordered spaces
There are concise and elegant characterisations of the real line as a topological space and as an ordered space in the literature. I am interested in the harder case of characterising subsets of the ...
- 188
6
votes
1
answer
237
views
Resource on how the definitions of subobjects for various categories can vary
I am looking for a reference on the different possible definitions of subobjects. According to a particular friend of mine, subobjects should be at least monomorphisms (up to slice isomorphism) and at ...
- 591
5
votes
2
answers
352
views
The cofinality of the poset $[\kappa]^{<\kappa}$ for a singular cardinal $\kappa$
For a cardinal $\kappa$ let $[\kappa]^{<\kappa}$ denote the family of subsets of cardinality $<\kappa$ in $\kappa$. The family $[\kappa]^{<\kappa}$ is endowed with the partial order of ...
- 41.8k
5
votes
2
answers
337
views
A "strong" Galois-Tukey connection between orders with suborders
(Background, may be skipped by the knowledgeable reader: A Galois-Tukey connection between two partial orders $(P,\le)$ and $(Q,\le)$ is a pair of maps $\varphi^+:P\to Q$ and $\varphi^-:Q\to P$ ...
- 14k
5
votes
1
answer
770
views
Intervals in posets: how to extend interval orders, Allen's algebra, and interval graphs to intervals of posets?
BACKGROUND
Assume a poset $\langle P, \le \rangle$. For two points $a,b \in P$
with $a \le b$, then $I = [a,b] = \{ x : a \le x \le b \}$ is the
interval between $a$ and $b$.
When $P$ is a chain (e....
- 53
5
votes
1
answer
177
views
Reference for statement that almost every $n$-element partial order has trivial automorphism group
I'm looking for a reference for the statement that almost every partial order on $n$ elements has trivial automorphism group. I've been told that this is a folklore result. Does anyone know of a ...
- 462
5
votes
1
answer
377
views
Generalized ordering on simplicial complex
The vertices of simplicial complexes are usually totally ordered so that face maps of each simplex can be defined easily for the purposes of homology. That gives an "oriented" simplicial complex.
But ...
- 221
5
votes
0
answers
201
views
Is this "trimming" of a supersolvable semimodular lattice known?
Let $L$ be a finite (upper) semimodular lattice. Recall that this means $L$ is graded and its rank function $\rho\colon L \to \mathbb{N}$ satisfies
$$ \rho(x) + \rho(y) \geq \rho(x\vee y)+\rho(x \...
- 24.2k
5
votes
0
answers
109
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 ...
- 12.5k
5
votes
0
answers
64
views
Characters on monotone functions
Characters on the semigroup $(C_{+}^{b}(\mathbb{R}^{d}),+)$, i.e. on bounded positive continuous functions with the ususal pointwise addition, are known to be of the form $C_{+}^{b}(\mathbb{R}^{d})\ni ...
- 289
4
votes
2
answers
657
views
Cantor theorem on orders
It is "a well-known theorem of Cantor", said Sierpinski (circa 1920), that every countable total order can be imbedded in the rationals, and he proceeds to demonstrate that, assuming the continuum ...
- 3,630
4
votes
3
answers
395
views
A characterisation of Boolean algebras
Let $M$ be a meet-semilattice with a least element $0$. Suppose there is an order-reversing involution $a \mapsto -a$ on $M$ such that for all $a, b \in M$, $a \wedge b = 0$ if and only if $b \le -a$....
- 4,728
4
votes
1
answer
209
views
Exactly how much (and how little) can partial ordered sets (classes) embed to the cardinalities
In the paper "Convex Sets of Cardinals", Truss mentioned a result of Jech:
If $M$ is a countable transitive model of ZFC, and $(P,<)∈M$ is a poset, then there exists a Cohen extension of ...
- 1,676
4
votes
1
answer
648
views
Characterizing $\omega_1$-like dense linear orderings
I recently came upon the following theorem which was attributed to J. Conway:
For each $A\subset \omega_1$, let $\Phi(A)$ be a linear ordering of type $\sum_{\alpha<\omega_1} \tau_\alpha$, where $\...
- 2,882
4
votes
1
answer
119
views
Antisymmetry of the stochastic order
An ordered topological space is a topological space $X$ equipped with a partial order $\leq$ which is closed as a subset of $X\times X$. By antisymmetry of $\leq$, it follows that the diagonal of $X$ ...
- 6,406
4
votes
2
answers
393
views
Embedding a linearly ordered free monoid into a linearly ordered group
A linearly ordered (shortly, l.o.) monoid is a triple $\mathbb M = (M, \cdot, \le)$ for which $(M, \cdot)$ is a (multiplicatively written) monoid and $\le$ is a total order on $M$ such that $xy < ...
- 10.5k
4
votes
1
answer
503
views
For what classes of comparability graphs are their complements also comparability graphs?
An interval graph is an intersection graph of real intervals, that is, an undirected graph whose vertices can be labeled with real intervals so that there is an edge between two vertices iff their ...
- 43
4
votes
1
answer
518
views
Strictly totally ordered semigroups - Looking for references
Let $\mathfrak A = (A, \cdot)$ be a semigroup (written multiplicatively). We say that $\mathfrak A$ is linearly orderable if there exists a total order $\le$ on $A$ such that $ac < bc$ and $ca < ...
- 10.5k
4
votes
0
answers
234
views
To whom is the classification of atomic, modular finite lattices due?
Here lattice means a poset with meets and joins. A lattice is called atomic if every element is a join of atoms. There are a few different ways to define modular for finite lattices: one is that the ...
- 24.2k
3
votes
1
answer
135
views
Concentration of sample median for iid Gaussians
Let $X_1, \dots, X_n$ be iid according to $\mathcal{N}(0, 1)$, and let $M_n$ be the median of the $X_1, \dots, X_n$. I recall reading a concentration inequality for $M_n$ that was (roughly) as follows:...
- 75
3
votes
2
answers
138
views
In the context of directed graphs is it standard notation to allow an element of an independent vertex set to be contained in a loop?
Given any relation $R$, that is, any set of ordered pairs, we can associate a unique digraph $D$ to our relation $R$ by setting $D=(\text{fld}(R),R)$ where $\text{fld}(R)=\text{dom}(R)\cup\text{rng}(R)...
- 2,506
3
votes
2
answers
320
views
Topological characterisations of properties of posets
Finite connected partially ordered sets are in bijective correspondence to connected finite topological spaces that satisfy T_0, see for example the Wikipedia article Finite topological space. Here ...
- 26.5k
3
votes
1
answer
173
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 ...
- 10.5k
3
votes
2
answers
475
views
Arithmetic of ordered sets more general than ordinals
Motivation. Having read about infinite time Turing machines and ω-languages, I was thinking about more general notions of languages and “computation time”. Languages over strings of length ...
- 1,185
3
votes
1
answer
162
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,585
3
votes
1
answer
210
views
Terminology question for maps between posets
Let $P$ and $Q$ be two poset (partially ordered sets) and $\phi : P \to Q$ an order-preserving function.
I would like to know whether there is a name and perhaps a different characterizations of such ...
- 408
3
votes
0
answers
95
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 ...
- 183
3
votes
0
answers
132
views
Duality for continuous lattices based on [0, 1]
A continuous lattice may be defined as a complete lattice in which arbitrary meets distribute over directed joins. A continuous lattice is naturally regarded as an algebraic structure where the ...
- 133
3
votes
0
answers
119
views
Generalizing disjointness
The following definition generalizes set-theoretic disjointess:
Definition 0. (Autonomy). Given a Lawvere theory $\mathsf{T}$, a $\mathsf{T}$-algebra $X$, and an indexed family $S$ of subalgebras ...
- 3,793
2
votes
1
answer
176
views
Generating totally ordered free commutative monoids
Let’s say I have a set $A$. I build the free commutative monoid $M$ generated by $A$.
When can a well-order on $A$ be extended to $M$, in a way that is compatible with its monoid structure? I am ...
- 341
2
votes
1
answer
208
views
Linearly ordered set arithmetic: reference request
A lot has been written about the arithmetic of ordinal numbers. However, we can also do arithmetic with linearly ordered sets.
Question. Is there an article or book where I can learn the basics of ...
- 3,793
2
votes
2
answers
341
views
Algorithm to compute certain poset from a given poset.
Hi. Associated with a finite poset $P$, one can consider the poset $S(P)$, whose elements are the intervals of $P$, ordered by inclusion. (See Discrete version of Nullstellensatz? for some motivation ...