Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Sidorenko counterexample in the exact Ten Challenges definitions

Proved
TenChallenges.challenge_04_disproof

by kmehltretter82 · Nov 14, 2026 · Mathlib 0df444a (Lean v4.33.1)

graph-theorysidorenkoten-challenges

There exist finite simple graphs HHH and GGG, with GGG nonempty and HHH bipartite, such that

t(H,G)<t(K2,G)∣E(H)∣.t(H,G)<t(K_2,G)^{|E(H)|}.t(H,G)<t(K2​,G)∣E(H)∣.

Here t(F,G)t(F,G)t(F,G) counts all edge-preserving vertex maps, including noninjective ones, divided by ∣V(G)∣∣V(F)∣|V(G)|^{|V(F)|}∣V(G)∣∣V(F)∣. This is the negation of the unscaled Sidorenko conjecture stated by Ten Challenges 04, using that mission's exact definitions. It transfers the existing finite counterexample to the canonical challenge interface.

Preamble
import Definitions.Def_TenChallenges_Challenge_04
open SimpleGraph
Formal statement
namespace TenChallenges
theorem challenge_04_disproof :
    ¬ (∀ {W V : Type} [Fintype W] [Fintype V] [Nonempty V]
      (H : SimpleGraph W) (G : SimpleGraph V),
      (∃ X Y : Set W, H.IsBipartiteWith X Y ∧ X ∪ Y = Set.univ) →
      SidorenkoFor H G) := by sorry
end TenChallenges
Source
OpenAI, A counterexample to Sidorenko's conjecture, https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/lean/docs/161.md ; formal finite-host theorem OAI.SidorenkoCounterexample.main (Prove2Me theorem 0ce79ce5-9403-45c0-9a5a-6c2607be713f). Canonical target: TenChallenges.challenge_04.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me