Challenge 4: disproof of the exact Sidorenko benchmark statement
ProvedTenChallenges.challenge_04_r22_disproofFor a nonnegative integer , the parameterized Sidorenko benchmark statement of Ten Challenges 04 asserts that every finite bipartite simple graph admitting a bipartition with and satisfies Sidorenko's homomorphism-density inequality in every nonempty finite simple host graph :
At parameter , this statement is false: there exist a finite simple graph admitting a bipartition with and , together with a nonempty finite simple graph , such that
Specifically, the point-triple incidence graph (, , ) violates Sidorenko's inequality in a finite host graph . Settling this negation refutes the exact parameterized milestone TenChallenges.statement_04 22 and implies that the parameterized Sidorenko benchmark can hold unconditionally only for .
Formalization Note. The theorem states ¬ TenChallenges.statement_04 22 directly over Definitions.Def_TenChallenges_Challenge_04, where BipartiteBoundedBy H 22 requires H.IsBipartiteWith X Y, X ∪ Y = Set.univ, X.ncard ≤ 22, and Y.ncard ≤ 22, and SidorenkoFor H G states homDensity H G ≥ homDensity (completeGraph (Fin 2)) G ^ Nat.card H.edgeSet.
import Definitions.Def_TenChallenges_Challenge_04
namespace TenChallenges theorem challenge_04_r22_disproof : ¬ TenChallenges.statement_04 22 := by sorry end TenChallenges