Horňák–Woźniak conjecture

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.

A tree is arbitrarily vertex decomposable (AVD) if, for every list of positive integers summing to its order, its vertices can be partitioned into connected sets of those sizes. Write S(a1,…,aq)S(a_1,\ldots,a_q) for the star-like tree whose arms have those orders, each counting the common central vertex. We prove both conjectures in §4 of Horňák and Woźniak's paper.

  1. Every admissible sequence (a1,a2,a3)(a_1,a_2,a_3) gives an AVD tree S(a1,a2,a3)S(a_1,a_2,a_3).
  2. If both (2,a2,a3,a4)(2,a_2,a_3,a_4) and (a2,a3,a4)(a_2,a_3,a_4) are admissible, then S(2,a2,a3,a4)S(2,a_2,a_3,a_4) is AVD.

Admissibility is the conjunction of the five tests of Theorem 12 for every indicated modulus. The proof below uses only tests 1, 2 and 5. We use Theorems 9 and 10, which quote the reductions of Barth and coauthors, and use the numbering of the publicly available preprint throughout. Original preprint · Published paper

1. Packing pieces of two consecutive sizes

Fix positive integers ii and j=i+1j=i+1. When one part of size jj contains the central vertex, every other part fits in a single arm. Conversely, if all the other parts can be assigned to the arms without exceeding their capacities, place them on consecutive segments starting at the leaves. The unused initial segments, together with the centre, form the central part.

Let xlx_l denote the available capacity of arm ll. Write

ql=⌊xl/i⌋,ul=xlmodi,hl=⌊xl/j⌋,vl=xlmodj.q_l=\left\lfloor x_l/i\right\rfloor,\quad u_l=x_l\bmod i, \qquad h_l=\left\lfloor x_l/j\right\rfloor,\quad v_l=x_l\bmod j.

If blb_l pieces of size jj go in arm ll, the number of size-ii pieces it can still accommodate is

ql−bl−⌈(bl−ul)/i⌉.q_l-b_l-\left\lceil (b_l-u_l)/i\right\rceil .

The ceiling is nonnegative. To place aa pieces of size ii and bb pieces of size jj outside the centre, we need 0≤bl≤hl0\le b_l\le h_l, ∑lbl=b\sum_l b_l=b, and total ceiling cost at most K=∑lql−a−bK=\sum_lq_l-a-b. For K≥0K\ge0 let M(K)M(K) be the largest bb obtainable with that cost budget. At cost zero each arm contributes min(hl,ul)\min(h_l,u_l) possible pieces. Each unit of additional cost in that arm increases this allowance by ii until it reaches hlh_l, with a possibly smaller final increment. Thus M(K)M(K) is obtained by taking the KK largest available increments, including zero increments as needed. Ties can be ordered by taking earlier increments of an arm first. Removing pieces preserves the cost bound. Consequently the assignment exists exactly when K≥0K\ge0 and b≤M(K)b\le M(K), and

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

For a fixed total size of the pieces outside the centre, increasing bb by ii decreases aa by jj and increases KK by one. By (1), if the largest possible bb is feasible in the given capacities, so is every smaller bb for which K≥0K\ge0.

We will also use the complementary count. If ala_l pieces of size ii go in arm ll, its remaining capacity for pieces of size jj is

hl−al+⌊(vl+al)/j⌋.h_l-a_l+\left\lfloor (v_l+a_l)/j\right\rfloor . \tag{2}

For a partition with a≤ia\le i, each flooring term is either zero or one. Producing a carry of one in arm ll requires exactly j−vlj-v_l of the smaller pieces as a minimum, and is possible if ql≥j−vlq_l\ge j-v_l. If these minima for the required carries fit within aa and ∑lql≥a\sum_l q_l\ge a, the rest of the smaller pieces can be distributed within the remaining space for size ii. This can only increase the sum of the flooring terms in (2).

2. Partitions without a smaller extra part

Let the arm capacities be their full orders minus one, and let n=1+∑lxln=1+\sum_l x_l. Let r(k)∈[1,k]r(k)\in[1,k] represent nn modulo kk. For a modulus kk let γk\gamma_k be the quotient on dividing the sum of the arm residues modulo kk by kk, so this sum equals r(k)−1+γkkr(k)-1+\gamma_k k. The first admissibility test gives γi≤1\gamma_i\le1 for every index ii needed in Theorems 9 and 10. We also have γj≤1\gamma_j\le1 in the same range. At the upper endpoint j=aq−2+aq−1−1j=a_{q-2}+a_{q-1}-1, the two shorter regular arms contribute j−1j-1, the possible one-edge arm contributes one, and the longest arm contributes at most j−1j-1.

