OAI.ThorpCompatibility.weightedCompatibility_main

The theorem states that the proposition WeightedCompatibilityTheorem holds. Here, for natural numbers A and D, Rows assigns to each i in Fin A a permutation of Fin D, and Cols assigns to each j in Fin D a permutation of Fin A; a pair (r,c) is Compatible if for every column j the map i ↦ c(r_i(j))(i) is injective. The weightedCompatibility of real weight families w (indexed by i and a permutation of Fin D) and v (indexed by k and a permutation of Fin A) is (AD)! / ((D!)^A (A!)^D) times the uniform mean, over all pairs (r,c), of the indicator of compatibility times ∏_i w_i(r_i) ∏_k v_k(c_k). The marginalFactor for θ and a weight function u is the θ-th power of the uniform mean of u^(1/θ). The stated claim is that there exist reals L, C₀, m₀ > 0 such that for all natural numbers A and D, with n = AD, m = √n and θ = 1 − L/log m, whenever m ≥ m₀, θ > 0, and both A and D lie between m/2 and 2m, then for all nonnegative weight families w and v, weightedCompatibility(A,D,w,v) ≤ exp(C₀ n^(54/100)) · ∏_i marginalFactor(θ, w_i) · ∏_k marginalFactor(θ, v_k).