Lean status: the complete statement in this note now has strict source, all-owned axiom, and pinned stock-kernel verification. See the formalization section for the exact definitions, endpoints and receipt. The combined package gate remains separate.
Statement and source
Bernardi and Morales state the conjecture as Conjecture 27 in Some probabilistic trees with algebraic roots, Electronic Journal of Combinatorics 23(2) (2016), P2.36, page 23, DOI 10.37236/4954. It is Conjecture 21 in arXiv:1501.01135v1.
Fix integers and . Write , with its cyclic order. For a proper subset , define when . When , define to be the next element of after in cyclic order. A singleton complement therefore gives a fixed point.
For , let
The set consists of the empty tuple if , and is empty otherwise. Given a map , let have arcs
Every nonroot vertex has one outgoing arc, while has none. Thus this graph is a tree exactly when every forward orbit reaches .
Theorem. For every fixed map ,
In particular, if , is nonempty, is uniform in that set, and is an independent uniform surjection, then
Equation (2) is the full published tree-probability conjecture. The fixed-map assertion (1) is stronger: neither surjectivity nor the inequality is needed. The companion EVENT_PROOF.md proves the separate, stronger event-determinant Conjecture 28. This file gives the tree identity its own proof.
1. The cyclic Laplacian and elimination
All matrices have rows and columns indexed by unless specified otherwise. For row and column sets , use with indices in increasing order. Empty determinants equal 1.
Let be the matrix with , with subscripts taken cyclically modulo , and all other entries zero. Set
For a nonempty set , let be the Laplacian of the cyclic successor on , extended by zero rows and columns on . Explicitly, its row at is . If is a singleton, this is the zero matrix. In particular, the row of at is .
Lemma 1. If and , then
and the Schur complement of in , on the remaining set , is
Proof. The successor graph restricted to a proper subset is a union of directed paths. Consequently is nilpotent. Ordering each path along its direction makes triangular with diagonal 1, proving the determinant assertion.
The inverse of is the finite sum of powers of . In the product , a contribution from to records the unique successor path from to whose internal vertices lie in . The product has coefficient when this path has at least one internal vertex. An arc with no internal vertex is already recorded with coefficient in . Subtracting the product therefore gives minus the cyclic-successor matrix on . When is a singleton, the returning path cancels its diagonal entry. This proves (3). The same statement for uses empty-block conventions. ∎
2. A determinant generating identity
Introduce commuting indeterminates . Put
and
Lemma 2. For an arbitrary matrix ,
Proof. Expand the left side by multilinearity in its rows. The coefficient of is the determinant formed by taking row of when , and row of when .
When , that determinant is . Otherwise put and place the indices of first by applying the same permutation to rows and columns. This does not change the determinant. From each row , subtract the linear combination of the selected rows. The resulting block matrix is
By Lemma 1 and the block determinant formula, its determinant is
Because has zero rows and columns outside , this is . The coefficient of every agrees with the right side of (5). ∎
Taking in (5) gives
Work for the moment over the rational-function field , where and is invertible. Set
Factoring in (5) yields
3. All minors, and the replacement of a block of rows
For any function of a proper subset define the normalized formal average
This notation is a linear functional on a finite sum. No analytic probability assumption on the indeterminates is needed.
Lemma 3. For all equally sized row and column sets ,
Proof. In (8), let all entries of be independent indeterminates. The principal-minor expansion followed by Cauchy–Binet gives, for any matrix ,
The polynomials appearing here are linearly independent: their monomials have distinct sets of row indices and column indices for distinct pairs . Equating their coefficients in (8) proves (9), after exchanging the names . In particular, the size-one assertion gives . ∎
The all-minor property in (9) is commonly called the determinant-preserving property. Its general closure rules are known; see Dereziński, Liang and Mahoney, arXiv:1912.04533v3, Definition 4 and Lemma 4. Here (5) proves that property for the cyclic matrices required by this conjecture. The following short argument supplies the precise closure step needed, without taking it as an external assumption.
Lemma 4. Suppose a square determinant has a specified set of rows taken from , with a fixed common set of columns. Its other rows are independent of . Applying to that determinant has the same effect as replacing the specified rows by the corresponding rows of .
Proof. Expand the determinant along the specified rows. Each term is a signed product of a square minor of and a complementary minor using the other rows. The latter factor is independent of . Apply (9) to the former factor and sum the Laplace expansion again. ∎
It follows that independently averaged matrices can be replaced one color at a time, even when the different colors occupy several interspersed rows. Entrywise expectations alone would not justify this step; (9) for all row and column sets does.
4. The cofactor of the mean matrix
Let be the all-ones column vector. The cycle Laplacian satisfies
Indeed, Lemma 1 gives a principal cofactor equal to 1, so has rank . Its left and right nullspaces are spanned by and . Hence the adjugate is a scalar multiple of , and the principal cofactor fixes that scalar at 1.
Since , the adjugate multiplication identity and (6)–(7) give
Writing , we therefore have
5. A fixed map and the tree indicator
Fix . For a tuple of proper subsets , form the matrix whose row at is row of , restricted to the columns in . Thus its row is , after deleting the root column.
We have the elementary indicator identity
To see this directly, if the graph contains a directed cycle, the rows indexed by that cycle sum to zero. A loop supplies a zero row. Either way the determinant is zero. If there is no directed cycle, every vertex reaches . Order the nonroot vertices by their distance from , and apply the same order to rows and columns. The matrix becomes triangular with diagonal 1, so its determinant is 1. This also proves (14) without invoking the matrix-tree theorem.
Apply the formal product average , giving each its own independent sum with weight . The word independent refers to this product of finite sums; the sets will be conditioned on the membership counts only at the end.
For each color , use Lemma 4 on the row set . Replace the rows belonging to that color by the corresponding rows of . Other colors are fixed during this step. A color with no assigned rows simply contributes the average of 1. After all replacements, the matrix is . Equations (13)–(14) give
Clearing denominators proves the polynomial identity
The coefficient of on the left counts the trees in (1). By (4), its coefficient on the right is . This proves (1).
When , averaging (1) over surjections gives (2). Finally, the map that deletes an empty first set is a bijection from the tuples in with to . Thus the ratio in (2) also has the interpretation stated in the source. ∎
6. Color-weight refinement
Summing (15) over all maps , with weight , gives
The determinant notation on the left means the determinant of the submatrix indexed by after taking the indicated sum. Its row-multilinear expansion is the sum over maps used above. In particular, prescribing color fiber sizes gives the exact tree count
Positive fiber sizes recover surjections. Formula (16) and the fixed-map theorem are refinements of the same conjecture, not separate conjectures counted as additional results.
Audit and verification
The parent research agent independently checked the source definition, Lemmas 1–3, the independent-color replacement, the adjugate evaluation, and coefficient extraction. The parent also proposed the fixed-map refinement, proved here by Lemma 4. The companion verify.py independently checks 71 fixed maps and 111,721 literal process pairs, along with 25 arbitrary-matrix instances of (5). Those finite calculations are checks of implementation and conventions; the proof above has no upper bound on , , or the membership counts.