Finite-exception theorem for Horňák–Woźniak tripods

This research checkpoint precedes the full proof of both conjectures. Its finite-exception argument is retained for the separate conclusion about the growth of the middle arm.

In Conjecture 1 of On arbitrarily vertex decomposable trees, Horňák and Woźniak ask whether their five arithmetic admissibility conditions suffice for a tripod to admit every partition into connected pieces. Write A≤B≤CA\le B\le C for the numbers of vertices on the three arms excluding the centre, and put n=1+A+B+Cn=1+A+B+C. In the authors' convention the arm orders are (A+1,B+1,C+1)(A+1,B+1,C+1).

Theorem 19 of the preprint proves sufficiency when B≥(A−2)(A−1)B\ge(A-2)(A-1). The later construction of decomposable combs of arbitrarily long minimum arm settles the related existence question. The maximum-degree theorem of Barth and Fournier addresses a separate conjecture. Searches of the original statements, citing papers, algorithm papers and more recent work on arbitrarily partitionable trees found no resolution of the full five-condition conjecture.

All partitions with only consecutive sizes

Theorem 9 reduces the test for decomposability to partitions with sizes ii and i+1i+1, possibly with one extra size m<im\lt i in the indicated short-arm range. The following argument shows that conditions 1, 2 and 5 of Theorem 12 already handle the entire class with no extra size.

For a fixed ii put j=i+1j=i+1. Reserve one size-jj piece for the centre, which is permitted by Lemma 11. If there is an extra piece of size mm, choose an arm for it and subtract mm from that arm's capacity. All remaining pieces must fit into three bins of the resulting capacities x1,x2,x3x_1,x_2,x_3. Conversely, a feasible bin assignment gives a connected decomposition by placing each assigned piece on a consecutive segment outward from the centre, with all unused initial segments forming the central piece.

Let aa be the count of size-ii pieces, and let bb be the count of size-jj pieces other than the central one. Put ql=⌊xl/i⌋q_l=\lfloor x_l/i\rfloor, ul=xlmodiu_l=x_l\bmod i, and Hl=⌊xl/j⌋H_l=\lfloor x_l/j\rfloor. If blb_l of the bigger pieces are in arm ll, the capacity there for smaller pieces is

ql−bl−⌈bl−uli⌉.q_l-b_l-\left\lceil\frac{b_l-u_l}{i}\right\rceil.

The ceiling is nonnegative for bl≥0b_l\ge0, because 0≤ul≤i−10\le u_l\le i-1. Therefore feasibility is equivalent to being able to allocate the bb pieces to the arms with total ceiling cost at most K=∑lql−a−bK=\sum_l q_l-a-b, subject to bl≤Hlb_l\le H_l. For an integer K≥0K\ge0, the maximum possible bb, denoted M(K)M(K), is obtained by starting with ∑lmin(ul,Hl)\sum_l\min(u_l,H_l) and choosing up to KK of the largest increments. For each arm the increments are copies of ii followed by a possible smaller final increment, because allowing ceiling cost klk_l gives capacity min(Hl,ul+ikl)\min(H_l,u_l+i k_l). These increments can be taken in their within-arm order. Every b≤M(K)b\le M(K) is feasible at this cost by removing bigger pieces from an allocation. In particular

0≤M(K+1)−M(K)≤i.0\le M(K+1)-M(K)\le i.

As the partition varies with the capacities fixed, the allotted total ai+bjai+bj is constant. Increasing bb by ii increases KK by one. Therefore if the largest bb passes, all smaller choices with K≥0K\ge0 also pass.

When a partition in this class exists, the admissibility condition gives ∑lul=r(i)−1+γii\sum_l u_l=r(i)-1+\gamma_i i, where r(i)∈[1,i]r(i)\in[1,i] represents nn modulo ii and γi≤1\gamma_i\le1. The smallest possible bb is r(i)−1r(i)-1, so at this first value K=1−γi≥0K=1-\gamma_i\ge0. It suffices to consider the largest bb, for which a=j−r(j)≤ia=j-r(j)\le i. Write vl=xlmodjv_l=x_l\bmod j and Ql=⌊xl/j⌋Q_l=\lfloor x_l/j\rfloor. Putting ala_l smaller pieces in arm ll leaves capacity

Ql−al+⌊vl+alj⌋Q_l-a_l+\left\lfloor\frac{v_l+a_l}{j}\right\rfloor

