Skip to main content
edited body
Source Link

Addendum: One has the more precise result that the degree of $P_{\Pi}(N)$ is exactly $n+1-|\Pi|$, because the sign of $\mu(\hat{0},\gamma)$$\mu(\hat{0},\Gamma)$ is $(-1)^{n-|\Gamma|}$. The coefficient of $N^{n+1-|\Pi|}$ is $$ (-1)^{|\Pi|-1}\sum_{\Gamma\in{\rm Part}_n} \mathbf{1}\{|\Gamma|=n+1-|\Pi|,\Pi\vee\Gamma=\hat{1}\} \prod_{A\in\Gamma}(|A|-1)! $$ which is easily seen to be nonzero. I don't know if one can actually compute its value.

Addendum: One has the more precise result that the degree of $P_{\Pi}(N)$ is exactly $n+1-|\Pi|$, because the sign of $\mu(\hat{0},\gamma)$ is $(-1)^{n-|\Gamma|}$. The coefficient of $N^{n+1-|\Pi|}$ is $$ (-1)^{|\Pi|-1}\sum_{\Gamma\in{\rm Part}_n} \mathbf{1}\{|\Gamma|=n+1-|\Pi|,\Pi\vee\Gamma=\hat{1}\} \prod_{A\in\Gamma}(|A|-1)! $$ which is easily seen to be nonzero. I don't know if one can actually compute its value.

Addendum: One has the more precise result that the degree of $P_{\Pi}(N)$ is exactly $n+1-|\Pi|$, because the sign of $\mu(\hat{0},\Gamma)$ is $(-1)^{n-|\Gamma|}$. The coefficient of $N^{n+1-|\Pi|}$ is $$ (-1)^{|\Pi|-1}\sum_{\Gamma\in{\rm Part}_n} \mathbf{1}\{|\Gamma|=n+1-|\Pi|,\Pi\vee\Gamma=\hat{1}\} \prod_{A\in\Gamma}(|A|-1)! $$ which is easily seen to be nonzero. I don't know if one can actually compute its value.

added 450 characters in body
Source Link

Addendum: One has the more precise result that the degree of $P_{\Pi}(N)$ is exactly $n+1-|\Pi|$, because the sign of $\mu(\hat{0},\gamma)$ is $(-1)^{n-|\Gamma|}$. The coefficient of $N^{n+1-|\Pi|}$ is $$ (-1)^{|\Pi|-1}\sum_{\Gamma\in{\rm Part}_n} \mathbf{1}\{|\Gamma|=n+1-|\Pi|,\Pi\vee\Gamma=\hat{1}\} \prod_{A\in\Gamma}(|A|-1)! $$ which is easily seen to be nonzero. I don't know if one can actually compute its value.


Addendum: One has the more precise result that the degree of $P_{\Pi}(N)$ is exactly $n+1-|\Pi|$, because the sign of $\mu(\hat{0},\gamma)$ is $(-1)^{n-|\Gamma|}$. The coefficient of $N^{n+1-|\Pi|}$ is $$ (-1)^{|\Pi|-1}\sum_{\Gamma\in{\rm Part}_n} \mathbf{1}\{|\Gamma|=n+1-|\Pi|,\Pi\vee\Gamma=\hat{1}\} \prod_{A\in\Gamma}(|A|-1)! $$ which is easily seen to be nonzero. I don't know if one can actually compute its value.

added some links with references
Source Link

First I will rephrase the question, and then I will solve the rephrased problem.

Let ${\rm Part}_n$ denote the set of set partitions of $[n]=\{1,2,\ldots,n\}$. For $\Theta,\Pi\in {\rm Part}_n$, we will say that $\Theta$ is finer than $\Pi$ and write $\Theta\le \Pi$, when $$ \forall A\in\Theta, \exists B\in\Pi, A\subset B\ . $$ The $\subset$ notation here allows equality. This defines the well-known partition lattice $({\rm Part}_n,\le)$. The smallest element denoted by $\hat{0}$ is the partition made of singletons. The largest element denoted by $\hat{1}$ is the single block partition. We will use $\vee$ to denote the join or supremum of two partitions in ${\rm Part}_n$.

