Decomposable trees with prescribed arm orders

What Lean checks

Lean proves arbitrary vertex decomposability for tripods with a positive short arm of length at most two, conditional on source tests 1 and 5. For all positive short-arm lengths it proves partitions containing a larger part under those tests, realizes partitions with a sublist summing to the short arm unconditionally, and reduces the remainder to partitions with no mergeable noncentral pair. The general all-small case, four-arm reduction, existence constructions and combined gate remain. Strict compilation, a 958-theorem full-chain axiom audit and isolated kernel replay passed.

Theorem. Fix any integer A≥1A\ge1. Let BB be a positive multiple of lcm(1,…,2A+1)\operatorname{lcm}(1,\ldots,2A+1) and set C=A+B+1C=A+B+1. The trees with arm lengths (A,B,C)(A,B,C) and (1,A,B,C)(1,A,B,C), measured in edges, are both arbitrarily vertex decomposable.

This gives every prescribed shortest arm order A+1A+1 for the tripod and every prescribed second-smallest arm order A+1A+1 for the four-arm tree. These are Questions 22.1 and 22.2 in the 2010 problem collection of Horňák, Marczyk and Woźniak, and they imply affirmative answers to Problems 1 and 2 in §4 of the original Horňák–Woźniak paper. The 2010 collection records existence for infinitely many tripod arm orders from the earlier comb construction, along with the original finite tables. Choosing the least possible BB above gives both trees order exp(2A+o(A))\exp(2A+o(A)) by the prime number theorem, since loglcm(1,…,m)=∑pk≤mlogp∼m\log\operatorname{lcm}(1,\ldots,m)=\sum_{p^k\le m}\log p\sim m. 2010 problems, pp. 26–27 · Original paper, §4 · Comb construction

Proof

By the admissibility theorem, it suffices to check tests 1, 2 and 5 for both trees. For any modulus k≥2k\ge2, let λ\lambda be 0 or 1 according as the optional one-edge arm is absent or present. Let VV be the sum of the three regular-arm residues modulo kk plus λ\lambda, and let HH be the sum of their quotients. Thus the order of the tree is 1+Hk+V1+Hk+V.

Tests 1 and 2 say that the sum of the two smallest regular-arm residues plus λ\lambda is less than kk. The case when all regular-arm residues vanish satisfies both tests directly. At k=1k=1 both tests are automatic.

Test 5 at index k−1k-1 only applies if k≤V<2kk\le V\lt2k and the two-size partition that uses at most k−1k-1 parts of size k−1k-1 exists. Its count of the smaller parts is 2k−1−V2k-1-V, and its count of the larger parts is H+2−(2k−1−V)H+2-(2k-1-V). Thus the partition exists exactly when H+V≥2k−2H+V\ge2k-2. In this case the test requires an arm with residue vv and quotient hh modulo kk satisfying

v≥V+1−k,qquadh+v≥k−1.v\ge V+1-k,qquad h+v\ge k-1.

The second inequality is equivalent to ⌊x/(k−1)⌋+v≥k\lfloor x/(k-1)\rfloor+v\ge k for that arm's length x=hk+vx=hk+v.

Moduli at most 2A+12A+1

Here BB has residue zero. Write u=Amodku=A\bmod k. If u=k−1u=k-1, the residue of CC is zero, so tests 1 and 2 hold. When λ=1\lambda=1, the sum VV is kk, and the arm of length AA has residue k−1k-1 and passes the test 5 inequalities. For λ=0\lambda=0 the test has no trigger.

If u≤k−2u\le k-2, the residue of CC is u+1u+1. The two smaller residues sum to uu, so tests 1 and 2 hold. For test 5, the arm of length CC has residue u+1≥2u+2+λ−k=V+1−ku+1\ge 2u+2+\lambda-k=V+1-k. Its quotient is at least k−1k-1, since BB is a common multiple of the consecutive integers 2A,2A+12A,2A+1 and hence C≥k(k−1)C\ge k(k-1).

Moduli above 2A+12A+1

Write B=hk+bB=hk+b with 0≤b<k0\le b\lt k. The residue of AA is AA.

If b+A+1<kb+A+1\lt k, let c=b+A+1c=b+A+1 be the residue of CC. The sum A+b+λ≤c<kA+b+\lambda\le c\lt k gives tests 1 and 2. Here H=2hH=2h and V=2c−1+λV=2c-1+\lambda. If test 5 applies, H+V≥2k−2H+V\ge2k-2 implies h+c≥k−1h+c\ge k-1, and c≥2c+λ−k=V+1−kc\ge2c+\lambda-k=V+1-k. Thus the arm of length CC gives the test 5 inequalities.

Otherwise let c=b+A+1−kc=b+A+1-k be the residue of CC, which lies in [0,A][0,A]. Now A+c+λ≤2A+1<kA+c+\lambda\le2A+1\lt k, giving tests 1 and 2. The quotients of B,CB,C are h,h+1h,h+1, respectively, and V=k−1+2c+λV=k-1+2c+\lambda. If test 5 applies, then

h+c≥(k−2−λ)/2≥A−1/2,h+c\ge(k-2-\lambda)/2\ge A-1/2,

so h+c≥Ah+c\ge A by integrality. For the arm of length BB, its residue b=k−A−1+cb=k-A-1+c gives h+b≥k−1h+b\ge k-1 and b≥2c+λ=V+1−kb\ge2c+\lambda=V+1-k. All required tests hold, and so both trees are AVD.