Bounded spinal concentration for local invariants of the partition graph

The axial and spinal concentration conjectures fail for local cliques

Precise source. In Axial Morphology of the Partition Graph: Self-Conjugate Axis, Spine, and Concentration, Fedor B. Lyudogovskiy conjectures that, for each of the three invariants

$$I\in\{\deg,\omega_{\mathrm{loc}},\dim_{\mathrm{loc}}\},$$

the axial concentration radius is bounded independently of the partition size (Conjecture 5.4), and that the spinal concentration radius is likewise bounded (Conjecture 5.5). We disprove both conjectures for

$$I=\omega_{\mathrm{loc}} \qquad\text{and}\qquad I=\dim_{\mathrm{loc}}.$$

The separate claim for the degree invariant is not addressed.

We explicitly credit the star/top classification of partition-graph cliques to the author's earlier paper The homotopy type of the clique complex of the partition graph, Theorems 3.4 and 3.6. The sharp global triangular clique threshold is also already established in the separate MathDB problem #373810, associated with Simplex Stratification and Phase Boundaries in the Partition Graph. We repeat the short relevant bound only to certify that our explicit vertices are genuine global maximizers. The new result is that those maximizers have unbounded axial and spinal distance, which also answers negatively Problem 9.5 in the author's later paper Simplicial shells and thickness in the partition graph.

1. The source definitions

Let $G_n$ be the partition graph: its vertices are the Ferrers diagrams of partitions of $n$, and two vertices are adjacent precisely when one diagram is obtained from the other by moving a single box.

The self-conjugate axis is

