Documentation

Linglib.Core.Combinatorics.SetFamily.FourFunctions

Holley's inequality for upper sets #

[UPSTREAM] Holley's inequality, a two-weight form of the Fortuin–Kasteleyn–Ginibre inequality, compares weights f and g on a finite distributive lattice with f a * g b ≤ f (a ⊓ b) * g (a ⊔ b): then g puts relatively more weight on every upper set than f does. This file states it for an upper set, without normalizing the weights, as a corollary of the four functions theorem.

References #

theorem holley_isUpperSet {α : Type u_1} {β : Type u_2} [DistribLattice α] [Fintype α] [DecidableEq α] [CommSemiring β] [LinearOrder β] [IsStrictOrderedRing β] [ExistsAddOfLE β] {f g : α → β} {s : Finset α} (hf : 0 ≤ f) (hg : 0 ≤ g) (hs : IsUpperSet ↑s) (h : ∀ (a b : α), f a * g b ≤ f (a ⊓ b) * g (a ⊔ b)) :
(∑ a ∈ s, f a) * ∑ a : α, g a ≤ (∑ a : α, f a) * ∑ a ∈ s, g a