Suppose a partition into sizes i,ji,j with at least one size-jj part exists. Reserve one of the latter for the centre. Among these partitions the smallest possible bb is r(i)−1r(i)-1 and the corresponding budget is K=1−γi≥0K=1-\gamma_i\ge0. All budgets are therefore nonnegative, so (1) reduces the problem to the partition with the largest bb. At that endpoint

a=j−r(j),b=∑lhl−a+γj.a=j-r(j),\qquad b=\sum_l h_l-a+\gamma_j .

The nonnegative budget implies that ∑lql≥a\sum_l q_l\ge a. If γj=0\gamma_j=0, (2) permits the required number of size-jj parts for any assignment of the size-ii parts. If γj=1\gamma_j=1, condition 5 of Theorem 12 applies, since this partition has a≤ia\le i. It gives an arm with vl≥r(j)v_l\ge r(j) and ql+vl≥jq_l+v_l\ge j. By (2), put at least j−vl≤aj-v_l\le a smaller pieces there to produce one carry. This accommodates all parts of the endpoint partition, proving the claim for every partition in this class.

3. Three regular arms and one smaller extra part

Here i≥2i\ge2 and we have three regular arm capacities x1,x2,x3x_1,x_2,x_3, each at least j+1j+1. Write n=1+λ+∑lxln=1+\lambda+\sum_l x_l, where λ=0\lambda=0 for a tripod and λ=1\lambda=1 when an extra one-edge arm stays with the centre. Suppose there is a part of size mm with 1≤m<i1\le m\lt i in addition to the parts of sizes i,ji,j. We will reserve size jj for the centre, including the one-edge arm if present, and place size mm in a regular arm. Superscript primes will indicate the capacities, quotients, and residues after subtracting mm from that arm.

Set U=∑lulU=\sum_l u_l and V=∑lvlV=\sum_l v_l, with sums over the three regular arms. The admissibility tests on the residues at ii and jj give

U+λ−maxlul<i,V+λ−maxlvl<j.U+\lambda-\max_l u_l<i,\qquad V+\lambda-\max_l v_l<j. \tag{3}

Indeed, tests 1 and 2 at a modulus kk say that the sum of the arm residues other than a largest is less than kk. For four arms and k≥2k\ge2, the residue of the one-edge arm is 1. A largest residue can be taken among the three regular arms unless they are all zero, in which case the corresponding inequality in (3) holds directly. Both ii and jj lie within the admissibility test range when there is a smaller extra part in Theorems 9 and 10.

For each regular arm set wl=hl+vlw_l=h_l+v_l and dl=ql−hld_l=q_l-h_l. Then

xl=ihl+wl,wl=idl+ul.x_l=i h_l+w_l,\qquad w_l=i d_l+u_l .

In particular dl≥0d_l\ge0, and the arm can produce a carry in (2) exactly when wl≥iw_l\ge i, by the identity

xl−(j−vl)i=(wl−i)j.x_l-(j-v_l)i=(w_l-i)j. \tag{4}

Define r=V+λ−ir=V+\lambda-i. When r>0r\gt0, the partition without mm with the largest count of size-jj parts has a0=j−ra_0=j-r smaller parts and ∑lhl+2−a0\sum_l h_l+2-a_0 bigger parts including the centre. It exists precisely when ∑lwl+λ≥2i\sum_l w_l+\lambda\ge2i. When it exists, Section 2 and (2) show that there is an arm pp with

vp≥r,wp≥i.v_p\ge r,\qquad w_p\ge i . \tag{5}

All size-ii and size-jj parts outside the centre of that partition belong to regular arms, so the existence of an optional one-edge arm does not change (5).

The endpoint with the most size-jj parts

For fixed mm, assume at least one partition in the required class exists. At the endpoint with the largest count of size-jj parts, put

ρ=⌈(V+1+λ−m)/j⌉,qquada=ρj−(V+1+λ−m),b+1=∑lhl+ρ−a.\rho=\left\lceil (V+1+\lambda-m)/j\right\rceil,qquad a=\rho j-(V+1+\lambda-m),\qquad b+1=\sum_l h_l+\rho-a .

Here 0≤a≤i0\le a\le i, b+1≥1b+1\ge1, and ρ∈{0,1,2}\rho\in\{0,1,2\} by (3) and 1≤m<i1\le m\lt i. If mm goes in arm ll, its size-jj quotient decreases by 11 exactly when vl<mv_l\lt m. Thus (2) needs at least ρ−1+𝟏vl<m\rho-1+\mathbf 1_{v_l\lt m} carries. Write H=∑lhlH=\sum_l h_l. Existence of the partition gives H≥a+1−ρH\ge a+1-\rho.