The lattice has a Möbius function $\mu(\Theta,\Pi)$ given by the entries of the matrix $(\mu(\Theta,\Pi))_{\Theta,\Pi\in{\rm Part}_n}$ which by definition is the inverse of the matrix $(\mathbf{1}\{\Theta\le \Pi\})_{\Theta,\Pi\in{\rm Part}_n}$. We used the notation $\mathbf{1}\{\cdots\}$ for the indicator function equal to $1$ if the enclosed condition is true, and equal to $0$ if the condition is false. An explicit formulaexplicit formula for the Möbius function is given by $$ \mu(\Theta,\Pi)=\prod_{A\in\Pi}\left[(-1)^{s(\Theta,A)-1}(s(\Theta,A)-1)!\right] $$ where $s(\Theta,A)$ is the number of blocks of $\Theta$ contained in $A$.

The following lemma reflects the graded/ranked property of the partition lattice.

Lemma: If $\Theta_1,\Theta_2\in{\rm Part}_n$, then $|\Theta_1\vee\Theta_2|\ge|\Theta_1|+|\Theta_2|-n$.

Proof: For $i=1,2$, pick $F_i$ a forest (subgraph of the complete graph with no circuit) whose partition of connected components is $\Theta_i$. We have $|\Theta_i|=n-|F_i|$. By eliminating redundant edges which create circuits instead of new connections, pick a forest $F_3\subset F_1\cup F_2$ such that the partition of connected components of $F_3$ is exactly $\Theta_1\vee\Theta_2$. Since $|F_3|\le |F_1|+|F_2|$, the wanted inequality follows.

The notation $(x)_k:=x(x-1)\cdots(x-k+1)$ is for the falling factorial. We now define $$ K_{\Pi}(N):=\sum_{\Theta\ge \Pi}(-1)^{|\Theta|}(|\Theta|-1)! \times\prod_{A\in\Theta}\left[\prod_{j=1}^{|A|-1}\left(1-\frac{j}{N}\right)\right] $$ $$ =\sum_{\Theta\ge \Pi}(-1)^{|\Theta|}(|\Theta|-1)! \times\prod_{A\in\Theta}\left(\frac{(N-1)_{|A|-1}}{N^{|A|-1}}\right) $$ $$ =\sum_{\Theta\ge \Pi}(-1)^{|\Theta|}(|\Theta|-1)! \times\prod_{A\in\Theta}\left(\frac{(N)_{|A|}}{N^{|A|}}\right) $$ $$ =-N^{-n}\ P_{\Pi}(N) $$ where we introduced the polynomial, in $N$, $$ P_{\Pi}(N):=\sum_{\Theta\ge \Pi}\mu(\Theta,\hat{1}) \prod_{A\in\Theta} (N)_{|A|}\ . $$ If I understood correctly, the question is to show the existence of a constant $C_n$, only depending on $n$, such that for all $N>0$ $$ |K_{\Pi}(N)|\le C_n N^{1-|\Pi|}\ , $$ i.e., $$ |P_{\Pi}(N)|\le C_n N^{n-|\Pi|+1}\ . $$ The means the degree of the polynomial $P_{\Pi}$ is at most $n-|\Pi|+1$.

Using Stirling numbers of the first kindStirling numbers of the first kind, and their definition in terms of permutations in the symmetric group $\mathfrak{S}_k$, we have $$ (x)_k=\sum_{\rho\in\mathfrak{S}_k}{\rm sgn}(\rho) x^{c(\rho)} $$ where $c(\rho)$ is the number of cycles of the permutation $\rho$. Grouping permutations according to the set partition corresponding to their cycles we have $$ (x)_k=\sum_{\Theta\in{\rm Part}_k}(-1)^{k-|\Theta|}x^{|\Theta|} \prod_{A\in\Theta}(|A|-1)! $$ $$ =\sum_{\Theta\in{\rm Part}_k}\mu(\hat{0},\Theta)x^{|\Theta|} $$ where the Möbius function is that of ${\rm Part}_k$. By taking the product of the previous identity over the blocks of some partition $\Theta\in{\rm Part}_n$, and expanding, we have $$ \prod_{A\in\Theta} (N)_{|A|}=\sum_{\Gamma\le\Theta}\mu(\hat{0},\Gamma)N^{|\Gamma|} $$ where the Möbius function is that of ${\rm Part}_n$.

