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.
The stronger event identity
This note proves Conjecture 28 in Bernardi and Morales, Some probabilistic trees with algebraic roots, Electronic Journal of Combinatorics 23(2) (2016), P2.36, page 23. It is Conjecture 22 in arXiv:1501.01135v1. The paper shows that this identity implies its delta-process tree-probability conjecture. The companion PROOF.md gives an independent proof of that probability formula.
The argument below was developed by the parent research agent and independently checked by the analysis agent. The checks included a direct enumeration using the paper's event definitions, without relying on the adjugate representation used in the proof.
1. Exact event formulation
Fix , , a surjection , and a set . Intervals are cyclic: contains the vertices strictly after up to and including , while .
For any subset , including the full set, define the zero-one matrices
For a tuple of arbitrary subsets, let be the ordinary numerical matrix obtained from the source's event matrix by taking event indicators:
The index is read cyclically, so means .
Write and
Theorem. For every fixed surjection and every ,
The sums on the left include full subsets. This distinction from the proper-subset model is necessary. The proof treats those subsets explicitly.
2. Cyclic adjugates
Let with cyclic indices, all other entries zero. For a binary vector representing , put
The determinant and adjugate are
The first equality follows by expanding the cyclic matrix determinant: only the identity permutation and the complete cycle contribute. For the second, . Multiplication by gives the first expression in (4) times the identity. The equality with the adjugate follows first where the determinant is nonzero and then as a polynomial identity. Entry of the displayed sum is the product of the indicators along the unique cyclic path of length at most , proving the equality with .
When is proper, and . When , every entry of equals 1. The full-set matrix is not an inverse.
The source's two event matrices also satisfy
For , the interval is . For , the right side requires every vertex to belong to , agreeing with the special diagonal definition of .
Thus (2) uses row of , multiplied by when , and has a fixed last row of ones.
3. A row-replacement lemma that includes the singular case
Let be a nonempty set of selected rows. Fix all other rows in a matrix , whose last row is . Let .
For a binary vector , form by taking row from for and from otherwise, then multiplying each selected row by . Put .
Lemma. Suppose the are independent Bernoulli variables with parameters . Put
and assume . Let retain the rows of outside and use row of inside , multiplied by when . Then
Proof. First omit the factors on the selected rows, and call the resulting matrix . We claim the exact binary identity
If is proper, multiply by . The selected rows become the standard rows , while the other rows become those of . Since , expanding along the selected standard rows proves (7). The sign is positive because the same index set is removed from rows and columns.
If , a selected row of equals , as does the last row. Hence the left side of (7) is zero. On the right, the last row of is , and that row is retained because . The right side is also zero. Thus (7) holds even at the singular full-set matrix.
Restore the marked row factors. Equation (7) gives
Column of is column of minus times column of . The determinant on the right of (8) therefore depends only on the variables with , and is affine in each of them. These variables are disjoint from those in the prefactor. Independence and multilinearity in the columns yield
Finally, multiply the unmarked version of by and expand along its selected standard rows. Now the multiplication contributes . Restoring the factors shows that the right side of (9) is . This proves (6). ∎
The nonempty condition on is used when . It is supplied by surjectivity in the next step. The proof never assumes that itself is an inverse or determinant preserving at a full subset.
4. Replace the colors and evaluate the determinant
For each color , sample a vector with independent Bernoulli coordinates of parameters . All colors are independent.
Apply the lemma to the nonempty row set . Condition on the other colors while doing so. The last row remains throughout. Each replacement contributes a factor . After all replacements, the first rows are the corresponding rows of
and the last row is . Call this final matrix . Thus
Multiplication of by turns row into . Its last row becomes
Expansion along the first diagonal rows gives
Combining this with (10) proves
5. Membership coefficients and the conjecture
Set . One can first take all , so every probability and inverse used above is defined. The probability weight of a subset is then , and
Multiplying (11) by gives
This proves (3) for positive . Both sides of (3) are polynomials, so it proves the polynomial identity without restrictions on the indeterminates.
For the original membership vector , define as the set of tuples of arbitrary subsets with those counts. Define by requiring every subset to be proper, as in PROOF.md. The coefficient of on the right of (3) is
Indeed, the factor enumerates the choices for the distinguished first subset, while enumerates the other proper subsets.
The probability determinant in the source is the expectation of the determinant of the numerical event-indicator matrix. This follows directly from its Leibniz expansion: each product of indicators is the indicator of the corresponding intersection of events. Taking coefficients in (3), dividing by , and averaging over the surjections therefore gives
This is the full published Conjecture 28. It holds before averaging over surjections, for each fixed surjection separately. The conditional-probability notation in (13) assumes , as in the source setting; the polynomial identity (3) and the count (12) require no such restriction. ∎
Relation to the tree identity
The source obtains its delta event matrix by summing the matrices in (2) over , with sign in the determinant expansion. Summing the right side of (3) with those signs gives
This recovers the tree-count polynomial for surjections, consistent with the independent Schur-complement proof. Both results belong to the same named conjecture investigation; the stronger identity and its specializations are not counted as extra named conjectures.
Exact check
Run python verify_events.py from this directory. The verifier implements (1)–(2) literally and computes signed integer determinants. It compares every membership coefficient with (12) for 342 pairs and 438,952 subset-tuple determinants: all through , and . All comparisons passed. No adjugate or Bernoulli identity is used by that verifier, and no part of the proof relies on the finite range checked.