$$\mathrm{Ax}_n = \{\alpha\vdash n:\alpha=\alpha'\}. \tag{1}$$

The source's thin spine satisfies

$$\mathrm{Ax}_n \subseteq \mathrm{Sp}_n \subseteq \{\gamma\vdash n:d_{G_n}(\gamma,\mathrm{Ax}_n)\leq1\}. \tag{2}$$

For a vertex $\gamma$, the local clique number and local dimension are

$$\begin{aligned} \omega_{\mathrm{loc}}(\gamma) &= \max\{|Q|:Q\text{ is a clique in }G_n,\ \gamma\in Q\}, \\ \dim_{\mathrm{loc}}(\gamma) &= \omega_{\mathrm{loc}}(\gamma)-1. \end{aligned} \tag{3}$$

The concentration radii measure the furthest, rather than the nearest, global maximizer:

$$\begin{aligned} \rho_I^{\mathrm{ax}}(n) &= \max_{\gamma\in\operatorname{Argmax}(I)} d_{G_n}(\gamma,\mathrm{Ax}_n), \\ \rho_I^{\mathrm{sp}}(n) &= \max_{\gamma\in\operatorname{Argmax}(I)} d_{G_n}(\gamma,\mathrm{Sp}_n). \end{aligned} \tag{4}$$

These formulas are equivalent to Definitions 2.15 and 2.16 of the source because the graph is finite.

2. A triangular upper bound for all cliques

Write

$$T_r=\binom{r+1}{2}=\frac{r(r+1)}2. \tag{5}$$

A partition with $d$ distinct positive part sizes has exactly $d$ removable corners and $d+1$ addable corners. Moreover, its size is at least

$$1+2+\cdots+d=T_d. \tag{6}$$

For completeness, the relevant consequence of the previously known star/top classification can also be seen directly. Regard Ferrers diagrams of size $n$ as sets of $n$ boxes. If distinct diagrams $A,B$ are adjacent, then

$$J=A\cap B, \qquad U=A\cup B, \qquad |J|=n-1, \qquad |U|=n+1. \tag{7}$$

Every diagram adjacent to both $A$ and $B$ either contains $J$ or is contained in $U$. A diagram of the first kind which is not contained in $U$ cannot be adjacent to a diagram of the second kind which does not contain $J$: the two diagrams then differ in at least two boxes on each side. Consequently every clique belongs entirely to one of the following types:

1. A star, whose diagrams all contain a common partition $\mu\vdash n-1$ and are obtained by adding distinct corners to $\mu$.
2. A top, whose diagrams are all contained in a common partition $\nu\vdash n+1$ and are obtained by removing distinct corners from $\nu$.

Hence, if a star has $s$ vertices, its base has at least $s-1$ distinct part sizes, and therefore

$$n-1\geq T_{s-1}. \tag{8}$$

If a top has $s$ vertices, its base has at least $s$ distinct part sizes, and therefore

$$n+1\geq T_s. \tag{9}$$

Now specialize to

$$n=T_r, \qquad r\geq2. \tag{10}$$

A star with at least $r+1$ vertices would violate (8), since

$$n-1=T_r-1<T_r. \tag{11}$$

A top with at least $r+1$ vertices would violate (9), since

$$n+1=T_r+1<T_{r+1} \qquad(r\geq2). \tag{12}$$

Thus every clique in $G_{T_r}$ has at most $r$ vertices.

3. An explicit maximum clique far from the axis

Consider the partitions

$$\begin{aligned} \mu_r &=(2r-2,r-2,r-3,\ldots,2,1), \\ \lambda_r &=(2r-1,r-2,r-3,\ldots,2,1). \end{aligned} \tag{13}$$

The trailing list is empty when $r=2$. Their sizes are

$$\begin{aligned} |\mu_r| &= 2r-2+\frac{(r-2)(r-1)}2 =T_r-1, \\ |\lambda_r| &= 2r-1+\frac{(r-2)(r-1)}2 =T_r. \end{aligned} \tag{14}$$

The partition $\mu_r$ has exactly $r-1$ distinct part sizes. It therefore has exactly $r$ addable corners. Adding one box at each of these corners produces $r$ different partitions of $T_r$, and any two differ by moving one box. Hence they form an $r$-vertex clique in $G_{T_r}$. One member of this clique is $\lambda_r$, obtained by adding a box to the first row.

Together with the upper bound in Section 2, this proves

$$\omega(G_{T_r}) = \omega_{\mathrm{loc}}(\lambda_r) =r. \tag{15}$$

Consequently,

$$\lambda_r \in \operatorname{Argmax}(\omega_{\mathrm{loc}}) = \operatorname{Argmax}(\dim_{\mathrm{loc}}). \tag{16}$$

The integer $T_r$ is axial: the staircase partition

$$\delta_r=(r,r-1,\ldots,2,1) \tag{17}$$

is self-conjugate and has size $T_r$.

4. Diverging distances and failure of both conjectures

For any nonempty partition $\gamma$, define its width-height imbalance by

$$b(\gamma)=\gamma_1-\ell(\gamma), \tag{18}$$

where $\ell(\gamma)$ is its number of nonzero parts. Every self-conjugate partition has equal width and height, and therefore

$$b(\alpha)=0 \qquad(\alpha\in\mathrm{Ax}_n). \tag{19}$$

Moving one Ferrers box changes the width by at most one and the height by at most one. Thus adjacent vertices $\gamma,\eta$ satisfy

$$|b(\gamma)-b(\eta)|\leq2. \tag{20}$$

For the maximizer in (13),

$$\lambda_{r,1}=2r-1, \qquad \ell(\lambda_r)=r-1, \qquad b(\lambda_r)=r. \tag{21}$$

Equations (19) and (20) give

$$d_{G_{T_r}}(\lambda_r,\mathrm{Ax}_{T_r}) \geq \left\lceil\frac r2\right\rceil. \tag{22}$$

Since every spinal vertex has distance at most one from the axis by (2), the triangle inequality also gives

$$d_{G_{T_r}}(\lambda_r,\mathrm{Sp}_{T_r}) \geq \left\lceil\frac r2\right\rceil-1. \tag{23}$$

Finally, $\lambda_r$ is a global maximizer of both local invariants by (16). Hence, for

$$I\in\{\omega_{\mathrm{loc}},\dim_{\mathrm{loc}}\},$$

the exact source-defined radii satisfy

$$\boxed{ \begin{aligned} \rho_I^{\mathrm{ax}}(T_r) &\geq \left\lceil\frac r2\right\rceil, \\ \rho_I^{\mathrm{sp}}(T_r) &\geq \left\lceil\frac r2\right\rceil-1. \end{aligned} } \tag{24}$$

Both lower bounds tend to infinity. Since

$$r=\frac{\sqrt{8T_r+1}-1}{2}, \tag{25}$$

the concentration radii grow at least on the order of $\sqrt n$ along the infinite axial subsequence $n=T_r$. Therefore the source's Conjectures 5.4 and 5.5 are both false for the local clique number and local simplex dimension. No conclusion is asserted for the degree invariant.