All Questions
Tagged with order-theory co.combinatorics
111 questions
0
votes
1
answer
234
views
Minimum number of elements needed to represent a lattice with a union-closed family of sets
I know that it is possible to represent every finite lattice $L$ with a union-closed family $\mathcal{F}$ containing the empty set: for every $x\in L$, let $S_x=\{y\in L\, :\, y\not\geq x\}$ and $\...
- 1,000
35
votes
12
answers
4k
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 ...
- 1,644
16
votes
3
answers
10k
views
Proving that a poset is a lattice
I discovered experimentally that a certain finite poset (sorry, I cannot give its definition here) seems to be in fact a (non-distributive, non-graded) lattice. The covering relations are reasonably ...
- 4,219
6
votes
3
answers
236
views
Refinement-minimal intersecting covers
Motivation. Yesterday I was sitting idly in the train, contemplating the train network. I noticed that a lot of lines (not all) intersected, and some pairs of lines intersected in quite a few stations....
- 41.8k
28
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 ...
- 35.5k
2
votes
2
answers
271
views
Is every finite lattice isomorphic to a union-closed family of sets containing $\emptyset$?
If a family of sets $\mathcal{F} \subseteq 2^E$ is union-closed and contains $\emptyset$, then $\mathcal{F}$ forms a lattice under the set-inclusion order. To see this, note that unions give the join ...
- 459
4
votes
2
answers
467
views
Is every finite poset a subset of a finite complemented distributive lattice?
Let $(X,\succeq)$ be a poset. I have the following two questions:
Is it true that there exists a finite complemented distributive lattice (a Boolean lattice) $(S, \succeq^*)$ such that $X\subseteq S$ ...
- 24.2k
2
votes
1
answer
233
views
Order on Euclidean space in which a finite poset embeds
Fix positive integers $k$ and $n$.
For which finite posets $(X,\lesssim)$ with $\#X=k$ does there exist an order embedding $\phi\colon(X,\lesssim)\to (\mathbb{R}^n,\le)$, where $\le$ is the standard ...
- 47.2k
29
votes
0
answers
665
views
A conjecture about inclusion–exclusion
$\newcommand\calF{\mathcal{F}}
\def\cupdot {\stackrel{\bullet}{\cup}}
\def\minusdot {\stackrel{\bullet}{\setminus}}$This post presents a conjecture that we have with some colleagues. It is about ...
- 24.2k
6
votes
1
answer
254
views
Fixed points for finitary distributive lattices bijection
Birkhoff's Fundamental Theorem of Finite Distributive Lattices says that there is a bijection
$$ \{ \textrm{finite posets}\} \to \{ \textrm{finite distributive lattices}\} $$
$$ P \mapsto J(P), $$
...
- 50.8k
5
votes
1
answer
376
views
Kuratowski's 14 theorem and universal algebra
For a tuple of functions $\overline{p}$ on a set $Y$, let $cl_{\overline{p}}$ be the associated closure operation: $cl_{\overline{p}}(Z)$ is the smallest subset of $Y$ containing $Z$ and closed under ...
- 14.6k
4
votes
1
answer
216
views
Lattice description of matroid duality
Apologies for this very basic question in matroid theory, but I could not find anything about it online after a bit of searching.
There is a well-known bijective correspondence ("cryptomorphism&...
- 82.7k
4
votes
0
answers
125
views
Can we extend "every finite lattice is a sublattice of partitions of a finite set" to linear and/or finitary lattices?
Pudlák and Tůma https://link.springer.com/article/10.1007/BF02482893 proved that every finite lattice can be
embedded as a sublattice of the partition lattice of a finite set.
Can this be generalized ...
- 429
1
vote
0
answers
73
views
Ordered combinatorial classes and partitions
Let $\mathcal{C}$ be a combinatorial class and let $\leq$ be a partial order on $\mathcal{C}$. We say that $(\mathcal{C},\leq)$ is an ordered combinatorial class if for all $x,y\in\mathcal{C}$, $$x&...
- 63.9k
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 ...
- 24.2k
6
votes
3
answers
333
views
Does the rank (=height) of a well partial order bound its type (=length, =stature)?
Terminology and context
(This should all be standard, but is recalled because terminology sometimes varies, and also to put the question into perspective.)
A partially ordered set is called well-...
- 121
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 ...
4
votes
1
answer
182
views
Find an order-embedding of $S_3\times{\bf2}\times{\bf2}$ into ${\mathbb Z}^4$
A function $f:P\to Q$ from a poset $(P,\le_P)$ to a poset $(Q,\le_Q)$ is an order-embedding if, for all $p,p'\in P$, $p\le_P p'$ if and only if $f(p)\le_Q f(p')$.
We partially order the Cartesian ...
- 23.7k
6
votes
2
answers
291
views
"Minimal" connected matroids
I'm interested in connected matroids $M$ on the ground set $[n]$ for which there is no connected matroid on $[n]$ of the same rank but with a strictly smaller set of bases (by inclusion). Equivalently,...
- 1,046
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
3
votes
0
answers
127
views
A class of Kripke frames which preserves validity
The background of our discussion is intuitionistic logic, i.e. the following definitions are intuitionistic Kripke frame.
For $1\leq s\leq n-2$, the frame $\mathcal{C}_n(s)$ denotes the frame which is ...
- 53
14
votes
1
answer
625
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.
...
- 47.2k
10
votes
0
answers
265
views
Let $X$ be a finite set of $n$ ($>1$) elements and $\tau$ be a topology on $X$ having exactly $m$ elements. Can we give any description of $m$?
Let $X$ be a finite set of $n$ ($>1$) elements and $\tau$ be a topology on $X$ having exactly $m$ elements.
Can we give any description of $m$ as it relates to $n$?
Obviously $2\le m\le 2^n$ and ...
- 53.3k
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 ...
- 1,446
5
votes
0
answers
624
views
A poset with small "cycles"
(A followup to this recent question.)
I noticed the following curious property of a poset (which I strongly believe to be a lattice, I'm still trying to prove that…):
Suppose that $z$ is covered by $x$...
- 12.9k
1
vote
1
answer
107
views
The quantity of poset with a given number of pairs of incomparable elements
$\DeclareMathOperator\inc{inc}$Let $|X|=n$ and $\inc(X,\leq)=\{\{x,y\} : \neg (x\leq y)\wedge \neg (y\leq x)\}$, where $(X,\leq)$ is poset (possibly unconnected). Define the function:
$$\pi(n,m):=|\{(...
10
votes
2
answers
676
views
Status of Barany's conjecture?
One of Barany's most intriguing conjectures is about the $f$-vectors of convex polytopes. It asks:
Let $P$ be a convex $d$-polytope. Is it always true that $f_k \geq \min(f_0, f_{d-1})$?
A convex $...
- 13.6k
5
votes
1
answer
270
views
Question about a family of nested countable subsets of $\mathbb{R}$
Let $\mathcal{F}$ denote a family of countable subsets of $\mathbb{R}$, such that for each $U, V\in\mathcal{F}$ we have that $U\subseteq V$, or $V\subseteq U$. Let $(\mathcal{F}, \preceq)$ denote the ...
- 47.2k
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
6
votes
0
answers
188
views
Natural bijection between join- and meet-irreducibles in modular lattices?
A well known property of finite modular lattices is that they have the same number of join-irreducible and meet-irreducible elements. I was wondering if there exists a natural bijection between these ...
- 3,513
5
votes
1
answer
218
views
Classification of multiplicative lattices
Question 1:Is there a classification of finite lattices which admit a multiplication making them into a finite multiplicative lattices? (see https://encyclopediaofmath.org/wiki/Multiplicative_lattice ...
- 4,219
15
votes
5
answers
7k
views
infinite permutations
This question is related to this one: Continued fractions using all natural integers. Suppose we have the set of natural numbers $N$ with order and we perform permutation on it. So we obtain the same ...
- 1,446
4
votes
0
answers
58
views
Are the countable (rayless) trees with wqo labels wqo?
It has been proved by Corominas that the countable trees with vertex-labels coming from a better-quasi-ordered set are better-quasi-ordered. My question is whether this holds if we replace bqo by wqo ...
- 1,926
3
votes
1
answer
599
views
Sum of $q$-binomial coefficients
Denote by $ \binom{n}{k}_q = \prod_{i=0}^{k-1} \frac{ q^{n-i} - 1 }{ q^{k-i} - 1 } $, $ k = 0, 1, \ldots, n $, the $ q $-binomial (Gaussian) coefficients. These numbers are symmetric, in the sense ...
- 63.9k
7
votes
0
answers
139
views
poset of lattice properties
Is there a good overview of the dependencies between properties that a (finite) lattice poset can have?
To give a practical example, I was looking for a property weaker than congruence uniform and ...
- 5,822
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 ...
CommunityBot
- 1
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 ...
- 63.9k
3
votes
1
answer
169
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 ...
- 63.9k
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 ...
- 4,219
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
41
votes
3
answers
2k
views
What is the minimal size of a partial order that is universal for all partial orders of size n?
A partial order $\mathbb{B}$ is universal for a class $\cal{P}$ of partial orders if every order in $\cal{P}$ embeds
order-preservingly into $\mathbb{B}$.
For example, every partial order
$\langle\...
- 877
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
6
votes
1
answer
233
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{...
- 50.8k
8
votes
1
answer
634
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 ...
- 18.8k
18
votes
3
answers
794
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,219
3
votes
1
answer
176
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,...,...
- 39.7k
8
votes
2
answers
212
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\...
- 7,875
8
votes
2
answers
294
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 $...
- 50.8k
4
votes
1
answer
302
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)...
- 231
11
votes
0
answers
286
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 ...
- 4,416