finset_one_inclusion_graph_card_edgeFinset_le
If a finite set system F has VC dimension at most d, its one-inclusion graph has at most d·|F| edges.
Statement
theorem finset_one_inclusion_graph_card_edgeFinset_le {α : Type*} [DecidableEq α] (𝓕 : Finset (Finset α)) [Fintype (finset_one_inclusion_graph 𝓕).edgeSet] (d : ℕ) (hd : 𝓕.vcDim ≤ d) : (finset_one_inclusion_graph 𝓕).edgeFinset.card ≤ d * 𝓕.card
- Formalizes
- arXiv:2610.08151 (Polynomial-in-r bounds for forbidden traces of uniform hypergraphs), Lemma 2 (one-inclusion graph edge bound). The edge set's Fintype instance is a hypothesis; the count does not depend on it.
- Verified
- 11 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- finset_one_inclusion_graphThe one-inclusion graph G_1(F) of a set system F: its vertices are the members of F, two members adjacent when their symmetric difference…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
The proof, explained
The proof establishes that the one-inclusion graph of a finite set family 𝓕 with VC dimension at most d has at most d * |𝓕| edges. It first establishes an upper bound of 2 * d * |𝒜| on the number of ordered pairs differing by a single element, by induction on the size of the underlying universe using a subfamily decomposition (Haussler's technique). Finally, it relates this bound to the graph edges via the handshaking property that twice the number of undirected edges equals the number of ordered adjacent vertex pairs, and divides by 2.
The intersection of the one-inclusion pairs of 𝒜 and ℬ is contained in the one-inclusion pairs of 𝒜 ∩ ℬ.
Let p = (A, B) be an ordered pair belonging to both sets of pairs. Then both A and B belong to 𝒜 and to ℬ, so they belong to 𝒜 ∩ ℬ, and their symmetric difference still has cardinality 1.
uses
Finset.mem_interintro p hp simp only [finset_one_inclusion_pairs, Finset.mem_inter, Finset.mem_filter, Finset.mem_product] at hp ⊢ exact ⟨⟨⟨hp.1.1.1, hp.2.1.1⟩, ⟨hp.1.1.2, hp.2.1.2⟩⟩, hp.1.2⟩
The one-inclusion pairs of 𝒜 are partitioned according to membership of element a, giving |E| ≤ |E₀₀| + |E₁₁| + |E_X|.
We partition the pairs E into pairs E₀₀ where neither set contains a, pairs E₁₁ where both sets contain a, and pairs E_X where exactly one set contains a. By union cardinality bounds, |E| is bounded by the sum of their sizes.
uses
Finset.card_le_card,Finset.card_union_leset F0 := 𝒜.nonMemberSubfamily a set F1 := 𝒜.memberSubfamily a set E := finset_one_inclusion_pairs 𝒜 set E00 := E.filter (fun p => a ∉ p.1 ∧ a ∉ p.2) set E11 := E.filter (fun p => a ∈ p.1 ∧ a ∈ p.2) set EX := E.filter (fun p => (a ∈ p.1 ∧ a ∉ p.2) ∨ (a ∉ p.1 ∧ a ∈ p.2)) have hsplit : E ⊆ E00 ∪ E11 ∪ EX := by intro p hp simp only [E00, E11, EX, Finset.mem_union, Finset.mem_filter] by_cases h1 : a ∈ p.1 <;> by_cases h2 : a ∈ p.2 <;> simp [h1, h2, hp] have hcardE : E.card ≤ E00.card + E11.card + EX.card := (Finset.card_le_card hsplit).trans ((Finset.card_union_le _ _).trans (Nat.add_le_add_right (Finset.card_union_le _ _) _)) -- E00 sits inside the pairs of F0
The pairs in E₀₀ form a subset of the one-inclusion pairs of F₀.
For any pair (A, B) in E₀₀, neither A nor B contains a, so both belong to the non-member subfamily F₀ of 𝒜. Thus the pair is a one-inclusion pair of F₀.
uses
Finset.mem_nonMemberSubfamilyhave h00 : E00 ⊆ finset_one_inclusion_pairs F0 := by intro p hp simp only [E00, E, finset_one_inclusion_pairs, Finset.mem_filter, Finset.mem_product] at hp ⊢ obtain ⟨⟨⟨hA, hB⟩, hP⟩, ha1, ha2⟩ := hp exact ⟨⟨Finset.mem_nonMemberSubfamily.2 ⟨hA, ha1⟩, Finset.mem_nonMemberSubfamily.2 ⟨hB, ha2⟩⟩, hP⟩
The cardinality of E₁₁ is at most the number of one-inclusion pairs of F₁.
The map (A, B) ↦ (A \ {a}, B \ {a}) injects E₁₁ into the one-inclusion pairs of the member subfamily F₁ because removing an element common to both sets preserves their symmetric difference and can be inverted by re-inserting a.
uses
Finset.card_le_card_of_injOnhave h11 : E11.card ≤ (finset_one_inclusion_pairs F1).card := by refine Finset.card_le_card_of_injOn (fun p => (p.1.erase a, p.2.erase a)) ?_ ?_ · intro p hp simp only [Finset.mem_coe, E11, E, finset_one_inclusion_pairs, Finset.mem_filter, Finset.mem_product] at hp ⊢ obtain ⟨⟨⟨hA, hB⟩, hP⟩, ha1, ha2⟩ := hp refine ⟨⟨Finset.mem_memberSubfamily.2 ⟨by rwa [Finset.insert_erase ha1], by simp⟩, Finset.mem_memberSubfamily.2 ⟨by rwa [Finset.insert_erase ha2], by simp⟩⟩, ?_⟩ have : symmDiff (p.1.erase a) (p.2.erase a) = symmDiff p.1 p.2 := by ext x by_cases hx : x = a · subst hx; simp [Finset.mem_symmDiff, ha1, ha2] · simp [Finset.mem_symmDiff, Finset.mem_erase, hx] rw [this]; exact hP · intro p hp q hq hpq simp only [Finset.mem_coe, E11, Finset.mem_filter] at hp hq simp only [Prod.mk.injEq] at hpq have e1 : p.1 = q.1 := by rw [← Finset.insert_erase hp.2.1, ← Finset.insert_erase hq.2.1, hpq.1] have e2 : p.2 = q.2 := by rw [← Finset.insert_erase hp.2.2, ← Finset.insert_erase hq.2.2, hpq.2] exact Prod.ext e1 e2
The cardinality of E_X is at most 2 * |F₀ ∩ F₁|.
For any pair (A, B) in E_X, their symmetric difference has size 1 and crosses a, so symmDiff A B = {a}. Therefore, one set is s and the other is s ∪ {a}, where s belongs to both F₀ and F₁. Mapping (A, B) to (A \ {a}, decide(a ∈ A)) gives an injection into (F₀ ∩ F₁) × Bool, which has size 2 * |F₀ ∩ F₁|.
uses
Finset.card_le_card_of_injOn,Fintype.card_boolhave hX : EX.card ≤ 2 * (F0 ∩ F1).card := by have hsd : ∀ p ∈ EX, symmDiff p.1 p.2 = {a} := by intro p hp simp only [EX, E, finset_one_inclusion_pairs, Finset.mem_filter] at hp obtain ⟨⟨-, hP⟩, hx⟩ := hp obtain ⟨x, hx1⟩ := Finset.card_eq_one.1 hP have : a ∈ symmDiff p.1 p.2 := by rw [Finset.mem_symmDiff]; tauto rw [hx1, Finset.mem_singleton] at this rw [hx1, this] have hcard2 : (F0 ∩ F1).card * 2 = ((F0 ∩ F1) ×ˢ (Finset.univ : Finset Bool)).card := by rw [Finset.card_product, Finset.card_univ, Fintype.card_bool] rw [mul_comm, hcard2] refine Finset.card_le_card_of_injOn (fun p => (p.1.erase a, decide (a ∈ p.1))) ?_ ?_ · intro p hp have hs := hsd p hp simp only [Finset.mem_coe, EX, E, finset_one_inclusion_pairs, Finset.mem_filter, Finset.mem_product] at hp obtain ⟨⟨⟨hA, hB⟩, -⟩, hx⟩ := hp have hiff : ∀ x, x ≠ a → (x ∈ p.1 ↔ x ∈ p.2) := by intro x hxa have : x ∉ symmDiff p.1 p.2 := by rw [hs]; simpa using hxa rw [Finset.mem_symmDiff] at this tauto simp only [Finset.mem_coe, Finset.mem_product, Finset.mem_univ, and_true, Finset.mem_inter, Finset.mem_nonMemberSubfamily, Finset.mem_memberSubfamily, F0, F1] rcases hx with ⟨ha1, ha2⟩ | ⟨ha1, ha2⟩ · have hBe : p.1.erase a = p.2 := by ext x by_cases hxa : x = a · subst hxa; simp [ha2] · rw [Finset.mem_erase]; exact ⟨fun h => (hiff x hxa).1 h.2, fun h => ⟨hxa, (hiff x hxa).2 h⟩⟩ refine ⟨⟨by rw [hBe]; exact hB, by simp⟩, by rwa [Finset.insert_erase ha1], by simp⟩ · have hAe : p.1.erase a = p.1 := Finset.erase_eq_of_notMem ha1 have hBi : insert a p.1 = p.2 := by ext x by_cases hxa : x = a · subst hxa; simp [ha2] · rw [Finset.mem_insert]; exact ⟨fun h => h.elim (fun e => absurd e hxa) (hiff x hxa).1, fun h => Or.inr ((hiff x hxa).2 h)⟩ rw [hAe] exact ⟨⟨hA, ha1⟩, by rw [hBi]; exact hB, ha1⟩ · intro p hp q hq hpq have hsp := hsd p hp have hsq := hsd q hq simp only [Prod.mk.injEq, decide_eq_decide] at hpq obtain ⟨he, hm⟩ := hpq have e1 : p.1 = q.1 := by by_cases ha : a ∈ p.1 · rw [← Finset.insert_erase ha, ← Finset.insert_erase (hm.1 ha), he] · rw [← Finset.erase_eq_of_notMem ha, ← Finset.erase_eq_of_notMem (fun h => ha (hm.2 h)), he] have e2 : p.2 = q.2 := by have h1 : p.2 = symmDiff p.1 {a} := by rw [← hsp, symmDiff_symmDiff_cancel_left] have h2 : q.2 = symmDiff q.1 {a} := by rw [← hsq, symmDiff_symmDiff_cancel_left] rw [h1, h2, e1] exact Prod.ext e1 e2
The split bound |E| ≤ |pairs(F₀ ∪ F₁)| + |pairs(F₀ ∩ F₁)| + 2 * |F₀ ∩ F₁| holds.
By submodularity of pairs, |pairs(F₀)| + |pairs(F₁)| ≤ |pairs(F₀ ∪ F₁)| + |pairs(F₀ ∩ F₁)|. Combining this with the bounds on E₀₀, E₁₁, and E_X, linear integer arithmetic closes the goal.
uses
Finset.card_union_add_card_inter,finset_one_inclusion_pairs_mono,finset_one_inclusion_pairs_interhave hUI : (finset_one_inclusion_pairs F0).card + (finset_one_inclusion_pairs F1).card ≤ (finset_one_inclusion_pairs (F0 ∪ F1)).card + (finset_one_inclusion_pairs (F0 ∩ F1)).card := by rw [← Finset.card_union_add_card_inter] exact Nat.add_le_add (Finset.card_le_card (Finset.union_subset (finset_one_inclusion_pairs_mono Finset.subset_union_left) (finset_one_inclusion_pairs_mono Finset.subset_union_right))) (Finset.card_le_card (finset_one_inclusion_pairs_inter F0 F1)) have := Finset.card_le_card h00 omega
In the base case where the universe u is empty, the family has 0 pairs and the bound holds.
If u = ∅, every set in 𝒜 must be empty, so no two sets can have symmetric difference of size 1. The set of pairs is empty, and its cardinality is 0, satisfying 0 ≤ 2 * (d * |𝒜|).
uses
Finset.card_eq_zero,Finset.subset_emptyinduction u using Finset.induction with | empty => intro 𝒜 h𝒜 d _ have : (finset_one_inclusion_pairs 𝒜).card = 0 := by rw [Finset.card_eq_zero, finset_one_inclusion_pairs, Finset.filter_eq_empty_iff] intro p hp rw [Finset.mem_product] at hp rw [Finset.subset_empty.1 (h𝒜 _ hp.1), Finset.subset_empty.1 (h𝒜 _ hp.2)] simp omega
For u = insert a u', all sets in F₀, F₁, F₀ ∪ F₁, and F₀ ∩ F₁ are subsets of u'.
By construction, members of F₀ do not contain a, and members of F₁ are formed by removing a from sets containing it. Since all original sets were in u = insert a u', removing or excluding a ensures they are subsets of u'.
uses
Finset.subset_insert_iff_of_notMem| insert a u hau ih => intro 𝒜 h𝒜 d hd set F0 := 𝒜.nonMemberSubfamily a set F1 := 𝒜.memberSubfamily a have hF0 : ∀ s ∈ F0, s ⊆ u := by intro s hs rw [Finset.mem_nonMemberSubfamily] at hs exact (Finset.subset_insert_iff_of_notMem hs.2).1 (h𝒜 s hs.1) have hF1 : ∀ s ∈ F1, s ⊆ u := by intro s hs rw [Finset.mem_memberSubfamily] at hs exact (Finset.subset_insert_iff_of_notMem hs.2).1 ((Finset.subset_insert _ _).trans (h𝒜 _ hs.1)) have hU : ∀ s ∈ F0 ∪ F1, s ⊆ u := by intro s hs rcases Finset.mem_union.1 hs with h | h exacts [hF0 s h, hF1 s h] have hI : ∀ s ∈ F0 ∩ F1, s ⊆ u := fun s hs => hF0 s (Finset.mem_inter.1 hs).1The VC dimension of F₀ ∪ F₁ is at most d, that of F₀ ∩ F₁ is at most d - 1, and F₀ ∩ F₁ is empty if d = 0.
Any set shattered by F₀ ∪ F₁ is also shattered by 𝒜, so vcDim(F₀ ∪ F₁) ≤ vcDim(𝒜) ≤ d. If a set s is shattered by F₀ ∩ F₁, then s ∪ {a} is shattered by 𝒜, implying |s| + 1 ≤ d, so vcDim(F₀ ∩ F₁) ≤ d - 1. When d = 0, F₀ ∩ F₁ cannot shatter ∅, so it is empty.
uses
Finset.sup_le,Finset.Shatters.card_le_vcDim,Finset.card_insert_of_notMemhave notmem : ∀ ℬ : Finset (Finset α), (∀ s ∈ ℬ, s ⊆ u) → ∀ s, ℬ.Shatters s → a ∉ s := by intro ℬ hℬ s hs ha obtain ⟨v, hv, hsv⟩ := hs.exists_superset exact hau (hℬ v hv (hsv ha)) have shU : ∀ s, (F0 ∪ F1).Shatters s → 𝒜.Shatters s := by intro s hs t ht have has := notmem _ hU s hs obtain ⟨w, hw, hsw⟩ := hs ht rcases Finset.mem_union.1 hw with hw | hw · rw [Finset.mem_nonMemberSubfamily] at hw exact ⟨w, hw.1, hsw⟩ · rw [Finset.mem_memberSubfamily] at hw exact ⟨insert a w, hw.1, by rw [Finset.inter_insert_of_notMem has, hsw]⟩ have shI : ∀ s, (F0 ∩ F1).Shatters s → 𝒜.Shatters (insert a s) := by intro s hs t ht have has := notmem _ hI s hs by_cases hat : a ∈ t · have hsub : t.erase a ⊆ s := by intro x hx rw [Finset.mem_erase] at hx have := ht hx.2 rw [Finset.mem_insert] at this exact this.resolve_left hx.1 obtain ⟨w, hw, hsw⟩ := hs hsub have hw1 := (Finset.mem_inter.1 hw).2 rw [Finset.mem_memberSubfamily] at hw1 refine ⟨insert a w, hw1.1, ?_⟩ rw [← Finset.insert_inter_distrib, hsw, Finset.insert_erase hat] · have hsub : t ⊆ s := by intro x hx have := ht hx rw [Finset.mem_insert] at this exact this.resolve_left (fun e => hat (e ▸ hx)) obtain ⟨w, hw, hsw⟩ := hs hsub have hw0 := (Finset.mem_inter.1 hw).1 rw [Finset.mem_nonMemberSubfamily] at hw0 refine ⟨w, hw0.1, ?_⟩ rw [Finset.insert_inter_of_notMem hw0.2, hsw] have vcU : (F0 ∪ F1).vcDim ≤ d := by unfold Finset.vcDim refine Finset.sup_le fun s hs => ?_ exact ((shU s (Finset.mem_shatterer.1 hs)).card_le_vcDim).trans hd have vcI : (F0 ∩ F1).vcDim ≤ d - 1 := by unfold Finset.vcDim refine Finset.sup_le fun s hs => ?_ have hs' := Finset.mem_shatterer.1 hs have h1 := (shI s hs').card_le_vcDim rw [Finset.card_insert_of_notMem (notmem _ hI s hs')] at h1 omega have hIempty : d = 0 → F0 ∩ F1 = ∅ := by intro hd0 by_contra hne have h1 := (shI ∅ (Finset.shatters_empty.2 (Finset.nonempty_iff_ne_empty.2 hne))).card_le_vcDim simp only [insert_empty_eq, Finset.card_singleton] at h1 omega
By the induction hypotheses on F₀ ∪ F₁ and F₀ ∩ F₁, the pair bound holds for 𝒜.
We apply the induction hypothesis to F₀ ∪ F₁ (with bound d) and to F₀ ∩ F₁ (with bound d - 1). Using |𝒜| = |F₀ ∪ F₁| + |F₀ ∩ F₁| and the splitting lemma, the bound follows by linear arithmetic: 2 * (d * |F₀ ∪ F₁|) + 2 * ((d - 1) * |F₀ ∩ F₁|) + 2 * |F₀ ∩ F₁| = 2 * (d * |𝒜|).
uses
Finset.card_memberSubfamily_add_card_nonMemberSubfamily,finset_one_inclusion_pairs_card_splithave ihU := ih (F0 ∪ F1) hU d vcU have ihI := ih (F0 ∩ F1) hI (d - 1) vcI have hcard : 𝒜.card = (F0 ∪ F1).card + (F0 ∩ F1).card := by rw [Finset.card_union_add_card_inter, add_comm, Finset.card_memberSubfamily_add_card_nonMemberSubfamily] have hedge : (finset_one_inclusion_pairs 𝒜).card ≤ (finset_one_inclusion_pairs (F0 ∪ F1)).card + (finset_one_inclusion_pairs (F0 ∩ F1)).card + 2 * (F0 ∩ F1).card := finset_one_inclusion_pairs_card_split a 𝒜 rcases Nat.eq_zero_or_pos d with hd0 | hdpos · have hI0 := hIempty hd0 subst hd0 rw [hI0] at hedge have h0 : (finset_one_inclusion_pairs (∅ : Finset (Finset α))).card = 0 := by simp [finset_one_inclusion_pairs] rw [h0, Finset.card_empty] at hedge simp only [zero_mul, mul_zero] at ihU ⊢ omega · have h1 : d * 𝒜.card = d * (F0 ∪ F1).card + d * (F0 ∩ F1).card := by rw [hcard, mul_add] have h2 : (d - 1) * (F0 ∩ F1).card + (F0 ∩ F1).card = d * (F0 ∩ F1).card := by obtain ⟨k, rfl⟩ := Nat.exists_eq_add_of_lt hdpos simp only [Nat.zero_add, Nat.add_sub_cancel] ring linarith
Applying the pairs bound with universe u = ⋃ 𝓕 gives at most 2 * (d * |𝓕|) one-inclusion pairs in 𝓕.
Setting u to the union of all sets in 𝓕 ensures every set in 𝓕 is contained in u. Since vcDim(𝓕) ≤ d, finset_one_inclusion_pairs_card_le yields |finset_one_inclusion_pairs 𝓕| ≤ 2 * (d * |𝓕|).
uses
finset_one_inclusion_pairs_card_le,Finset.le_supclassical have hpairs := finset_one_inclusion_pairs_card_le (𝓕.sup id) 𝓕 (fun s hs => Finset.le_sup (f := id) hs) d hd
Ordered pairs of adjacent vertices in the one-inclusion graph biject with finset_one_inclusion_pairs 𝓕.
We exhibit a bijection between pairs of adjacent vertices in the graph and elements of finset_one_inclusion_pairs 𝓕 via the canonical inclusion of vertices as sets.
uses
Finset.card_bijhave hbij : ((Finset.univ : Finset (𝓕 × 𝓕)).filter (fun x => (finset_one_inclusion_graph 𝓕).Adj x.1 x.2)).card = (finset_one_inclusion_pairs 𝓕).card := by apply Finset.card_bij (fun x _ => ((x.1 : Finset α), (x.2 : Finset α))) · intro x hx simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hx simp only [finset_one_inclusion_pairs, Finset.mem_filter, Finset.mem_product] exact ⟨⟨x.1.2, x.2.2⟩, hx⟩ · intro x _ y _ h simp only [Prod.mk.injEq] at h exact Prod.ext (Subtype.ext h.1) (Subtype.ext h.2) · intro b hb simp only [finset_one_inclusion_pairs, Finset.mem_filter, Finset.mem_product] at hb refine ⟨(⟨b.1, hb.1.1⟩, ⟨b.2, hb.1.2⟩), ?_, rfl⟩ simp only [Finset.mem_filter, Finset.mem_univ, true_and] exact hb.2
Twice the number of edges equals the number of one-inclusion pairs in 𝓕.
By SimpleGraph.two_mul_card_edgeFinset, the number of directed edges (adjacent vertex pairs) in a simple graph is twice the number of undirected edges.
uses
SimpleGraph.two_mul_card_edgeFinsethave key : 2 * (finset_one_inclusion_graph 𝓕).edgeFinset.card = (finset_one_inclusion_pairs 𝓕).card := by rw [← hbij] convert SimpleGraph.two_mul_card_edgeFinset (finset_one_inclusion_graph 𝓕)
The number of edges in the one-inclusion graph is at most d * |𝓕|.
Combining 2 * |E| = |finset_one_inclusion_pairs 𝓕| with the bound |finset_one_inclusion_pairs 𝓕| ≤ 2 * (d * |𝓕|) and dividing by 2 yields |E| ≤ d * |𝓕|.
uses
Nat.le_of_mul_le_mul_lefthave h2 : 2 * (finset_one_inclusion_graph 𝓕).edgeFinset.card ≤ 2 * (d * 𝓕.card) := by rw [key]; exact hpairs exact Nat.le_of_mul_le_mul_left h2 (by norm_num)
Finset.mem_inter- An element belongs to the intersection of two finsets if and only if it belongs to both.
Finset.card_le_card- If a finite set is a subset of another, its cardinality is at most the other set's cardinality.
Finset.card_union_le- The cardinality of the union of two finsets is at most the sum of their cardinalities.
Finset.mem_nonMemberSubfamily- A set s belongs to the non-member subfamily of a with respect to 𝒜 if and only if s is in 𝒜 and a ∉ s.
Finset.card_le_card_of_injOn- If a function maps a finite set injectively into another, the domain's cardinality is at most the codomain's cardinality.
Fintype.card_bool- The type Bool has exactly two elements.
Finset.card_union_add_card_inter- For any two finsets s and t, |s ∪ t| + |s ∩ t| = |s| + |t|.
finset_one_inclusion_pairs_mono- If 𝒜 ⊆ ℬ, then the one-inclusion pairs of 𝒜 form a subset of the one-inclusion pairs of ℬ.
finset_one_inclusion_pairs_inter- The intersection of the one-inclusion pairs of 𝒜 and of ℬ is a subset of the one-inclusion pairs of 𝒜 ∩ ℬ.
Finset.card_eq_zero- A finset has cardinality 0 if and only if it is empty.
Finset.subset_empty- A finset is a subset of the empty set if and only if it is empty.
Finset.subset_insert_iff_of_notMem- When an element a is not in s, s is a subset of insert a t if and only if s is a subset of t.
Finset.sup_le- The supremum of a finite set is at most a given upper bound if each element is at most that bound.
Finset.Shatters.card_le_vcDim- If a family shatters a set s, then |s| is at most the VC dimension of the family.
Finset.card_insert_of_notMem- Inserting an element not in s increases the cardinality of s by 1.
Finset.card_memberSubfamily_add_card_nonMemberSubfamily- The cardinality of the member subfamily plus that of the non-member subfamily with respect to an element equals the cardinality of the full family.
finset_one_inclusion_pairs_card_split- Splitting a family 𝒜 along an element a bounds its one-inclusion pairs by the pairs of the union, the pairs of the intersection, and twice the size of the intersection of its subfamilies.
finset_one_inclusion_pairs_card_le- If every set in 𝒜 is a subset of a finite universe u and 𝒜 has VC dimension at most d, then 𝒜 has at most 2 * (d * |𝒜|) one-inclusion pairs.
Finset.le_sup- Any element of a finset is less than or equal to the supremum of the finset under a function.
Finset.card_bij- A bijection between two finsets proves they have the same cardinality.
SimpleGraph.two_mul_card_edgeFinset- In a finite simple graph, twice the number of edges equals the number of ordered pairs of adjacent vertices.
Nat.le_of_mul_le_mul_left- If c * a ≤ c * b and c > 0, then a ≤ b for natural numbers.
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.
/-- Ordered pairs of members of `𝒜` whose symmetric difference has exactly one element. -/def finset_one_inclusion_pairs {α : Type*} [DecidableEq α] (𝒜 : Finset (Finset α)) : Finset (Finset α × Finset α) := (𝒜 ×ˢ 𝒜).filter (fun p => (symmDiff p.1 p.2).card = 1)theorem finset_one_inclusion_pairs_mono {α : Type*} [DecidableEq α] {𝒜 ℬ : Finset (Finset α)} (h : 𝒜 ⊆ ℬ) : finset_one_inclusion_pairs 𝒜 ⊆ finset_one_inclusion_pairs ℬ := Finset.filter_subset_filter _ (Finset.product_subset_product h h)theorem finset_one_inclusion_pairs_inter {α : Type*} [DecidableEq α] (𝒜 ℬ : Finset (Finset α)) : finset_one_inclusion_pairs 𝒜 ∩ finset_one_inclusion_pairs ℬ ⊆ finset_one_inclusion_pairs (𝒜 ∩ ℬ) := by intro p hp simp only [finset_one_inclusion_pairs, Finset.mem_inter, Finset.mem_filter, Finset.mem_product] at hp ⊢ exact ⟨⟨⟨hp.1.1.1, hp.2.1.1⟩, ⟨hp.1.1.2, hp.2.1.2⟩⟩, hp.1.2⟩theorem finset_one_inclusion_pairs_card_split {α : Type*} [DecidableEq α] (a : α) (𝒜 : Finset (Finset α)) : (finset_one_inclusion_pairs 𝒜).card ≤ (finset_one_inclusion_pairs (𝒜.nonMemberSubfamily a ∪ 𝒜.memberSubfamily a)).card + (finset_one_inclusion_pairs (𝒜.nonMemberSubfamily a ∩ 𝒜.memberSubfamily a)).card + 2 * (𝒜.nonMemberSubfamily a ∩ 𝒜.memberSubfamily a).card := by set F0 := 𝒜.nonMemberSubfamily a set F1 := 𝒜.memberSubfamily a set E := finset_one_inclusion_pairs 𝒜 set E00 := E.filter (fun p => a ∉ p.1 ∧ a ∉ p.2) set E11 := E.filter (fun p => a ∈ p.1 ∧ a ∈ p.2) set EX := E.filter (fun p => (a ∈ p.1 ∧ a ∉ p.2) ∨ (a ∉ p.1 ∧ a ∈ p.2)) have hsplit : E ⊆ E00 ∪ E11 ∪ EX := by intro p hp simp only [E00, E11, EX, Finset.mem_union, Finset.mem_filter] by_cases h1 : a ∈ p.1 <;> by_cases h2 : a ∈ p.2 <;> simp [h1, h2, hp] have hcardE : E.card ≤ E00.card + E11.card + EX.card := (Finset.card_le_card hsplit).trans ((Finset.card_union_le _ _).trans (Nat.add_le_add_right (Finset.card_union_le _ _) _)) -- E00 sits inside the pairs of F0 have h00 : E00 ⊆ finset_one_inclusion_pairs F0 := by intro p hp simp only [E00, E, finset_one_inclusion_pairs, Finset.mem_filter, Finset.mem_product] at hp ⊢ obtain ⟨⟨⟨hA, hB⟩, hP⟩, ha1, ha2⟩ := hp exact ⟨⟨Finset.mem_nonMemberSubfamily.2 ⟨hA, ha1⟩, Finset.mem_nonMemberSubfamily.2 ⟨hB, ha2⟩⟩, hP⟩ -- E11 injects into the pairs of F1 by erasing `a` have h11 : E11.card ≤ (finset_one_inclusion_pairs F1).card := by refine Finset.card_le_card_of_injOn (fun p => (p.1.erase a, p.2.erase a)) ?_ ?_ · intro p hp simp only [Finset.mem_coe, E11, E, finset_one_inclusion_pairs, Finset.mem_filter, Finset.mem_product] at hp ⊢ obtain ⟨⟨⟨hA, hB⟩, hP⟩, ha1, ha2⟩ := hp refine ⟨⟨Finset.mem_memberSubfamily.2 ⟨by rwa [Finset.insert_erase ha1], by simp⟩, Finset.mem_memberSubfamily.2 ⟨by rwa [Finset.insert_erase ha2], by simp⟩⟩, ?_⟩ have : symmDiff (p.1.erase a) (p.2.erase a) = symmDiff p.1 p.2 := by ext x by_cases hx : x = a · subst hx; simp [Finset.mem_symmDiff, ha1, ha2] · simp [Finset.mem_symmDiff, Finset.mem_erase, hx] rw [this]; exact hP · intro p hp q hq hpq simp only [Finset.mem_coe, E11, Finset.mem_filter] at hp hq simp only [Prod.mk.injEq] at hpq have e1 : p.1 = q.1 := by rw [← Finset.insert_erase hp.2.1, ← Finset.insert_erase hq.2.1, hpq.1] have e2 : p.2 = q.2 := by rw [← Finset.insert_erase hp.2.2, ← Finset.insert_erase hq.2.2, hpq.2] exact Prod.ext e1 e2 -- pairs differing exactly in `a` have hX : EX.card ≤ 2 * (F0 ∩ F1).card := by have hsd : ∀ p ∈ EX, symmDiff p.1 p.2 = {a} := by intro p hp simp only [EX, E, finset_one_inclusion_pairs, Finset.mem_filter] at hp obtain ⟨⟨-, hP⟩, hx⟩ := hp obtain ⟨x, hx1⟩ := Finset.card_eq_one.1 hP have : a ∈ symmDiff p.1 p.2 := by rw [Finset.mem_symmDiff]; tauto rw [hx1, Finset.mem_singleton] at this rw [hx1, this] have hcard2 : (F0 ∩ F1).card * 2 = ((F0 ∩ F1) ×ˢ (Finset.univ : Finset Bool)).card := by rw [Finset.card_product, Finset.card_univ, Fintype.card_bool] rw [mul_comm, hcard2] refine Finset.card_le_card_of_injOn (fun p => (p.1.erase a, decide (a ∈ p.1))) ?_ ?_ · intro p hp have hs := hsd p hp simp only [Finset.mem_coe, EX, E, finset_one_inclusion_pairs, Finset.mem_filter, Finset.mem_product] at hp obtain ⟨⟨⟨hA, hB⟩, -⟩, hx⟩ := hp have hiff : ∀ x, x ≠ a → (x ∈ p.1 ↔ x ∈ p.2) := by intro x hxa have : x ∉ symmDiff p.1 p.2 := by rw [hs]; simpa using hxa rw [Finset.mem_symmDiff] at this tauto simp only [Finset.mem_coe, Finset.mem_product, Finset.mem_univ, and_true, Finset.mem_inter, Finset.mem_nonMemberSubfamily, Finset.mem_memberSubfamily, F0, F1] rcases hx with ⟨ha1, ha2⟩ | ⟨ha1, ha2⟩ · have hBe : p.1.erase a = p.2 := by ext x by_cases hxa : x = a · subst hxa; simp [ha2] · rw [Finset.mem_erase]; exact ⟨fun h => (hiff x hxa).1 h.2, fun h => ⟨hxa, (hiff x hxa).2 h⟩⟩ refine ⟨⟨by rw [hBe]; exact hB, by simp⟩, by rwa [Finset.insert_erase ha1], by simp⟩ · have hAe : p.1.erase a = p.1 := Finset.erase_eq_of_notMem ha1 have hBi : insert a p.1 = p.2 := by ext x by_cases hxa : x = a · subst hxa; simp [ha2] · rw [Finset.mem_insert]; exact ⟨fun h => h.elim (fun e => absurd e hxa) (hiff x hxa).1, fun h => Or.inr ((hiff x hxa).2 h)⟩ rw [hAe] exact ⟨⟨hA, ha1⟩, by rw [hBi]; exact hB, ha1⟩ · intro p hp q hq hpq have hsp := hsd p hp have hsq := hsd q hq simp only [Prod.mk.injEq, decide_eq_decide] at hpq obtain ⟨he, hm⟩ := hpq have e1 : p.1 = q.1 := by by_cases ha : a ∈ p.1 · rw [← Finset.insert_erase ha, ← Finset.insert_erase (hm.1 ha), he] · rw [← Finset.erase_eq_of_notMem ha, ← Finset.erase_eq_of_notMem (fun h => ha (hm.2 h)), he] have e2 : p.2 = q.2 := by have h1 : p.2 = symmDiff p.1 {a} := by rw [← hsp, symmDiff_symmDiff_cancel_left] have h2 : q.2 = symmDiff q.1 {a} := by rw [← hsq, symmDiff_symmDiff_cancel_left] rw [h1, h2, e1] exact Prod.ext e1 e2 -- pairs of F0 and F1 against those of the union and the intersection have hUI : (finset_one_inclusion_pairs F0).card + (finset_one_inclusion_pairs F1).card ≤ (finset_one_inclusion_pairs (F0 ∪ F1)).card + (finset_one_inclusion_pairs (F0 ∩ F1)).card := by rw [← Finset.card_union_add_card_inter] exact Nat.add_le_add (Finset.card_le_card (Finset.union_subset (finset_one_inclusion_pairs_mono Finset.subset_union_left) (finset_one_inclusion_pairs_mono Finset.subset_union_right))) (Finset.card_le_card (finset_one_inclusion_pairs_inter F0 F1)) have := Finset.card_le_card h00 omegatheorem finset_one_inclusion_pairs_card_le {α : Type*} [DecidableEq α] (u : Finset α) : ∀ 𝒜 : Finset (Finset α), (∀ s ∈ 𝒜, s ⊆ u) → ∀ d : ℕ, 𝒜.vcDim ≤ d → (finset_one_inclusion_pairs 𝒜).card ≤ 2 * (d * 𝒜.card) := by induction u using Finset.induction with | empty => intro 𝒜 h𝒜 d _ have : (finset_one_inclusion_pairs 𝒜).card = 0 := by rw [Finset.card_eq_zero, finset_one_inclusion_pairs, Finset.filter_eq_empty_iff] intro p hp rw [Finset.mem_product] at hp rw [Finset.subset_empty.1 (h𝒜 _ hp.1), Finset.subset_empty.1 (h𝒜 _ hp.2)] simp omega | insert a u hau ih => intro 𝒜 h𝒜 d hd set F0 := 𝒜.nonMemberSubfamily a set F1 := 𝒜.memberSubfamily a have hF0 : ∀ s ∈ F0, s ⊆ u := by intro s hs rw [Finset.mem_nonMemberSubfamily] at hs exact (Finset.subset_insert_iff_of_notMem hs.2).1 (h𝒜 s hs.1) have hF1 : ∀ s ∈ F1, s ⊆ u := by intro s hs rw [Finset.mem_memberSubfamily] at hs exact (Finset.subset_insert_iff_of_notMem hs.2).1 ((Finset.subset_insert _ _).trans (h𝒜 _ hs.1)) have hU : ∀ s ∈ F0 ∪ F1, s ⊆ u := by intro s hs rcases Finset.mem_union.1 hs with h | h exacts [hF0 s h, hF1 s h] have hI : ∀ s ∈ F0 ∩ F1, s ⊆ u := fun s hs => hF0 s (Finset.mem_inter.1 hs).1 have notmem : ∀ ℬ : Finset (Finset α), (∀ s ∈ ℬ, s ⊆ u) → ∀ s, ℬ.Shatters s → a ∉ s := by intro ℬ hℬ s hs ha obtain ⟨v, hv, hsv⟩ := hs.exists_superset exact hau (hℬ v hv (hsv ha)) have shU : ∀ s, (F0 ∪ F1).Shatters s → 𝒜.Shatters s := by intro s hs t ht have has := notmem _ hU s hs obtain ⟨w, hw, hsw⟩ := hs ht rcases Finset.mem_union.1 hw with hw | hw · rw [Finset.mem_nonMemberSubfamily] at hw exact ⟨w, hw.1, hsw⟩ · rw [Finset.mem_memberSubfamily] at hw exact ⟨insert a w, hw.1, by rw [Finset.inter_insert_of_notMem has, hsw]⟩ have shI : ∀ s, (F0 ∩ F1).Shatters s → 𝒜.Shatters (insert a s) := by intro s hs t ht have has := notmem _ hI s hs by_cases hat : a ∈ t · have hsub : t.erase a ⊆ s := by intro x hx rw [Finset.mem_erase] at hx have := ht hx.2 rw [Finset.mem_insert] at this exact this.resolve_left hx.1 obtain ⟨w, hw, hsw⟩ := hs hsub have hw1 := (Finset.mem_inter.1 hw).2 rw [Finset.mem_memberSubfamily] at hw1 refine ⟨insert a w, hw1.1, ?_⟩ rw [← Finset.insert_inter_distrib, hsw, Finset.insert_erase hat] · have hsub : t ⊆ s := by intro x hx have := ht hx rw [Finset.mem_insert] at this exact this.resolve_left (fun e => hat (e ▸ hx)) obtain ⟨w, hw, hsw⟩ := hs hsub have hw0 := (Finset.mem_inter.1 hw).1 rw [Finset.mem_nonMemberSubfamily] at hw0 refine ⟨w, hw0.1, ?_⟩ rw [Finset.insert_inter_of_notMem hw0.2, hsw] have vcU : (F0 ∪ F1).vcDim ≤ d := by unfold Finset.vcDim refine Finset.sup_le fun s hs => ?_ exact ((shU s (Finset.mem_shatterer.1 hs)).card_le_vcDim).trans hd have vcI : (F0 ∩ F1).vcDim ≤ d - 1 := by unfold Finset.vcDim refine Finset.sup_le fun s hs => ?_ have hs' := Finset.mem_shatterer.1 hs have h1 := (shI s hs').card_le_vcDim rw [Finset.card_insert_of_notMem (notmem _ hI s hs')] at h1 omega have hIempty : d = 0 → F0 ∩ F1 = ∅ := by intro hd0 by_contra hne have h1 := (shI ∅ (Finset.shatters_empty.2 (Finset.nonempty_iff_ne_empty.2 hne))).card_le_vcDim simp only [insert_empty_eq, Finset.card_singleton] at h1 omega have ihU := ih (F0 ∪ F1) hU d vcU have ihI := ih (F0 ∩ F1) hI (d - 1) vcI have hcard : 𝒜.card = (F0 ∪ F1).card + (F0 ∩ F1).card := by rw [Finset.card_union_add_card_inter, add_comm, Finset.card_memberSubfamily_add_card_nonMemberSubfamily] have hedge : (finset_one_inclusion_pairs 𝒜).card ≤ (finset_one_inclusion_pairs (F0 ∪ F1)).card + (finset_one_inclusion_pairs (F0 ∩ F1)).card + 2 * (F0 ∩ F1).card := finset_one_inclusion_pairs_card_split a 𝒜 rcases Nat.eq_zero_or_pos d with hd0 | hdpos · have hI0 := hIempty hd0 subst hd0 rw [hI0] at hedge have h0 : (finset_one_inclusion_pairs (∅ : Finset (Finset α))).card = 0 := by simp [finset_one_inclusion_pairs] rw [h0, Finset.card_empty] at hedge simp only [zero_mul, mul_zero] at ihU ⊢ omega · have h1 : d * 𝒜.card = d * (F0 ∪ F1).card + d * (F0 ∩ F1).card := by rw [hcard, mul_add] have h2 : (d - 1) * (F0 ∩ F1).card + (F0 ∩ F1).card = d * (F0 ∩ F1).card := by obtain ⟨k, rfl⟩ := Nat.exists_eq_add_of_lt hdpos simp only [Nat.zero_add, Nat.add_sub_cancel] ring linariththeorem finset_one_inclusion_graph_card_edgeFinset_le {α : Type*} [DecidableEq α] (𝓕 : Finset (Finset α)) [Fintype (finset_one_inclusion_graph 𝓕).edgeSet] (d : ℕ) (hd : 𝓕.vcDim ≤ d) : (finset_one_inclusion_graph 𝓕).edgeFinset.card ≤ d * 𝓕.card := by classical have hpairs := finset_one_inclusion_pairs_card_le (𝓕.sup id) 𝓕 (fun s hs => Finset.le_sup (f := id) hs) d hd have hbij : ((Finset.univ : Finset (𝓕 × 𝓕)).filter (fun x => (finset_one_inclusion_graph 𝓕).Adj x.1 x.2)).card = (finset_one_inclusion_pairs 𝓕).card := by apply Finset.card_bij (fun x _ => ((x.1 : Finset α), (x.2 : Finset α))) · intro x hx simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hx simp only [finset_one_inclusion_pairs, Finset.mem_filter, Finset.mem_product] exact ⟨⟨x.1.2, x.2.2⟩, hx⟩ · intro x _ y _ h simp only [Prod.mk.injEq] at h exact Prod.ext (Subtype.ext h.1) (Subtype.ext h.2) · intro b hb simp only [finset_one_inclusion_pairs, Finset.mem_filter, Finset.mem_product] at hb refine ⟨(⟨b.1, hb.1.1⟩, ⟨b.2, hb.1.2⟩), ?_, rfl⟩ simp only [Finset.mem_filter, Finset.mem_univ, true_and] exact hb.2 have key : 2 * (finset_one_inclusion_graph 𝓕).edgeFinset.card = (finset_one_inclusion_pairs 𝓕).card := by rw [← hbij] convert SimpleGraph.two_mul_card_edgeFinset (finset_one_inclusion_graph 𝓕) have h2 : 2 * (finset_one_inclusion_graph 𝓕).edgeFinset.card ≤ 2 * (d * 𝓕.card) := by rw [key]; exact hpairs exact Nat.le_of_mul_le_mul_left h2 (by norm_num)