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 for the numbers of vertices on the three arms excluding the centre, and put . In the authors' convention the arm orders are .
Theorem 19 of the preprint proves sufficiency when . 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.
- Horňák and Woźniak, preprint, Theorems 9, 12 and 19 and §4
- Published article
- Barth, Baudon and Puech, Decomposable trees: a polynomial algorithm for tripodes
- Barth, Fournier and Ravaux, On the shape of decomposable trees, Theorem 7
- Research issue
All partitions with only consecutive sizes
Theorem 9 reduces the test for decomposability to partitions with sizes and , possibly with one extra size 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 put . Reserve one size- piece for the centre, which is permitted by Lemma 11. If there is an extra piece of size , choose an arm for it and subtract from that arm's capacity. All remaining pieces must fit into three bins of the resulting capacities . 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 be the count of size- pieces, and let be the count of size- pieces other than the central one. Put , , and . If of the bigger pieces are in arm , the capacity there for smaller pieces is
The ceiling is nonnegative for , because . Therefore feasibility is equivalent to being able to allocate the pieces to the arms with total ceiling cost at most , subject to . For an integer , the maximum possible , denoted , is obtained by starting with and choosing up to of the largest increments. For each arm the increments are copies of followed by a possible smaller final increment, because allowing ceiling cost gives capacity . These increments can be taken in their within-arm order. Every is feasible at this cost by removing bigger pieces from an allocation. In particular
As the partition varies with the capacities fixed, the allotted total is constant. Increasing by increases by one. Therefore if the largest passes, all smaller choices with also pass.
When a partition in this class exists, the admissibility condition gives , where represents modulo and . The smallest possible is , so at this first value . It suffices to consider the largest , for which . Write and . Putting smaller pieces in arm leaves capacity
for bigger pieces. The desired count is . When , any placement of all smaller pieces suffices, since the flooring terms are nonnegative. Such a placement exists because . When , condition 5 gives an arm with and . Place 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 also has , since the first two residues sum to at .
For a fixed extra size , subtracting it changes the minimum for any chosen arm by at most one. Thus it is enough to check the first and last counts of the size- pieces for each allowed pair . If the last passes in some arm, the same arm works down to the second count, where even if its first value is . The general proof that the extra-size checks follow from admissibility remains open.
A finite-exception theorem
Theorem. For all sufficiently large , every admissible tripod with shortest arm size is arbitrarily vertex decomposable. In fact, for every fixed , admissibility forces once is sufficiently large in terms of .
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 is less than , for every . If the three residues have sum , condition 2 is that their maximum is at least , which is exactly the asserted pair condition. That condition also rules out , and if both original tests hold.
For , admissibility also implies the arm-length bound used in Theorem 8. Indeed, no expression of as a sum of parts in is possible. Any such expression can be balanced to use either a single size or consecutive sizes in the same interval. In the single-size case , while and are unchanged residues with sum at least . Condition 2 then fails. In the consecutive-size case the positive count of size- parts can be reduced by at a time, replacing them by size- parts, to reach a count in . Here , both shorter arms have quotient zero at , and only the longest arm can contribute to the left side of condition 4. Its contribution is at most , whereas condition 4 requires at least . A carry of two would already violate condition 1.
The forbidden intervals for are consequently for all positive . As , any remaining belongs to a gap
The bound on is necessary for the gap to be nonempty. In particular and .
The reciprocal residues cannot avoid an open box at polynomial scales
Suppose there is a sequence of admissible triples with and . Then is bounded by a fixed power of by the preceding argument. Pass to a subsequence on which every frequency has either a finite limit for , 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 of , and is saturated, meaning that a nonzero integer multiple in implies that the frequency itself is in .
For any fixed compact interval of inside , the points converge jointly with to Haar measure on the coset
More precisely, the first coordinate has measure in the limit when the count over is divided by . For , the Fourier coefficient in the other two coordinates follows directly by Riemann sums. For , let . On the given interval of , the -th derivative of has size comparable to . Take a fixed derivative order larger than the power bounding . Then and . The van der Corput derivative test gives a sum on every fixed subinterval in . Fourier approximation and approximation by step functions in give the claimed joint convergence.
It remains to see that this limiting measure gives positive mass to . When has rank zero, both and are uniform. When it has rank two, and have finite limits and the coset is the point . Simultaneous Dirichlet approximation gives an integer with arbitrarily close to integers. A sufficiently small decrement of puts all three fractional parts strictly in 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 of must have nonzero coefficients of opposite signs. On the values of form an open interval of length . Thus their residues cover the circle apart from at most one point. If the length is exactly one, then , and the sole excluded residue is . The affine phase can avoid that residue on an open interval of with , also when . 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 with at which all three residues exceed . 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 . For each remaining , only finitely many choices of fall outside Theorem 19, and the bound on 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 and , then apply Theorem 12 at every modulus . In tests 3 and 4, a partition with at most bigger parts exists exactly when . In test 5, a partition with at most smaller parts exists exactly when . The statement of Proposition 20.1 omits the factor on ; the proof gives the latter formula.
The range contains 686,518,911 candidate triples before the arithmetic tests. The only admissible triple is , 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.