max_claw_packing
def
For a simple graph G on a finite type V, max_claw_packing G is defined as the supremum of Finset.card P over all P : Finset (Finset V) in Finset.univ satisfying is_claw_packing G P.
Statement
noncomputable def max_claw_packing {V : Type*} [Fintype V] (G : SimpleGraph V) : ℕ
- Defined in
- arXiv:2511.19585
- Verified
- 01 Nov 2026
- Axioms
- none listed
- Built on 1
- is_claw_packingFor a simple graph G on type V and a finite set of finite vertex subsets P : Finset (Finset V), is_claw_packing G P asserts that every s…
- Used by 1
- chain_trees_extensive_mmi_gap_of_exact_claw_packingsFor any integer k ≥ 1, if max_claw_packing (chain_tree_1 k) = 5 * k / 2 in ℕ (using integer division) and max_claw_packing (chain_tree_2…
Read back from the Lean
For a finite type V and a simple graph G on V, max_claw_packing G is defined as the maximum cardinality of a family P of finite subsets of V such that:
1. Every subset s ∈ P induces a subgraph of G that is isomorphic to the complete bipartite graph $K_{1,3}$ (with parts Fin 1 and Fin 3), and
2. The subsets in P are pairwise disjoint.
(If no such family has positive size, it evaluates to 0 via the empty family).
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 maximum number of pairwise vertex-disjoint induced claws in a finite graph. -/ noncomputable def max_claw_packing {V : Type*} [Fintype V] (G : SimpleGraph V) : ℕ := by classical exact Finset.sup (Finset.filter (is_claw_packing G) Finset.univ) Finset.card