Multiplicity for partially ordered sets
이 뉴스, 어떠셨어요?
한 번의 탭으로 반응을 남겨요 · 로그인 불필요
Abstract
Let $\mathcal Q=\{Q_a:a\geq1\}$ be a nested family of finite posets such that $Q_a\subseteq Q_{a+1}$ and $|Q_a|<|Q_{a+1}|$.
For a poset $Q$, let $\mathcal C_t(Q)$ denote the set of all strict $t$-chains in $Q$.
Given an $r$-coloring of $\mathcal C_t(Q_a)$ and posets $P_1,\ldots,P_r$, a weak copy of $P_i$ is called monochromatic of color $i$ if all $t$-chains in the copy have color $i$; the strong version is defined in the same way for induced copies.
The corresponding weak and strong multiplicity parameters are the minimum possible total number of such monochromatic copies in the host this http URL the Boolean lattice $B_n$, define $E_n={(S,T,U)\in B_n^3:S\subsetneq T\subsetneq U,\ |S|+|T|=|U|}.$ For a two-coloring $\chi:B_n\to{0,1}$, a triple $(S,T,U)\in E_n$ is monochromatic if $\chi(S)=\chi(T)=\chi(U)$.
Let $R^{\mathrm{arith}}_2$ be the least integer $n$ such that every two-coloring of $B_n$ contains a monochromatic triple in $E_n$, and let $M^{\mathrm{arith}}_2(B_n)$ be the minimum number of monochromatic triples in $E_n$ over all two-colorings of $B_n$.
We prove that $R^{\mathrm{arith}}_2=9.$ Moreover, $|E_n|=\binom{2n}{n}-[x^n](1+x+x^2)^n-2^n+1=\frac{4^n}{\sqrt{\pi n}}\bigl(1+o(1)\bigr),$ and $2^{\delta n+o(n)}\le M^{\mathrm{arith}}_2(B_n)\le 2^{\gamma n+o(n)}, $ where $\delta\approx 1.356779$ and $\gamma\approx 1.567837$ are explicit entropy constants.
For general nested host families, we prove a double-counting lower bound for strong poset multiplicity.
For an arbitrary finite host poset $R$, we also introduce a Fourier-Möbius method and give an exact Fourier expansion for strong multiplicity, a Parseval-type error bound, and a spectral lower bound.