for bigger pieces. The desired count is b=∑lQl−a+γjb=\sum_l Q_l-a+\gamma_j. When γj=0\gamma_j=0, any placement of all smaller pieces suffices, since the flooring terms are nonnegative. Such a placement exists because K≥0K\ge0. When γj=1\gamma_j=1, condition 5 gives an arm with vl≥r(j)v_l\ge r(j) and ⌊xl/i⌋+vl≥j\lfloor x_l/i\rfloor+v_l\ge j. Place j−vl≤aj-v_l\le a smaller pieces there to create one carry, and fit the other smaller pieces in the available capacity. This gives the desired number of bigger pieces. The case i=A+Bi=A+B also has γj≤1\gamma_j\le1, since the first two residues sum to j−1j-1 at j=A+B+1j=A+B+1.

For a fixed extra size mm, subtracting it changes the minimum KK for any chosen arm by at most one. Thus it is enough to check the first and last counts of the size-jj pieces for each allowed pair (i,m)(i,m). If the last passes in some arm, the same arm works down to the second count, where K≥0K\ge0 even if its first value is −1-1. The general proof that the extra-size checks follow from admissibility remains open.

A finite-exception theorem

Theorem. For all sufficiently large AA, every admissible tripod with shortest arm size AA is arbitrarily vertex decomposable. In fact, for every fixed D>0D\gt0, admissibility forces B>ADB\gt A^D once AA is sufficiently large in terms of DD.

What the residue tests imply about the arm lengths

The first two tests of Theorem 12 are equivalent to requiring that the sum of the two smallest of Amodi,Bmodi,CmodiA\bmod i,B\bmod i,C\bmod i is less than ii, for every 1≤i≤A+B1\le i\le A+B. If the three residues have sum s≥is\ge i, condition 2 is that their maximum is at least s−i+1s-i+1, which is exactly the asserted pair condition. That condition also rules out s≥2is\ge2i, and if s<is\lt i both original tests hold.

For A≥2A\ge2, admissibility also implies the arm-length bound used in Theorem 8. Indeed, no expression of nn as a sum of parts in [B+1,A+B][B+1,A+B] is possible. Any such expression can be balanced to use either a single size ii or consecutive sizes i,i+1i,i+1 in the same interval. In the single-size case r(i)=ir(i)=i, while AA and BB are unchanged residues with sum at least ii. Condition 2 then fails. In the consecutive-size case the positive count of size-i+1i+1 parts can be reduced by ii at a time, replacing them by i+1i+1 size-ii parts, to reach a count in [1,i][1,i]. Here A+B≥i+1A+B\ge i+1, both shorter arms have quotient zero at i+1i+1, and only the longest arm can contribute to the left side of condition 4. Its contribution is at most CmodiC\bmod i, whereas condition 4 requires at least A+B+(Cmodi)−i>CmodiA+B+(C\bmod i)-i\gt C\bmod i. A carry of two would already violate condition 1.

The forbidden intervals for nn are consequently [k(B+1),k(A+B)][k(B+1),k(A+B)] for all positive kk. As n>2(B+1)n\gt2(B+1), any remaining nn belongs to a gap

[k(A+B)+1,(k+1)(B+1)−1],2≤k≤⌊B−1A−1⌋.[k(A+B)+1,(k+1)(B+1)-1],\qquad 2\le k\le\left\lfloor\frac{B-1}{A-1}\right\rfloor.

The bound on kk is necessary for the gap to be nonempty. In particular B≥2A−1B\ge2A-1 and C=O(B2/A)C=O(B^2/A).

The reciprocal residues cannot avoid an open box at polynomial scales

Suppose there is a sequence of admissible triples with A→∞A\to\infty and B≤ADB\le A^D. Then CC is bounded by a fixed power of AA by the preceding argument. Pass to a subsequence on which every frequency (h,k)∈ℤ2(h,k)\in\mathbb Z^2 has either a finite limit Lh,kL_{h,k} for (hB+kC)/A(hB+kC)/A, or tends to infinity in absolute value. This is possible by a diagonal selection using the compact extended real line. The frequencies with finite limit form a subgroup RR of ℤ2\mathbb Z^2, and RR is saturated, meaning that a nonzero integer multiple in RR implies that the frequency itself is in RR.

For any fixed compact interval of t=A/it=A/i inside (1,∞)(1,\infty), the points ({B/i},{C/i})(\{B/i\},\{C/i\}) converge jointly with tt to Haar measure on the coset

