random_greedy_survival_poly
For a finite simple graph J on a finite vertex type V with decidable equality and decidable adjacency, and a vertex subset A : Finset V, the formal polynomial in ℝ[X] in the variable Y = 1 - t, recursively defined on |E(J)| by mapping each recursive polynomial on J - e and A ∪ V(e) for edges e incident to A via the zero-constant antiderivative p ↦ ∑_n (p.coeff n / (n + 1)) X^(n + 1), summing over all such incident edges e, and setting the constant term to 1 minus the evaluation of this sum at 1, so that it evaluates to 1 at 1.
Statement
noncomputable def random_greedy_survival_poly {V : Type*} [Fintype V] [DecidableEq V] (J : SimpleGraph V) [DecidableRel J.Adj] (A : Finset V) : Polynomial ℝ
- Defined in
- arXiv:2611.13571 Lemma 3.1
- Verified
- 12 Nov 2026
- Axioms
- none listed
- Used by 1
- random_greedy_survival_probFor a finite simple graph J on a finite vertex type V with decidable equality and decidable adjacency, a vertex subset A : Finset V, and…
Read back from the Lean
A recursive definition of random_greedy_survival_poly, which takes:
- a finite type V with decidable equality,
- a simple graph J on V with decidable adjacency, and
- a finite subset A of vertices of V,
and returns a real polynomial Polynomial ℝ.
The function is defined by well-founded recursion on the number of edges in J (J.edgeFinset.card):
1. Let incident be the set of edges e in J.edgeFinset that are incident to at least one vertex in A (i.e., ∃ v ∈ A, v ∈ e).
2. For each edge e ∈ incident, make a recursive call to random_greedy_survival_poly on the graph J.deleteEdges {e} with the vertex set A ∪ {endpoints of e}.
3. Take the formal antiderivative vanishing at 0 of each resulting polynomial (mapping $\sum a_n X^n$ to $\sum \frac{a_n}{n+1} X^{n+1}$).
4. Sum these antiderivatives over all e ∈ incident to obtain a polynomial step_sum.
5. Return the polynomial $P(X) = (1 - \text{step\_sum}(1)) + \text{step\_sum}(X)$ (i.e., the unique polynomial with antiderivative part given by step_sum and normalized so that $P(1) = 1$).
If incident is empty (e.g. if J has no edges incident to A), step_sum is 0 and the definition yields the constant polynomial 1.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The survival polynomial of vertex set A in graph J under random greedy matching. -/ noncomputable def random_greedy_survival_poly {V : Type*} [Fintype V] [DecidableEq V] (J : SimpleGraph V) [DecidableRel J.Adj] (A : Finset V) : Polynomial ℝ := let incident : Finset (Sym2 V) := J.edgeFinset.filter (fun e => ∃ v ∈ A, v ∈ e) let poly_antideriv' (p : Polynomial ℝ) : Polynomial ℝ := ∑ n ∈ p.support, Polynomial.C (p.coeff n / (n + 1 : ℝ)) * Polynomial.X ^ (n + 1) let step_sum := ∑ e ∈ incident.attach, poly_antideriv' (random_greedy_survival_poly (J.deleteEdges ↑({e.val} : Finset (Sym2 V))) (A ∪ e.val.toMultiset.toFinset)) Polynomial.C (1 - step_sum.eval 1) + step_sum termination_by J.edgeFinset.card decreasing_by have he_inc : e.val ∈ incident := e.property have he_edge : e.val ∈ J.edgeFinset := (Finset.mem_filter.mp he_inc).1 have h1 : (J.deleteEdges ↑({e.val} : Finset (Sym2 V))).edgeFinset = J.edgeFinset \ {e.val} := SimpleGraph.edgeFinset_deleteEdges ({e.val} : Finset (Sym2 V)) rw [h1, Finset.sdiff_singleton_eq_erase] exact Finset.card_erase_lt_of_mem he_edge