As a result, $$ P_{\Pi}(N)=\sum_{\Theta\ge\Pi}\mu(\Theta,\hat{1}) \left(\sum_{\Gamma\le \Theta}\mu(\hat{0},\Gamma)N^{|\Gamma|}\right) $$ $$ =\sum_{\Gamma\in{\rm Part}_n}\mu(\hat{0},\Gamma)N^{|\Gamma|} \left(\sum_{\Theta\ge \Pi\vee\Gamma}\mu(\Theta,\hat{1})\right) $$ $$ =\sum_{\Gamma\in{\rm Part}_n}\mu(\hat{0},\Gamma)N^{|\Gamma|}\mathbf{1}\{\Pi\vee\Gamma=\hat{1}\} $$ and the degree bound immediately follows from the Lemma.

As an aside, here are two more ways to write the polynomial $P_{\Pi}(N)$. $$ P_{\Pi}(N)=\sum_{\rho\in\mathfrak{S}_n}\mathbf{1}\{\langle\tau,\rho\rangle\ {\rm transitive}\} {\rm sgn}(\rho)N^{c(\rho)}\ . $$ Here $\tau$ is a fixed permutation whose cycle partition is $\Pi$. The sum is over permutations $\rho$ such that the subgroup of the symmetric group, generated by $\tau$ and $\rho$, acts transitively on $[n]$. $$ P_{\Pi}(N)=\sum_G \mathbf{1}\{G\ \Pi-{\rm connects}\ [n]\} (-1)^{|G|}N^{C(G)} $$ where the sum is over subgraphs $G$ of the complete graph $K_n$, seen as a set of edges, with the condition that $G$ together with a forest that has $\Pi$ as partition of connected components, connects the entire set $[n]$. Here $C(G)$ is the number of connected components of $G$. The last formula is related to the Whitney-Tutte-Fortuin-Kasteleyn representation of the chromatic polynomial (for the complete graph). See this article by Sokal, in particular for the relation to rigorous statistical mechanics.

First I will rephrase the question, and then I will solve the rephrased problem.

Let ${\rm Part}_n$ denote the set of set partitions of $[n]=\{1,2,\ldots,n\}$. For $\Theta,\Pi\in {\rm Part}_n$, we will say that $\Theta$ is finer than $\Pi$ and write $\Theta\le \Pi$, when $$ \forall A\in\Theta, \exists B\in\Pi, A\subset B\ . $$ The $\subset$ notation here allows equality. This defines the well-known partition lattice $({\rm Part}_n,\le)$. The smallest element denoted by $\hat{0}$ is the partition made of singletons. The largest element denoted by $\hat{1}$ is the single block partition. We will use $\vee$ to denote the join or supremum of two partitions in ${\rm Part}_n$.

The lattice has a Möbius function $\mu(\Theta,\Pi)$ given by the entries of the matrix $(\mu(\Theta,\Pi))_{\Theta,\Pi\in{\rm Part}_n}$ which by definition is the inverse of the matrix $(\mathbf{1}\{\Theta\le \Pi\})_{\Theta,\Pi\in{\rm Part}_n}$. We used the notation $\mathbf{1}\{\cdots\}$ for the indicator function equal to $1$ if the enclosed condition is true, and equal to $0$ if the condition is false. An explicit formula for the Möbius function is given by $$ \mu(\Theta,\Pi)=\prod_{A\in\Pi}\left[(-1)^{s(\Theta,A)-1}(s(\Theta,A)-1)!\right] $$ where $s(\Theta,A)$ is the number of blocks of $\Theta$ contained in $A$.

The following lemma reflects the graded/ranked property of the partition lattice.

Lemma: If $\Theta_1,\Theta_2\in{\rm Part}_n$, then $|\Theta_1\vee\Theta_2|\ge|\Theta_1|+|\Theta_2|-n$.