{(x,y)∈(ℝ/ℤ)2:hx+ky=Lh,kt(mod1) for every (h,k)∈R}.\{(x,y)\in(\mathbb R/\mathbb Z)^2:h x+k y=L_{h,k}t\pmod1 \text{ for every }(h,k)\in R\}.

More precisely, the first coordinate tt has measure dt/t2dt/t^2 in the limit when the count over ii is divided by AA. For (h,k)∈R(h,k)\in R, the Fourier coefficient in the other two coordinates follows directly by Riemann sums. For (h,k)∉R(h,k)\notin R, let H=hB+kCH=hB+kC. On the given interval of i≍Ai\asymp A, the rr-th derivative of H/iH/i has size comparable to |H|/Ar+1|H|/A^{r+1}. Take a fixed derivative order rr larger than the power bounding |H||H|. Then |H|/Ar+1→0|H|/A^{r+1}\to0 and Ar|H|/Ar+1=|H|/A→∞A^r|H|/A^{r+1}=|H|/A\to\infty. The van der Corput derivative test gives a sum o(A)o(A) on every fixed subinterval in tt. Fourier approximation and approximation by step functions in tt give the claimed joint convergence.

It remains to see that this limiting measure gives positive mass to {t},x,y∈(1/2,1)\{t\},x,y\in(1/2,1). When RR has rank zero, both xx and yy are uniform. When it has rank two, B/AB/A and C/AC/A have finite limits b0,c0≥1b_0,c_0\ge1 and the coset is the point ({b0t},{c0t})(\{b_0t\},\{c_0t\}). Simultaneous Dirichlet approximation gives an integer T>2T\gt2 with b0T,c0Tb_0T,c_0T arbitrarily close to integers. A sufficiently small decrement of TT puts all three fractional parts strictly in (1/2,1)(1/2,1) on an open interval. The same argument works if one limit is finite and the other coordinate is free.

The remaining case has rank one and both ratios unbounded. A primitive generator (h,k)(h,k) of RR must have nonzero coefficients of opposite signs. On x,y∈(1/2,1)x,y\in(1/2,1) the values of hx+kyhx+ky form an open interval of length (|h|+|k|)/2≥1(|h|+|k|)/2\ge1. Thus their residues cover the circle apart from at most one point. If the length is exactly one, then h=−k=±1h=-k=\pm1, and the sole excluded residue is 1/21/2. The affine phase Lh,ktL_{h,k}t can avoid that residue on an open interval of tt with {t}∈(1/2,1)\{t\}\in(1/2,1), also when Lh,k=0L_{h,k}=0. The corresponding lines cross the open square and have positive Haar measure there. In all cases the limiting measure is positive on the desired open set. Thus there must be a modulus ii with i≤Ai\le A at which all three residues exceed i/2i/2. This contradicts the first two admissibility tests.

The van der Corput bound applies with derivative lower and upper bounds of the same order, so its normalized terms tend to zero uniformly for each fixed subinterval of positive length.

The resulting superpolynomial separation of the first two arms implies the hypothesis of Theorem 19 for all large AA. For each remaining AA, only finitely many choices of BB fall outside Theorem 19, and the bound on CC gives finitely many triples there as well. This argument does not provide a numerical cutoff for the exceptional set. It proves the finite-exception theorem and leaves the all-tripod statement open.

Exact cross-check

To screen a bounded range, enumerate the integer gaps above with 2≤A≤562\le A\le56 and B<(A−2)(A−1)B\lt(A-2)(A-1), then apply Theorem 12 at every modulus 1≤i≤A+B1\le i\le A+B. In tests 3 and 4, a partition with at most ii bigger parts exists exactly when n≥r(i)(i+1)n\ge r(i)(i+1). In test 5, a partition with at most ii smaller parts exists exactly when n≥(i+1)2−ir(i+1)n\ge (i+1)^2-i r(i+1). The statement of Proposition 20.1 omits the factor ii on r(i+1)r(i+1); the proof gives the latter formula.

The range contains 686,518,911 candidate triples before the arithmetic tests. The only admissible triple is (5,9,14)(5,9,14), whose decomposition is given by the authors in §4. Independent direct enumeration of the two tests' triggering partitions agreed with the threshold implementation for 3,374 small tripods. Direct allocation of bigger pieces to the three arms agreed with the capacity formula for 276,832 small partitions with and without the extra piece. This cross-check covers the indicated range and the proof leaves the rest of the exceptional set undetermined.