Notes on Combinatorics (V) chains in distributive lattice

---

tags: Combinatorics

Write it at the front

This part is mainly the third part of combinatorics of numbers 3.5 and 3.6 Section content .

Simple properties of distributive lattices

Easy to verify :

• $P$ Of $k$ The number of ordered ideals is equal to $J(P)$ The middle rank is $k$ Number of elements of .
• $P$ in $k$ Meta inverse chain $(k\ge 1)$ The number of is equal to $J(P)$ Which just covers $k$ Number of elements of elements

proposition 1

set up $P$ Is a finite poset and $m\in \mathbb{N}$, Is the following number equal :

1. Order preserving mapping $\sigma :P\to \mathbf{m}$ The number of ,
2. $J(P)$ The medium length is $m$ The heavy chain of $\hat{0}=I_0\le I_1\le \cdot \cdot \cdot \le I_m=\hat{1}$ The article number ,
3. $J(P\times \mathbf{m}-1)$ The number of elements in .

prove : ( Constructive bijection )

$\sigma :P\to \mathbf{m}$,( Posets $P$ To $m$ Mapping of meta chains ) Definition $I_j={\sigma }^{-1}(\mathbf{j})$, Given $\hat{0}=I_0\le I_1\le \cdot \cdot \cdot \le I_m=\hat{1}$, Definition $J(P\times \mathbf{m}-1)$ The order ideal of is

$$I=\{(x,y)\in P\times \mathbf{m}-1:x\in I_{m-j}\},$$

Define the above $\sigma$ by : If there is $j$ bring $(x,j)\in I$, be $\sigma (x)=\min \{m-j:(x,j)\in I\}$, If it does not exist , be $\sigma (x)=m$. This constitutes a bijection satisfying the above condition . Or directly by $1,3$ obtain :

$${\mathbf{m}}^P\cong (2^{\mathbf{m}-1}{)}^P\cong 2^{\mathbf{m}-1\times P}.$$

proposition 2

set up $P$ Is a finite poset and $m\in \mathbb{N}$, Is the following number equal :

1. Order preserving surjection $\sigma :P\to \mathbf{m}$ The number of ,
2. $J(P)$ The medium length is $m$ Chain $\hat{0}=I_0<I_1<\cdot \cdot \cdot <I_m=\hat{1}$ The article number .

• $P$ Extension to total order ($P$ Linear extension of ): If $|P|=n$, Then order preserving bijection $\sigma :P\to \mathbf{n}$.
• Number of expansions Write it down as $e(P)$, It's obviously equal to $J(P)$ The number of middle maximal chains .

Distributive lattice and lattice count

Can be $P$ Extension to total order $\sigma :P\to \mathbf{n}$ Equate to $P$ Arrangement of elements in : ${\sigma }^{-1}(1),...,{\sigma }^{-1}(n)$, Or will $J(P)$ The maximal chain of is equivalent to that in the following Euclidean space " grue ".

hypothesis $C_1,C_2,\cdots ,C_k$ by $P$ A chain partition of , (Dilworth The theorem infers that $k$ The minimum possible value of is $P$ The maximum cardinality of the anti chain of ), Define mapping $\delta :J(P)\to {\mathbb{N}}^k$ ,$\delta (I)=(|I\cap C_1|,|I\cap C_2|,\cdots ,|I\cap C_k|)$.

give ${\mathbb{N}}^k$ Product order , be $\delta$ Is a simple lattice homomorphism , And maintain the coverage relationship , ($J(P)$ Isomorphism ${\mathbb{N}}^k$) A sub lattice of , If you select each $|C_i|=1$, A rank preserving simple lattice homomorphism is obtained $J(P)\to B_n$, In the area $|P|=n$.)

Given $\delta :J(P)\to {\mathbb{N}}^k$, Definition ${\Gamma }_{\delta }={\bigcup }_{T}cx(\delta (T))$, among $cx$ Express ${\mathbb{R}}^k$ The convex hull in $T$ Take over $J(P)$ Is isomorphic to the interval of Boolean algebra . ${\Gamma }_{\delta }$ yes ${\mathbb{R}}^k$ A compact polyhedron subset of .

$J(P)$ The number of longest chains in is equal to at ${\Gamma }_{\delta }$ From the origin $(0,0,...,0)=\delta (\hat{0})$ To $\delta (\hat{1})$ The number of lattice paths , Each step moves one unit along the axis .

namely , Number of expansions $e(P)$ Equal to $\delta (\hat{1})$ Expressed as $\delta (\hat{1})=v_1+v_2+\cdots +v_n$ The number of ways , Each of them $v_i$ Is in ${\mathbb{R}}^k$ A unit vector in , And for all $i$, Yes ${\sum }_{k=1}^i{v}_k\in {\Gamma }_{\delta }$.

example 1:( Do not hand in and ) concrete problems

For the following poset , take $C_1=\{a,c\},C_2=\{b,d,e\}$.

Use the method in the previous section , It is easy to find $J(P)$, As shown in the figure below , Marked the element :

Mark with the above coordinates , You can get :

In the figure: $\varnothing$ To $abcde$, From $(0,0)$ To $(2,3)$, Yes $9$ An alternative way , therefore $e(P)=9$.

example 2:( Do not hand in and ) A general example

set up $P=C_1+C_2$, And $|C_1|=m,|C_2|=n$, be ${\Gamma }_{\delta }$ For one $m\times n$ Rectangular mesh , therefore $e(P)=\left(\genfrac{}{}{0ex}{}{m+n}{n}\right)$, From the perspective of linear order expansion , structure $\sigma :P\to \mathbf{m}+\mathbf{n}$, Completely by $\sigma (C_1)$ determine , by $\mathbf{m}+\mathbf{n}$ Arbitrarily $m$ Meta subset , From this, we can get $e(P)=\left(\genfrac{}{}{0ex}{}{m+n}{m}\right)$.

Extension :

If $P=P_1+\cdots +P_k,n_i=|P_i|$, be

$$e(P)=\left(\genfrac{}{}{0ex}{}{n_1+\cdots +n_k}{n_1,\cdots ,n_k}\right)e(P_1)\cdots e(P_k).$$

example 3: ( The cartesian product )

set up $P=2\times \mathbf{n}$, take $C_1=\{(2,j):j\in \mathbf{n}\}$, $C_2=\{(1,j):j\in \mathbf{n}\}$, be $\delta (J(P))=\{(i,j)\in {\mathbb{N}}^2:0\le i\le j\le n\}$. When $n=3$, namely $P=2\times 3$, Posets $P$ As shown below :

Easy to get $J(P)$ Here's the picture :

This is equivalent to not passing through $y=x$ The number of lattice paths that only go up and right one lattice , Obviously, the picture shows $5$. In a general way , $e(2\times \mathbf{n})=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$.

Recursive relations

take $e$ regard as $J(P)$ The function on , That is, if $I\in J(P)$, be $e(I)$ Express $I$ As $P$ The number of partially ordered subsets of the extension to totally ordered sets , therefore $e(I)$ Equal to the $J(P)$ In the from $\hat{0}$ To $I$ The number of saturated chains . therefore

$$e(I)=\sum _{I^{\prime }}e(I^{\prime }),$$

among $I^{\prime }$ Take over $J(P)$ in $I$ All elements covered , Similar to Yanghui triangle , $e(I)$ It happens to be $I$ Below $e(I^{\prime })$ And .

A simple example is $P=\mathbb{N}+\mathbb{N}$, remember $J_f(P)$ by $P$ Lattice of finite ordered ideals of , Then there are $J_f(P)\cong \mathbb{N}\times \mathbb{N}$.