finset_contains_trace
def
A set system F contains the set system H on the ground set {0,…,h−1} as a trace if there is an injection φ of the ground set of H into that of F such that every edge e of H equals A ∩ φ(V(H)) (transported by φ) for some A ∈ F. Distinct edges of H automatically get distinct witnesses A, since A ∩ Y determines e.
Statement
def finset_contains_trace {α : Type*} [DecidableEq α] {h : ℕ} (𝓕 : Finset (Finset α)) (𝓗 : Finset (Finset (Fin h))) : Prop
- Defined in
- arXiv:2610.08151 (Polynomial-in-r bounds for forbidden traces of uniform hypergraphs), Sec. 1.1 (containing F as a trace; an induced Berge copy). The ground set of H is Fin h; the distinctness of the witnesses H_e is implied by H_e ∩ Y = e and is not stated separately.
- Verified
- 11 Oct 2026
- Axioms
- none listed
- Used by 4
- not_finset_contains_trace_emptyThe empty set system contains no nonempty set system as a trace.
- finset_vc_dim_le_of_not_contains_traceLet H be a set system on an h-element ground set, h ≥ 1. If a finite set system F is trace-H-free, then VCdim(F) ≤ h − 1.
- finset_contains_trace_powerset_univThe full power set of {0,…,h−1} contains every set system on {0,…,h−1} as a trace.
- finset_contains_trace_of_subsetContaining H as a trace is monotone: if F ⊆ F' and F contains H as a trace, so does F'.
Lean source view module on GitHub
/-- `𝓕` contains the set system `𝓗` on `Fin h` as a trace: some embedding `φ` of `Fin h` and, for every edge `e` of `𝓗`, some `A ∈ 𝓕` with `A ∩ φ(Fin h) = φ(e)`. -/ def finset_contains_trace {α : Type*} [DecidableEq α] {h : ℕ} (𝓕 : Finset (Finset α)) (𝓗 : Finset (Finset (Fin h))) : Prop := ∃ φ : Fin h ↪ α, ∀ e ∈ 𝓗, ∃ A ∈ 𝓕, A ∩ Finset.univ.map φ = e.map φ