Sidorenko counterexample in the exact Ten Challenges definitions
ProvedTenChallenges.challenge_04_disproofgraph-theorysidorenkoten-challenges
There exist finite simple graphs and , with nonempty and bipartite, such that
Here counts all edge-preserving vertex maps, including noninjective ones, divided by . 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 TenChallengesSource
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.