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.

Both conjectures in §4 of Horňák and Woźniak's On arbitrarily vertex decomposable trees hold. Every tripod passing their arithmetic admissibility tests admits a partition into connected pieces of any prescribed sizes. A four-arm tree with a one-edge arm has the same property whenever both its arm sequence and the remaining tripod's sequence pass the tests. Original conjectures · Journal article

An explicit construction gives both kinds of decomposable trees for every prescribed shortest regular arm, answering two further questions from the authors’ 2010 problem collection.

The proof treats the first and last feasible counts of the larger part in the two-consecutive-size reduction. It also shows that three of the five admissibility tests suffice.

Proof · Literature check · Research discussion

Lean status: partial. HornakTwoArm.lean proves arbitrary vertex decomposability for tripods with a positive short arm of length at most two, conditional on source tests 1 and 5. HornakGroupGraph.lean proves every positive tripod partition containing a part larger than the positive short arm from those tests; HornakPath.lean unconditionally realizes partitions with a sublist summing to that arm. HornakMerge.lean reduces the remaining all-small case to partitions with no mergeable noncentral pair; HornakSmallBalance.lean proves the unique-largest balancing step. 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.

The standard-library check compares the arithmetic tests to direct partition searches on small trees and checks the local transfer by direct bin allocation. It also checks the admissibility of instances from the explicit construction.

python3 results/hornak-wozniak/verify.py

An optional symbolic cross-check uses z3-solver to test the two local endpoint implications as linear integer formulas. The written proof establishes the implications directly.

python3 results/hornak-wozniak/verify_symbolic.py