All Questions
20 questions
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
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
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
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
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
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
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
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
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
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 ...
2
votes
0
answers
116
views
Isomorphic subcategories of directed graphs and presets
For the purposes of this post, a digraph (directed graph) has neither loops nor multiple parallel edges, and a preset is an ordered pair consisting of a set $S$ and a preorder (viz., a reflexive and ...
- 10.5k
2
votes
0
answers
95
views
A specific notion between the notions of transversal and system of distinct representatives.
Let $X$ be a set, let $\mathcal{C}$ be a collection of subsets of $X$, and let $x_1, \dots , x_k \in X$. Say that the sequence $\{x_i\}_{i=1\dots k}$ is a sequential transversal (of length $k$) ...
- 588
0
votes
0
answers
131
views
terminology: monotone maps of posets such that the image of a lower set is a lower set
How are called in combinatorics
monotone maps of partially ordered sets such that the image of a lower set is a lower set, i.e. closed (or open) maps of finite topologies? Is there a classification ...
- 113