Proof: For $i=1,2$, pick $F_i$ a forest (subgraph of the complete graph with no circuit) whose partition of connected components is $\Theta_i$. We have $|\Theta_i|=n-|F_i|$. By eliminating redundant edges which create circuits instead of new connections, pick a forest $F_3\subset F_1\cup F_2$ such that the partition of connected components of $F_3$ is exactly $\Theta_1\vee\Theta_2$. Since $|F_3|\le |F_1|+|F_2|$, the wanted inequality follows.

The notation $(x)_k:=x(x-1)\cdots(x-k+1)$ is for the falling factorial. We now define $$ K_{\Pi}(N):=\sum_{\Theta\ge \Pi}(-1)^{|\Theta|}(|\Theta|-1)! \times\prod_{A\in\Theta}\left[\prod_{j=1}^{|A|-1}\left(1-\frac{j}{N}\right)\right] $$ $$ =\sum_{\Theta\ge \Pi}(-1)^{|\Theta|}(|\Theta|-1)! \times\prod_{A\in\Theta}\left(\frac{(N-1)_{|A|-1}}{N^{|A|-1}}\right) $$ $$ =\sum_{\Theta\ge \Pi}(-1)^{|\Theta|}(|\Theta|-1)! \times\prod_{A\in\Theta}\left(\frac{(N)_{|A|}}{N^{|A|}}\right) $$ $$ =-N^{-n}\ P_{\Pi}(N) $$ where we introduced the polynomial, in $N$, $$ P_{\Pi}(N):=\sum_{\Theta\ge \Pi}\mu(\Theta,\hat{1}) \prod_{A\in\Theta} (N)_{|A|}\ . $$ If I understood correctly, the question is to show the existence of a constant $C_n$, only depending on $n$, such that for all $N>0$ $$ |K_{\Pi}(N)|\le C_n N^{1-|\Pi|}\ , $$ i.e., $$ |P_{\Pi}(N)|\le C_n N^{n-|\Pi|+1}\ . $$ The means the degree of the polynomial $P_{\Pi}$ is at most $n-|\Pi|+1$.

Using Stirling numbers of the first kind, and their definition in terms of permutations in the symmetric group $\mathfrak{S}_k$, we have $$ (x)_k=\sum_{\rho\in\mathfrak{S}_k}{\rm sgn}(\rho) x^{c(\rho)} $$ where $c(\rho)$ is the number of cycles of the permutation $\rho$. Grouping permutations according to the set partition corresponding to their cycles we have $$ (x)_k=\sum_{\Theta\in{\rm Part}_k}(-1)^{k-|\Theta|}x^{|\Theta|} \prod_{A\in\Theta}(|A|-1)! $$ $$ =\sum_{\Theta\in{\rm Part}_k}\mu(\hat{0},\Theta)x^{|\Theta|} $$ where the Möbius function is that of ${\rm Part}_k$. By taking the product of the previous identity over the blocks of some partition $\Theta\in{\rm Part}_n$, and expanding, we have $$ \prod_{A\in\Theta} (N)_{|A|}=\sum_{\Gamma\le\Theta}\mu(\hat{0},\Gamma)N^{|\Gamma|} $$ where the Möbius function is that of ${\rm Part}_n$.

As a result, $$ P_{\Pi}(N)=\sum_{\Theta\ge\Pi}\mu(\Theta,\hat{1}) \left(\sum_{\Gamma\le \Theta}\mu(\hat{0},\Gamma)N^{|\Gamma|}\right) $$ $$ =\sum_{\Gamma\in{\rm Part}_n}\mu(\hat{0},\Gamma)N^{|\Gamma|} \left(\sum_{\Theta\ge \Pi\vee\Gamma}\mu(\Theta,\hat{1})\right) $$ $$ =\sum_{\Gamma\in{\rm Part}_n}\mu(\hat{0},\Gamma)N^{|\Gamma|}\mathbf{1}\{\Pi\vee\Gamma=\hat{1}\} $$ and the degree bound immediately follows from the Lemma.