Case ρ=0\rho=0. All vl<mv_l\lt m. Subtracting mm from any arm leaves at least H−1≥aH-1\ge a slots for the size-ii parts, since xl−m≥(hl−1)jx_l-m\ge (h_l-1)j. No carry is needed.

Case ρ=1\rho=1. We have H≥aH\ge a. If some vl≥mv_l\ge m, put mm there, leaving x′l≥hljx'_l\ge h_l j, so there are at least HH slots for the size-ii parts and no carry is needed. Suppose all vl<mv_l\lt m. We will find an arm ll with vl≥rv_l\ge r and wl≥mw_l\ge m. Subtracting mm there leaves x′l≥ihlx'_l\ge i h_l, and the wrapped size-jj residue is v′l=vl+j−mv'_l=v_l+j-m. The new carry costs m−vl≤a=m−rm-v_l\le a=m-r smaller parts. This many fit in the arm because hl≥m−vlh_l\ge m-v_l. Thus (2) gives feasibility.

To find such an arm, if r>0r\gt0 and ∑lwl+λ≥2i\sum_l w_l+\lambda\ge2i, use (5). In the other cases, suppose no arm satisfies both bounds. Every arm with vl≥rv_l\ge r then has wl<mw_l\lt m. If an arm has vl<rv_l\lt r, then r>0r\gt0 and H+V+λ≤2i−1H+V+\lambda\le2i-1, giving wl≤H+r−1≤i−2w_l\le H+r-1\le i-2. Hence wl<iw_l\lt i for all arms, so ul=wlu_l=w_l. We have

U+λ=H+V+λ≥a+V+λ=i+m.U+\lambda=H+V+\lambda\ge a+V+\lambda=i+m.

By (3), there is an arm with ul>mu_l\gt m, so this arm must have vl<rv_l\lt r. The other two vv residues sum to at least i−λ+1i-\lambda+1, and each is at most m−1m-1. Each is thus at least i−λ+2−mi-\lambda+2-m. The other two uu residues are at least their corresponding vv residues, as ul=wlu_l=w_l in all arms. Every pair of uu residues now sums to at least i−λi-\lambda, contradicting (3). This proves the required existence.

Case ρ=2\rho=2. Now r>mr\gt m and a=j−r+m=a0+ma=j-r+m=a_0+m. Since H≥a−1H\ge a-1, the partition without mm at a0a_0 exists. Take the arm pp from (5). If an arm other than pp has vl≥mv_l\ge m, place mm there and produce the required carry in arm pp at cost j−vp≤a0j-v_p\le a_0. The arm receiving mm still has room for hlh_l smaller parts, and qp≥hp+1q_p\ge h_p+1, so the total room for smaller parts is at least H+1≥aH+1\ge a. If wp≥i+mw_p\ge i+m, we may instead place mm in arm pp: it has vp≥r>mv_p\ge r\gt m, still has a carry by (4), and its carry costs j−vp+m≤aj-v_p+m\le a. Again there is room for at least H+1H+1 smaller parts.

In the remaining case the other two arms have vl<mv_l\lt m and wp<i+mw_p\lt i+m. If another arm ll has wl≥mw_l\ge m, put mm there. Arm pp can produce its usual carry and the adjusted arm ll can produce a carry at cost m−vlm-v_l, as in the case ρ=1\rho=1. Both are needed because vl<mv_l\lt m. Their total cost is at most aa, since

a−[(j−vp)+(m−vl)]=i−λ−vk≥0a-[(j-v_p)+(m-v_l)]=i-\lambda-v_k\ge0

for the remaining arm kk, whose vk<m<iv_k\lt m\lt i. There is still room for at least H+1H+1 smaller parts. Finally, if neither other arm has wl≥mw_l\ge m, we have ul=wl<mu_l=w_l\lt m on both and up=wp−i<mu_p=w_p-i\lt m. But H≥a−1H\ge a-1 implies

U+λ=H+V+λ−i≥i+m.U+\lambda=H+V+\lambda-i\ge i+m.

This would force maxlul>m\max_l u_l\gt m by (3). All possibilities have now been covered, proving feasibility at the largest count of size-jj parts.

The endpoint with the fewest size-jj parts

Put R=⌊(U+λ−m)/i⌋R=\lfloor(U+\lambda-m)/i\rfloor. At the endpoint with the smallest count of size-jj parts, the count outside the centre is b=U+λ−m−Rib=U+\lambda-m-Ri. The budget after placing mm in arm ll is

