English
There is no commutative fractional polymorphism for functions with the Max-Cut property under given symmetry and validity assumptions.
Русский
Существование коммутативного фракционного полиморфизма невозможно для функций с свойством Max-Cut при данных предположениях симметрии и допустимости.
LaTeX
$$$\\forall f, mcf : f.HasMaxCutProperty, \\forall ω, ω.IsValid, ω.IsSymmetric \\Rightarrow ¬f.AdmitsFractional ω$$$
Lean4
/-- The pigeonhole principle for finitely many pigeons counted by weight, strict inequality version:
if the total weight of a finite set of pigeons is greater than `n • b`, and they are sorted into
`n` pigeonholes, then for some pigeonhole, the total weight of the pigeons in this pigeonhole is
greater than `b`. -/
theorem exists_lt_sum_fiber_of_maps_to_of_nsmul_lt_sum (hf : ∀ a ∈ s, f a ∈ t) (hb : #t • b < ∑ x ∈ s, w x) :
∃ y ∈ t, b < ∑ x ∈ s with f x = y, w x :=
exists_lt_of_sum_lt <| by simpa only [sum_fiberwise_of_maps_to hf, sum_const]