As an aside, here are two more ways to write the polynomial $P_{\Pi}(N)$. $$ P_{\Pi}(N)=\sum_{\rho\in\mathfrak{S}_n}\mathbf{1}\{\langle\tau,\rho\rangle\ {\rm transitive}\} {\rm sgn}(\rho)N^{c(\rho)}\ . $$ Here $\tau$ is a fixed permutation whose cycle partition is $\Pi$. The sum is over permutations $\rho$ such that the subgroup of the symmetric group, generated by $\tau$ and $\rho$, acts transitively on $[n]$. $$ P_{\Pi}(N)=\sum_G \mathbf{1}\{G\ \Pi-{\rm connects}\ [n]\} (-1)^{|G|}N^{C(G)} $$ where the sum is over subgraphs $G$ of the complete graph $K_n$, seen as a set of edges, with the condition that $G$ together with a forest that has $\Pi$ as partition of connected components, connects the entire set $[n]$. Here $C(G)$ is the number of connected components of $G$. The last formula is related to the Whitney-Tutte-Fortuin-Kasteleyn representation of the chromatic polynomial (for the complete graph).

First I will rephrase the question, and then I will solve the rephrased problem.

Let ${\rm Part}_n$ denote the set of set partitions of $[n]=\{1,2,\ldots,n\}$. For $\Theta,\Pi\in {\rm Part}_n$, we will say that $\Theta$ is finer than $\Pi$ and write $\Theta\le \Pi$, when $$ \forall A\in\Theta, \exists B\in\Pi, A\subset B\ . $$ The $\subset$ notation here allows equality. This defines the well-known partition lattice $({\rm Part}_n,\le)$. The smallest element denoted by $\hat{0}$ is the partition made of singletons. The largest element denoted by $\hat{1}$ is the single block partition. We will use $\vee$ to denote the join or supremum of two partitions in ${\rm Part}_n$.

The lattice has a Möbius function $\mu(\Theta,\Pi)$ given by the entries of the matrix $(\mu(\Theta,\Pi))_{\Theta,\Pi\in{\rm Part}_n}$ which by definition is the inverse of the matrix $(\mathbf{1}\{\Theta\le \Pi\})_{\Theta,\Pi\in{\rm Part}_n}$. We used the notation $\mathbf{1}\{\cdots\}$ for the indicator function equal to $1$ if the enclosed condition is true, and equal to $0$ if the condition is false. An explicit formula for the Möbius function is given by $$ \mu(\Theta,\Pi)=\prod_{A\in\Pi}\left[(-1)^{s(\Theta,A)-1}(s(\Theta,A)-1)!\right] $$ where $s(\Theta,A)$ is the number of blocks of $\Theta$ contained in $A$.

The following lemma reflects the graded/ranked property of the partition lattice.

Lemma: If $\Theta_1,\Theta_2\in{\rm Part}_n$, then $|\Theta_1\vee\Theta_2|\ge|\Theta_1|+|\Theta_2|-n$.

Proof: For $i=1,2$, pick $F_i$ a forest (subgraph of the complete graph with no circuit) whose partition of connected components is $\Theta_i$. We have $|\Theta_i|=n-|F_i|$. By eliminating redundant edges which create circuits instead of new connections, pick a forest $F_3\subset F_1\cup F_2$ such that the partition of connected components of $F_3$ is exactly $\Theta_1\vee\Theta_2$. Since $|F_3|\le |F_1|+|F_2|$, the wanted inequality follows.

