The Width of Hamming Balls
Kada Kálmán Williams · 2024
Read The Width of Hamming Balls by Kada Kálmán Williams (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2411-01496.txt.
Description
Abstract The width of a poset is the size of its largest antichain. Sperner’s theorem states that ( 2 [ n ] , ⊂ ) (2^{[n]},\subset) is a poset whose width equals the size of its largest layer. We show that Hamming ball posets also have this property.
Catalog record
| CREATOR | Kada Kálmán Williams |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 12 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2411-01496
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The Width of Hamming Balls Kada Kálmán Williams Abstract The width of a poset is the size of its largest antichain. Sperner’s theorem states that ( 2 [ n ] , ⊂ ) (2^{[n]},\subset) is a poset whose width equals the size of its largest layer. We show that Hamming ball posets also have this property. This extends earlier work that proves this in the case of small radii. Our proof is inspired by (and corrects) a result of Harper. 1 Introduction Let P be an arbitrary set and < be an irreflexive, transitive relation on pairs of its elements. Then we say that (P,<) is a partially ordered set, or to contract, a poset . In a poset P , with relation < , an element x is covered by y if x<y without any intermediate z\in P , such that x<z and z<y . For example, in the poset of rational numbers, 0 is not covered by any element, by the Archimedean axiom. However, in a finite poset, an intermediate element can only be found finitely many times, and so every relation x<y can be deduced from a chain of covers x<z_{1} , z_{1}<z_{2} , \dots , z_{k-1}<z_{k} , z_{k}<y . Let (P,<) be a finite poset. Consider the function r:P\to\{0,1,\dots\} given by r(x^{\prime})=\begin{cases}0\quad\text{if }\{x\in P:x<x^{\prime}\}=\emptyset,\\ \max\{r(x):x<x^{\prime}\}+1\quad\text{otherwise}.\end{cases} The value r(x)=k is the rank of x . The set of x\in P whose rank is k is layer P_{k} . Clearly, if r(y)=k and x<y , then r(x)<r(y) . Let (P,<) be a poset with C\subseteq P and A\subseteq P . If any two elements x\neq y in C are comparable, we say that C is a chain. If any two elements x\neq y in A are incomparable, we say that A is an antichain. Observe that in this case, |A\cap C|\leq 1 . Definition 1 . Let (P,<) be a finite poset. The size of the largest antichain of P is the width of P , denoted w(P) . The size of the largest layer of P is denoted \ell(P) . Since a layer of a finite poset P is an antichain, w(P)\geq\ell(P) . Theorem 2 (Sperner, 1928) . In the poset P=(2^{[n]},\subset) , w(P)=\ell(P) . Sperner’s proof [ 1 ] observes that if P is the union of c chains, then w(P)\leq c – a simpler proof of this is given by Greene and Kleitman [ 3 ] . However, a more general approach to poset width calculation considers a collection of chains that covers x\in P with a certain multiplicity. [ 2 ] Definition 3 . Let \mathcal{C} be a collection of chains in a finite poset P . Suppose that if we sample C\in\mathcal{C} uniformly at random, then for all x\in P , the chance that x\in C is \frac{1}{|P_{r(x)}|} . Then we say that \mathcal{C} is a unit flow. Applying our observation that an antichain A intersects a chain C in at most a singleton to a unit flow C , by linearity of expectation, we have the following property. Definition 4 . Let P be a finite poset. If every antichain A\subset P satisfies \sum_{x\in A}\frac{1}{|P_{r(x)}|}\leq 1, then we say that P is a LYM poset [ 4 ] or that P is a strong Sperner poset [ 8 ] . If P_{k} is the largest layer of P , then for all x\in P , |P_{r(x)}|\leq|P_{k}| . We deduce that if P is a LYM poset, then P is a Sperner poset. Theorem 5 (Yamamoto-Meshalkin-Bollobás-Lubell) . (2^{[n]},\subset) is a LYM poset. Proof. It suffices to find a unit flow, letting the symmetries of [n] act on the chain \emptyset\subset[1]\subset[2]\subset\dots\subset[n] . ∎ Finding a unit flow, in general, is difficult. Hence, it is of benefit for us to know a sufficient condition – a consequence of the Max Flow Min Cut theorem. [ 5 ] Proposition 6 (Kleitman, 1974) . Let (P,<) be a finite poset, where the LYM inequality \sum_{x\in A}\frac{1}{|P_{r(x)}|}\leq 1 holds for all antichains A contained within two consecutive layers. For such a poset P , there is a unit flow. We shall use this condition to prove that product posets and Hamming balls have the LYM property. 2 Harper’s theorem on product posets Definition 7 . Let (P,<) be a finite poset, and let P_{k} have size p_{k} . If the fractions \frac{p_{k+1}}{p_{k}} , when defined, are decreasing in k , we say that P is log-concave. For instance, if P is log-concave, then the subset of P given by layers indexed by an arithmetic progression is also log-concave. [ 7 ] Definition 8 . Let P and Q be posets. Then the set P\times Q with partial order (x_{P},x_{Q})\leq(y_{P},y_{Q}) if x_{P}\leq y_{P} and x_{Q}\leq y_{Q} is called the product poset P\times Q . For example, (2^{[n]},\subseteq) can be recognized as the n -fold product of (\{\emptyset,\{\emptyset\}\},\subseteq) . Theorem 9 (Harper, 1974) . Let P and Q be finite posets. If both P and Q are log-concave LYM posets, then their product poset P\times Q is LYM and log-concave. Proof. For completeness, we give a proof, while correcting an error made in [ 6 ] . Let P and Q consist of layers P_{0},\dots,P_{h} and Q_{0},\dots,Q_{\mu} , respectively. By Proposition 6 , there is a unit flow on P and on Q , and particularly from P_{k} to P_{k+1} and from Q_{l} to Q_{l+1} ( 0\leq k<h , 0\leq l<\mu ). Every element of P_{k}\times Q_{l}\subseteq P\times Q has rank k+l , and so (P\times Q)_{m}=\bigcup_{k+l=m}P_{k}\times Q_{l}. Consider a "block poset", whose elements are the "blocks" P_{k}\times Q_{l} ( 0\leq k\leq h , 0\leq l\leq\mu ) and relations are P_{k}\times Q_{l}\leq P_{k^{\prime}}\times Q_{l^{\prime}} for k\leq k^{\prime} and l\leq l^{\prime} . Each block P_{k}\times Q_{l} occurs with multiplicity given by its numbers of elements. In this block poset, by Proposition 6 , a unit flow can be found if the LYM inequality holds within consecutive layers. This would follow from the inequality 1 1 1 It is this inequality, for a unit flow in the block poset, which [ 6 ] proves incorrectly. Estimating p_{k-i}p_{k+1-j}q_{l+i}q_{l+j}\leq\begin{cases}p_{k+1-i}p_{k-j}q_{l+i}q_{l+j}\text{ if }j\leq i,\\ p_{k+1-(i+1)}p_{k-(j-1)}q_{l+(i+1)}q_{l+(j-1)}\text{ if }j>i.\end{cases} and summing, [ 6 ] notes that ”every term of the previous sum gives a unique term of this one”, falsely, because the contributions of upper bounds for j=i-1 and for i=j-1 involve t-1 duplicates. \frac{\sum_{i=0}^{t-1}|P_{k-i}\times Q_{l+i}|}{|(P\times Q)_{k+l}|}\leq\frac{\sum_{i=0}^{t}|P_{k+1-i}\times Q_{l+i}|}{|(P\times Q)_{k+l+1}|}, where t is a positive integer, 0\leq k+l<h+\mu , and undefined P_{k} or Q_{l} are empty. Given a unit flow on the block poset, a unit flow on P\times Q emerges by replacing P_{k}\times Q_{l}<P_{k+1}\times Q_{l} in the random chain with elements of the respective blocks in proportion to the unit flow from P_{k} to P_{k+1} , and similarly for P_{k}\times Q_{l}<P_{k}\times Q_{l+1} . To establish the requisite bounds, denote |P_{k}|=p_{k} and |Q_{l}|=q_{l} . We require \left(\sum_{i=0}^{t-1}p_{k-i}q_{l+i}\right)\left(\sum_{j}p_{k+1-j}q_{l+j}\right)\leq\left(\sum_{i=0}^{t}p_{k+1-i}q_{l+i}\right)\left(\sum_{j}p_{k-j}q_{l+j}\right), \sum_{i=0}^{t-1}\sum_{j}p_{k-i}p_{k+1-j}q_{l+i}q_{l+j}\leq\sum_{i=0}^{t}\sum_{j}p_{k+1-i}p_{k-j}q_{l+i}q_{l+j}. Observe the dependence on q_{l+j} ( j<0 ). Its coefficients on either side are \sum_{i=0}^{t-1}p_{k-i}p_{k+1-j}q_{l+i}\quad\text{and}\quad\sum_{i=0}^{t}p_{k+1-i}p_{k-j}q_{l+i}. By log-concavity of P , p_{k-i}p_{k+1-j}\leq p_{k+1-i}p_{k-j} holds if i\geq 0\geq j . Hence, if only for the terms involving q_{l+j} ( j<0 ), our inequality holds. The same is true for the terms involving p_{k-j} ( j\geq t ). Its coefficients, via summand (j+1) ,