K=1−R−𝟏ul<m.K=1-R-\mathbf 1_{u_l\lt m} .

This follows by using a+b=∑lql+R−1a+b=\sum_l q_l+R-1 in the budget formula. By (3), R≤1R\le1. If R≤0R\le0, the budget is nonnegative for every choice of arm. The largest-count partition and (1) then give every partition for this mm. If R=1R=1, only the first endpoint still needs a proof, since every later budget is at least zero for any placement of mm.

Suppose R=1R=1. Since U+λ≥i+mU+\lambda\ge i+m, (3) gives maxlul>m\max_l u_l\gt m. Choose an arm with ul≥mu_l\ge m, so K=0K=0 and ∑lu′l=b+i−λ\sum_l u'_l=b+i-\lambda. At this budget we can place ∑lmin(h′l,u′l)\sum_l\min(h'_l,u'_l) bigger pieces. The difference between this number and ∑lu′l\sum_l u'_l comes only from the arms with d′l=0d'_l=0. More precisely, the number of bigger pieces possible is

∑lu′l−∑l:d′l=0v′l,\sum_l u'_l-\sum_{l:d'_l=0}v'_l,

because h′l−u′l=id′l−v′lh'_l-u'_l=i d'_l-v'_l. It suffices to make the sum of the indicated v′lv'_l at most i−λi-\lambda.

Placing mm in an arm with ul≥mu_l\ge m leaves qlq_l unchanged and increases dld_l by one if vl<mv_l\lt m, leaving it unchanged otherwise. If at least two dld_l were positive before the placement, at most one d′ld'_l is zero. In a zero arm v′l≤u′l≤i−1≤i−λv'_l\le u'_l\le i-1\le i-\lambda, as required.

Suppose only arm pp originally had positive dpd_p. The two other residues satisfy ∑l≠pvl≤i−λ\sum_{l\ne p}v_l\le i-\lambda. For r≤0r\le0 this follows from V≤i−λV\le i-\lambda. For r>0r\gt0 we have ∑lwl+λ≥U+i+λ≥2i+m\sum_l w_l+\lambda\ge U+i+\lambda\ge2i+m, so (5) applies and its carry arm must be pp. If the placement of mm increases the number of positive arms, the preceding argument applies. Otherwise, the residue in any arm other than pp receiving mm decreases, and the required bound on the two zero arms persists.

If all three dld_l were zero, choose an arm with largest ulu_l. When this becomes positive, the two unaltered residues v′l=vlv'_l=v_l off that arm satisfy vl≤ulv_l\le u_l and have sum at most i−λi-\lambda by (3). When all three d′ld'_l remain zero, h′l=q′l≤u′lh'_l=q'_l\le u'_l in each arm, so the number of bigger pieces possible at zero cost is ∑lh′l=∑lq′l=a+b≥b\sum_l h'_l=\sum_l q'_l=a+b\ge b. This last case also gives feasibility. We have proved the first endpoint, and hence all partitions with the extra part.

4. Applying the reductions

For the tripod, take λ=0\lambda=0 and xl=al−1x_l=a_l-1. Theorem 9 reduces AVD to the partitions from Section 2 for 1≤i≤a1+a2−21\le i\le a_1+a_2-2 and those from Section 3 for 2≤i≤a1−32\le i\le a_1-3. In the latter range all arms have capacity at least i+2=j+1i+2=j+1. Sections 2 and 3 therefore prove Conjecture 1 for every admissible triple.

For the four-arm tree, the shorter sequence (a2,a3,a4)(a_2,a_3,a_4) is admissible, so its tree is AVD by Conjecture 1. Theorem 10 then reduces AVD of S(2,a2,a3,a4)S(2,a_2,a_3,a_4) to the same two kinds of partitions, now with a2a_2 in place of a1a_1 in the smaller-extra-part range and upper bound a2+a3−2a_2+a_3-2 for Section 2. For Section 3 take λ=1\lambda=1 and capacities a2−1,a3−1,a4−1a_2-1,a_3-1,a_4-1. All regular arms have capacity at least j+1j+1 in the range in question. This proves Conjecture 2. The proof applies throughout the original ranges and uses no lower bound on the middle arm.

Theorem 12 gives necessity of tests 1, 2 and 5. In the four-arm case, the necessity of decomposability of the remaining tripod follows from Theorem 10. Together with the proof above, the three tests characterize AVD for tripods, and characterize AVD for four-arm trees with a one-edge arm when also applied to the tripod obtained by removing that leaf.