The notation $(x)_k:=x(x-1)\cdots(x-k+1)$ is for the falling factorial. We now define $$ K_{\Pi}(N):=\sum_{\Theta\ge \Pi}(-1)^{|\Theta|}(|\Theta|-1)! \times\prod_{A\in\Theta}\left[\prod_{j=1}^{|A|-1}\left(1-\frac{j}{N}\right)\right] $$ $$ =\sum_{\Theta\ge \Pi}(-1)^{|\Theta|}(|\Theta|-1)! \times\prod_{A\in\Theta}\left(\frac{(N-1)_{|A|-1}}{N^{|A|-1}}\right) $$ $$ =\sum_{\Theta\ge \Pi}(-1)^{|\Theta|}(|\Theta|-1)! \times\prod_{A\in\Theta}\left(\frac{(N)_{|A|}}{N^{|A|}}\right) $$ $$ =-N^{-n}\ P_{\Pi}(N) $$ where we introduced the polynomial, in $N$, $$ P_{\Pi}(N):=\sum_{\Theta\ge \Pi}\mu(\Theta,\hat{1}) \prod_{A\in\Theta} (N)_{|A|}\ . $$ If I understood correctly, the question is to show the existence of a constant $C_n$, only depending on $n$, such that for all $N>0$ $$ |K_{\Pi}(N)|\le C_n N^{1-|\Pi|}\ , $$ i.e., $$ |P_{\Pi}(N)|\le C_n N^{n-|\Pi|+1}\ . $$ The means the degree of the polynomial $P_{\Pi}$ is at most $n-|\Pi|+1$.

Using Stirling numbers of the first kind, and their definition in terms of permutations in the symmetric group $\mathfrak{S}_k$, we have $$ (x)_k=\sum_{\rho\in\mathfrak{S}_k}{\rm sgn}(\rho) x^{c(\rho)} $$ where $c(\rho)$ is the number of cycles of the permutation $\rho$. Grouping permutations according to the set partition corresponding to their cycles we have $$ (x)_k=\sum_{\Theta\in{\rm Part}_k}(-1)^{k-|\Theta|}x^{|\Theta|} \prod_{A\in\Theta}(|A|-1)! $$ $$ =\sum_{\Theta\in{\rm Part}_k}\mu(\hat{0},\Theta)x^{|\Theta|} $$ where the Möbius function is that of ${\rm Part}_k$. By taking the product of the previous identity over the blocks of some partition $\Theta\in{\rm Part}_n$, and expanding, we have $$ \prod_{A\in\Theta} (N)_{|A|}=\sum_{\Gamma\le\Theta}\mu(\hat{0},\Gamma)N^{|\Gamma|} $$ where the Möbius function is that of ${\rm Part}_n$.

As a result, $$ P_{\Pi}(N)=\sum_{\Theta\ge\Pi}\mu(\Theta,\hat{1}) \left(\sum_{\Gamma\le \Theta}\mu(\hat{0},\Gamma)N^{|\Gamma|}\right) $$ $$ =\sum_{\Gamma\in{\rm Part}_n}\mu(\hat{0},\Gamma)N^{|\Gamma|} \left(\sum_{\Theta\ge \Pi\vee\Gamma}\mu(\Theta,\hat{1})\right) $$ $$ =\sum_{\Gamma\in{\rm Part}_n}\mu(\hat{0},\Gamma)N^{|\Gamma|}\mathbf{1}\{\Pi\vee\Gamma=\hat{1}\} $$ and the degree bound immediately follows from the Lemma.

As an aside, here are two more ways to write the polynomial $P_{\Pi}(N)$. $$ P_{\Pi}(N)=\sum_{\rho\in\mathfrak{S}_n}\mathbf{1}\{\langle\tau,\rho\rangle\ {\rm transitive}\} {\rm sgn}(\rho)N^{c(\rho)}\ . $$ Here $\tau$ is a fixed permutation whose cycle partition is $\Pi$. The sum is over permutations $\rho$ such that the subgroup of the symmetric group, generated by $\tau$ and $\rho$, acts transitively on $[n]$. $$ P_{\Pi}(N)=\sum_G \mathbf{1}\{G\ \Pi-{\rm connects}\ [n]\} (-1)^{|G|}N^{C(G)} $$ where the sum is over subgraphs $G$ of the complete graph $K_n$, seen as a set of edges, with the condition that $G$ together with a forest that has $\Pi$ as partition of connected components, connects the entire set $[n]$. Here $C(G)$ is the number of connected components of $G$. The last formula is related to the Whitney-Tutte-Fortuin-Kasteleyn representation of the chromatic polynomial (for the complete graph). See this article by Sokal, in particular for the relation to rigorous statistical mechanics.

added 16 characters in body
Source Link
Loading
edited body
Source Link
Loading
edited body
Source Link
Loading
added 5 characters in body
Source Link
Loading
Source Link
Loading