All Questions
Tagged with order-theory combinatorics
269
questions
0
votes
1
answer
45
views
Number of lattices over a finite set
I'm interested in finding a general formula for the number of lattices possible over a finite set $S$ as a function of the set's cardinality.
For instance, how many lattices over $\{1, 2, 3\}$ are ...
- 3,468
1
vote
0
answers
40
views
List of all posets of size $n$ for small $n$? [duplicate]
Is there a good reference for, or an easy way of generating, all Hasse diagrams of partially ordered sets of small size (say $n\leq 6$)? I am familiar with the OEIS entry A000112 listing the number of ...
- 1,307
2
votes
0
answers
29
views
Counting the number of posets with fixed dimension
I'm reading through a few of Trotter's papers on dimension and cardinality over certain posets, and I was curious about some combinatorial questions on posets with fixed dimension.In particular, what ...
- 63
0
votes
0
answers
53
views
Ranking and unranking of a binary subset
Let's consider "N" bits.
We want to rank and unrank a specific subset of bit combinations based on the following criteria -
...
- 13
0
votes
0
answers
15
views
Number of initial segments in a certain poset
For $[n] = \{1,\dotsc,n\}$, the set $\binom{[n]}{k}$ of $k$-element subsets of $[n]$ has a partial order $\leq_p$ induced by the total order on $[n]$. An element $S$ of the set $H(n, k, l) := \binom{\...
- 2,254
1
vote
0
answers
37
views
Binary subset rank and unrank [closed]
Let there be N=5 bits.
We want to rank and un-rank a specific subset of bits based on the following criteria -
...
- 13
4
votes
1
answer
82
views
Induction does not preserve ordering between cardinality of sets?
Consider building a binary tree and consider it as a collection of points and edges. Here is one with five levels, numbered level $1$ at the top with $1$ node to level $5$ at the bottom with $16$ ...
- 6,360
2
votes
1
answer
53
views
Möbius function of distributive lattice only takes values $\pm 1$ and $0$.
In this Wikipedia article, I found the statement
[...] shares some properties with distributive lattices: for example, its Möbius function takes on only values 0, 1, −1.
My question is: How it can ...
- 23.1k
2
votes
1
answer
41
views
The join of two set partitions in the refinement order
Let $X$ be a set. The set $\Pi_X$ of all partitions of $X$ is partially ordered via the refinement order, which is defined by $\alpha \leq \beta$ if and only if for each block $A\in \alpha$ there is a ...
- 23.1k
6
votes
1
answer
191
views
Number of surjective functions with given property
Let $n \in \mathbb{N}, n \geq 2$ and $M = \{1, 2, \ldots, n\}$. Show that there are more than $2^n$ surjective functions $f : \mathcal{P}(M) \rightarrow \{0, 1, \ldots, n\}$ such that $f(A) \leq f(B)$ ...
- 175
1
vote
0
answers
28
views
Relabel According to the Order of First Occurrence
Let $a\in\mathbb R^n$ be a tuple of length $n\in\mathbb Z_{>0}$. Let $X=\{a_i:1\le i\le n\}$ be the set of elements of $a$. For $x\in X$ let
$$i(x)=\min\{j:a_j=x\}$$
be the first occurence of $x$ ...
- 3,633
1
vote
1
answer
42
views
How are the two definitions of Eulerian posets equivalent?
I have been following Stanley's Enumerative combinatorics for the definition of an Eulerian poset. It is defined as follows:
Definition: A finite graded poset $P$ with $\hat{0}$ and $\hat{1}$ is ...
- 73
1
vote
1
answer
39
views
Definition of 2-chain in Posets
The definition of a 2-chain comes from Fayer's paper at: https://qmro.qmul.ac.uk/xmlui/bitstream/handle/123456789/64468/Fayers%202-chains%3A%20an%20interesting%202020%20Accepted.pdf?sequence=2&...
- 61
2
votes
0
answers
35
views
Number of partial orders such that a given function is monotone (order homomorphism)?
Given a set $X$, a poset $(Y, \preceq)$, and an arbitrary function $f: X \to Y$, how many partial orders $\le$ can one construct on $X$ such that $f$ becomes an order homomorphism $(X, \le) \to (Y, \...
- 1,458
0
votes
1
answer
54
views
How many topological orders does the following directed acyclic graph have?
Q: How many topological orders does the following directed acyclic graph have? You may basically think of it as putting numbers on a $2\times 6$ table such that the number at the right or down is ...
- 470