Lemma 13, labeled form — over connected Veblen infragraphs
ProvedHararySachs.Hyper.lemma_13This is the labeled form of Lemma 13 of Clark and Cooper. It expresses the -th differential trace of a hypergraph as a weighted count of connected Veblen infragraphs.
Let , and , and let be a simple -graph, i.e. every edge is a -element subset of . Write for the -th trace of the normalized adjacency hypermatrix given by Equation (1) of the paper:
Here is an matrix of independent variables, is the -th coordinate of with replaced by , and the operator is applied to , keeping the constant term.
A labeled infragraph of with edges is a multiset of edges, each taken from and repetitions allowed. It is Veblen when every vertex degree is divisible by , and connected when and any two covered vertices are joined by a chain of edges of . Let be the associated coefficient of Definition 10, i.e. the sum of over the Euler rootings of . Then
This identity is the bridge between the algebraic trace in the resultant formula and the combinatorial Harary–Sachs expansion of Theorem 14. Inserting it into the Schur polynomial yields the labeled form of Theorem 14.
Formalization Note The paper states Lemma 13 as over isomorphism classes. For a connected , Definition 11 makes the number of labeled copies of in , so the class-weighted sum equals the labeled sum used here. That labeled sum is the first display of the paper's proof, a sum over Euler rootings of all labeled connected Veblen infragraphs. Infragraphs are the elements of allMultisets E d, and is assocCoeff S, which equals connectedCoeff S for connected . The trace is the mission definition Tr.
import Mathlib import Definitions.Def_HararySachs_Hyper_Operators import Definitions.Def_HararySachs_Hyper_Veblen
namespace HararySachs.Hyper
open Classical
theorem lemma_13 (n k d : ℕ) (hk : 2 ≤ k) (hn : 1 ≤ n)
(E : Finset (Finset (Fin n))) (hE : ∀ e ∈ E, e.card = k)
(hd : 1 ≤ d) :
Tr (k := k) E d =
(d : ℚ) * ((k : ℚ) - 1) ^ n *
∑ S ∈ (allMultisets E d).filter (fun S => IsVeblen S k ∧ IsConnected S),
assocCoeff S := by sorry
end HararySachs.Hyper