digraph_common_predecessor_edge_le_sum_choose
The common-predecessor graph has at most the sum over vertices of the number of pairs in each out-neighborhood.
Statement
theorem digraph_common_predecessor_edge_le_sum_choose (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] : (digraph_common_predecessor_graph D).edgeFinset.card ≤ ∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2
- Source
- General form of the auxiliary edge count in arXiv:2610.11517, Proposition 4.3.
- Verified
- 03 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- digraph_common_predecessor_graphThe simple graph joining distinct vertices that have a common in-neighbor in the digraph.
- Used by 2
- digraph_seven_two_overlap_order_ge_43A finite digraph with every outdegree at least seven and twice its common-predecessor overlap below its order has at least 43 vertices.
- digraph_oriented_small_overlap_good_centerIn an oriented arc-dominated digraph, if repeated common-predecessor pair incidences are less than one third of the order, some vertex has…
The proof, explained
The proof bounds the number of edges in the common-predecessor graph by associating each edge to a common predecessor. First, it shows that every edge {u, v} arises from some shared in-neighbor w, so the edge set is covered by the union over all w of the pairs of distinct vertices in the out-neighborhood of w. The result then follows by the union bound and the fact that the number of unordered pairs of distinct vertices in an out-neighborhood of size k is (k choose 2).
Adjacency in the common-predecessor graph is decidable.
For any two vertices u and v, adjacency in the common-predecessor graph means that u ≠ v and there exists a common predecessor w. Decidability of this bounded existential quantifier over the finite vertex type α is inferred automatically from the decidability of adjacency in the underlying digraph D.
intro u v unfold digraph_common_predecessor_graph infer_instance
For each vertex v, define its out-neighborhood outs v and the set edgesAt v of all unordered pairs of distinct out-neighbors.
We work classically and define outs v to be the finset of all out-neighbors of v in D (vertices w such that D.Adj v w). We then define edgesAt v as the finset of unordered pairs s(x, y) formed by distinct elements x, y in outs v, obtained as the image of the off-diagonal pairs (outs v).offDiag under the canonical quotient map.
classical let outs : α → Finset α := fun v => Finset.univ.filter (fun w => D.Adj v w) let edgesAt : α → Finset (Sym2 α) := fun v => (outs v).offDiag.image Sym2.mk.uncurry
Every edge of the common-predecessor graph belongs to the union over all vertices w of edgesAt w.
Let e be an edge of the common-predecessor graph. By induction on unordered pairs, e can be written as s(u, v). By the definition of the graph, u ≠ v and there exists a vertex w with w → u and w → v in D. Thus both u and v belong to outs w. Since u ≠ v, the pair (u, v) is in (outs w).offDiag, so its image s(u, v) is in edgesAt w. Hence e belongs to the union of edgesAt w over all vertices w in the graph.
uses
Sym2.ind,SimpleGraph.mem_edgeFinset,SimpleGraph.mem_edgeSet,Finset.mem_biUnion.mpr,Finset.mem_univ,Finset.mem_image.mpr,Finset.mem_offDiag.mprhave hcover : (digraph_common_predecessor_graph D).edgeFinset ⊆ (Finset.univ : Finset α).biUnion edgesAt := by intro e he induction e using Sym2.ind with | h u v => rw [SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet] at he obtain ⟨hne, w, hwu, hwv⟩ := he apply Finset.mem_biUnion.mpr refine ⟨w, Finset.mem_univ _, ?_⟩ apply Finset.mem_image.mpr refine ⟨(u,v), ?_, rfl⟩ apply Finset.mem_offDiag.mpr refine ⟨?_, ?_, hne⟩ · simp [outs, hwu] · simp [outs, hwv]
The number of edges in the common-predecessor graph is at most the sum over all vertices v of (|outs v| choose 2).
Since the edge set of the common-predecessor graph is covered by the union of edgesAt v over all v, its cardinality is at most the cardinality of that union (by Finset.card_le_card). By subadditivity of cardinality over unions (Finset.card_biUnion_le), this is bounded by the sum of |edgesAt v| over all vertices v. Finally, each edgesAt v consists of all unordered pairs of distinct elements from outs v, so its cardinality is precisely (|outs v| choose 2) by Sym2.card_image_offDiag. Combining these steps yields the desired bound.
uses
Finset.card_le_card,Finset.card_biUnion_le,Finset.sum_congr,Sym2.card_image_offDiagcalc (digraph_common_predecessor_graph D).edgeFinset.card ≤ ((Finset.univ : Finset α).biUnion edgesAt).card := Finset.card_le_card hcover _ ≤ ∑ v ∈ (Finset.univ : Finset α), (edgesAt v).card := Finset.card_biUnion_le _ = ∑ v : α, Nat.choose (outs v).card 2 := by apply Finset.sum_congr rfl intro v _ exact Sym2.card_image_offDiag (outs v)
Sym2.ind- To prove a property for all unordered pairs, it suffices to prove it for pairs of the form s(x, y).
SimpleGraph.mem_edgeFinset- An element belongs to the edge finset of a simple graph if and only if it belongs to its edge set.
SimpleGraph.mem_edgeSet- An unordered pair s(v, w) belongs to the edge set of a simple graph if and only if v and w are adjacent.
Finset.mem_biUnion.mpr- If an element belongs to t a for some a in s, then it belongs to the union of the sets t a over a in s.
Finset.mem_univ- Every element of a finite type belongs to the universal finset.
Finset.mem_image.mpr- If an element is the image of some a in s under f, then it belongs to the image of s under f.
Finset.mem_offDiag.mpr- A pair (u, v) belongs to the off-diagonal of s if both u and v belong to s and u ≠ v.
Finset.card_le_card- If a finite set s is a subset of t, then |s| ≤ |t|.
Finset.card_biUnion_le- The cardinality of a union of finite sets is at most the sum of the cardinalities of the individual sets.
Finset.sum_congr- Two sums over finite sets are equal if their index sets are equal and their summands agree on every element.
Sym2.card_image_offDiag- The number of unordered pairs of distinct elements from a finite set s is (|s| choose 2).
- The helper instance on lines 1–4 is a formal Lean detail establishing the decidability of graph adjacency, which Mathlib requires to construct the finite set of edges (edgeFinset) on a finite type. On paper, this is taken for granted.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
private instance in478_general_edge_count_decAdj {α : Type} [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] : DecidableRel (digraph_common_predecessor_graph D).Adj := by intro u v unfold digraph_common_predecessor_graph infer_instancetheorem digraph_common_predecessor_edge_le_sum_choose (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] : (digraph_common_predecessor_graph D).edgeFinset.card ≤ ∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2 := by classical let outs : α → Finset α := fun v => Finset.univ.filter (fun w => D.Adj v w) let edgesAt : α → Finset (Sym2 α) := fun v => (outs v).offDiag.image Sym2.mk.uncurry have hcover : (digraph_common_predecessor_graph D).edgeFinset ⊆ (Finset.univ : Finset α).biUnion edgesAt := by intro e he induction e using Sym2.ind with | h u v => rw [SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet] at he obtain ⟨hne, w, hwu, hwv⟩ := he apply Finset.mem_biUnion.mpr refine ⟨w, Finset.mem_univ _, ?_⟩ apply Finset.mem_image.mpr refine ⟨(u,v), ?_, rfl⟩ apply Finset.mem_offDiag.mpr refine ⟨?_, ?_, hne⟩ · simp [outs, hwu] · simp [outs, hwv] calc (digraph_common_predecessor_graph D).edgeFinset.card ≤ ((Finset.univ : Finset α).biUnion edgesAt).card := Finset.card_le_card hcover _ ≤ ∑ v ∈ (Finset.univ : Finset α), (edgesAt v).card := Finset.card_biUnion_le _ = ∑ v : α, Nat.choose (outs v).card 2 := by apply Finset.sum_congr rfl intro v _ exact Sym2.card_image_offDiag (outs v)