ProofAtlas

Extremal graph theory and graph homomorphism inequalities

Sidorenko’s Conjecture

Collaboration beta

A random-like graph is conjectured to minimize the density of every fixed bipartite pattern among graphs with the same edge density. Many graph families and kernel classes are known, but the universal inequality is still open.

tH(W)≥p|E(H)|,p=∫W
Known results and sources
A finite bipartite graph suspended over a nonnegative kernel heatmap, with a balanced homomorphism-density scale left visibly unresolved.
Sidorenko's conjecture compares every bipartite pattern density with the random-density baseline; the full inequality remains open.

Research problem

Exact mathematical statement

For every finite simple bipartite graph H=(A,B,E) with m edges and every measurable nonnegative kernel W on probability spaces, the homomorphism density satisfies t_H(W) >= p^m, where p is the integral of W.

tH(W)≥p|E(H)|,p=∫Wt_H(W)\ge p^{|E(H)|},\qquad p=\int W

Problem infographic

Problem at a glance

A bipartite graph, finite kernel matrix, entropy-lifting map, and radial covariance path arranged as separate established and open components.
Finite-witness and entropy reductions make the full problem finite-dimensional, but uniform control of the radial covariance defect is still missing.

Current mathematical picture

Where work on Sidorenko’s Conjecture stands

Open conjecture

Selected route highlights from the mathematical source. This is not yet a complete mathematical inventory.

Useful failureSource-reported closed or invalid route

Differential edge-deletion induction is false even for P4, with an exact finite counterexample in the source. Compute and control the finite endpoint curvature K_1 and then bound the positive part of the radial covariance defect uniformly over finite alphabets; alternatively construct average-edge lifts with O_H(1) entropy overhead.

Route status · Narrowed route
Main reductionBounded Overhead

A uniform additive entropy overhead is removed by tensor amplification.

Evidence posture · Source-reported route statement · dependencies incomplete
Priority open bridgeCompute the finite endpoint curvature K_1 explicitly.Task status · Ready to work on
Research-record correctionResearch-record correction

We corrected the cited passages. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Reader-facing record corrected; mathematics unchanged

Work mapped so far

Sidorenko’s Conjecture in numbers

2.1kretained lines of mathematical investigation2,111 in the current working snapshot
Argument development
1,677 · 79%
Explored or eliminated routes
131 · 6%
Computational analysis
51 · 2%
Open obligations
94 · 4%
Definitions and setup
158 · 7%
7selected mapped statements2routes investigated5open questions5contribution-ready tasks
How this is measured

This measures retained mathematical investigation, not proximity to a proof. Code, data, logs, repeated text, operational instructions, and generated presentation copy are excluded.

Proposed byAlexander F. SidorenkoStatus checkedAug 15, 2026
Source recordedAug 15, 2026

Argument map and routes

How the current approaches connect

Claims, reductions, open questions, active routes, and narrowed alternatives in one mathematical map.

Visible working map

Research route map

14 selected steps

Selected claims, active routes, useful failures, and open questions from the current research map. Arrows appear only for explicitly recorded relationships.

14 selected steps

Scroll horizontally to explore the route

Working route overview for Sidorenko’s ConjectureA selected map of recorded claims, active routes, useful failures, open questions, and their explicit relationships. Search, filter, zoom, or pan within this page.For every finite simple bipartite graph H=(A,B,E) with m edges and every measurable nonnegative kernel W on probability spaces, the homomorphism density satisfies t_H(W) >= p^m, where p is the integral of W. — Depends on missing premiseFor every finite simplebipartite graph H=(A,B,E)with…Bounded Overhead — Depends on missing premiseBounded OverheadCurrent reduction — Depends on missing premiseCurrent reductionEntropy Equivalence — Depends on missing premiseEntropy EquivalenceFinite Witness — Depends on missing premiseFinite WitnessClosing target — Depends on missing premiseClosing targetControlled Class — Depends on missing premiseControlled ClassSource-reported closed or invalid route — stoppedSource-reported closed orinvalid routeSecond source-reported limitation — stoppedSecond source-reportedlimitationCompute the finite endpoint curvature K_1 explicitly. — OpenCompute the finite endpointcurvature K_1 explicitly.Control the positive radial covariance defect uniformly. — OpenControl the positive radialcovariance defect uniformly.Classify one-edge-saturated finite KKT supports. — OpenClassify one-edge-saturatedfinite KKT supports.Exact Conjecture — OpenExact ConjectureFull Bridge Open — OpenFull Bridge Open
Working claimActive routeOpen, active, or blocked questionUseful failure

Working overview, not proof. The map shows selected recorded relationships; more nodes or edges do not establish correctness or completion.

Explored alternatives

Other routes

2 recorded
Narrowed routeSource-reported closed or invalid route

Differential edge-deletion induction is false even for P4, with an exact finite counterexample in the source. Compute and control the finite endpoint curvature K_1 and then bound the positive part of the radial covariance defect uniformly over finite alphabets; alternatively construct average-edge lifts with O_H(1) entropy overhead.

Route status · Narrowed route
Narrowed routeSecond source-reported limitation

Unrestricted monotonicity under adding a missing edge is also false; any viable edge-exposure method needs a global potential or extra hypothesis. Compute and control the finite endpoint curvature K_1 and then bound the positive part of the radial covariance defect uniformly over finite alphabets; alternatively construct average-edge lifts with O_H(1) entropy overhead.

Route status · Narrowed route

More ways to contribute

Open questions

Additional prepared tasks for exploring this research frontier.

5 featured tasks
01
Compute the finite endpoint curvature K_1 explicitly.Suggested move: Differentiate the scaled moment system to second order and express K_1 as a finite Schur complement respecting support and one-defect data.
Ready to work on
02
Control the positive radial covariance defect uniformly.Suggested move: Prove K_t <= 0, an alphabet-independent weighted positive-part bound, or an o(n) tensor-power analogue.
Ready to work on
03
Exact Conjecture

The conjecture requires t_H(W) at least p^m for every bipartite H and every nonnegative W.

Suggested move: Resolve the exact source-reported obligation without treating it as an established negative result.
Ready to work on
04
Full Bridge Open

The full arbitrary-kernel bridge remains unresolved despite exact finite and target-specific progress.

Suggested move: Resolve the exact source-reported obligation without treating it as an established negative result.
Ready to work on
05
Classify one-edge-saturated finite KKT supports.Suggested move: Combine saturation, KKT slack, Gibbs fixed point, Hessian inequalities, endpoint identities, and curvature moments in a symbolic structural classification.
Ready to work on

Sourced mathematical context

The known mathematical landscape

Context collected Aug 15, 2026
Current statusOpen conjecture

Peer-reviewed sources in 2024 and 2026 continue to state the graph conjecture as open while extending the classes of bipartite graphs known to satisfy it. Hypergraph counterexamples concern an analogue, not the graph conjecture itself.

[3][4]
External progress

What the literature has established

Selected external milestones in reverse chronological order, with their evidence posture.

  1. Peer reviewedA peer-reviewed 2026 paper proved new subdivision and generalized-theta substitution families while describing the full conjecture as still not completely understood.[3]
  2. Historical sourceThe correlation-inequality paper stated the bipartite graph integral conjecture in a directly recognizable form.[2]
  3. Historical sourceSidorenko developed inequalities for bipartite-graph functionals in the foundational source.[1]
4 cited sources1 related results or reductionsReferences

Mathematical neighborhood

Related results and reusable starting points

Current focusSidorenko's Conjecture
Related problemKNRS conjecture

The 2026 paper uses locally dense/KNRS results to derive new Sidorenko graph families; this does not make the two conjectures identical.

[3]

Formalization opportunities

Lean work can make these reusable foundations precise without being presented as a proof of the core problem.

  • Formalization targetNo complete proof or graph counterexample was identified in the bounded current primary-source review.
  • Formalization targetPacket-local finite certificates and standard inputs require their stated independent audits before any stronger evidence posture.

Research-record corrections

What changed in the research record

These notes describe corrections to cited passages, highlighted tasks, or connections between claims. The mathematical claims and their status did not change.

Research-record correctionWe corrected the cited passages. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Correction details
Research-record correctionWe corrected the cited passages. We removed a duplicate or outdated task or route step. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Correction details

The initial argument structure appears separately. Uploads, model runs, and presentation changes do not count as mathematical updates.

Detailed research inventory

Claims, milestones, and routes in the current map

This view highlights the mathematical statements most useful for following the current route.

5 standing statements2 proposed statements5 open questions2 narrowed routes
Statements by mathematical role7 selected mapped statements
  • theorem candidate1 of 71
  • reduction3 of 73
  • lemma2 of 72
  • equivalence1 of 71
Selected mathematical clusters1 mathematical clusters
Current research mapThe conjecture, retained reductions, explored limitations, and open questions represented in this overview.23 displayed rows · 2 routes included
  • retained route statementFor every finite simple bipartite graph H=(A,B,E) with m edges and every measurable nonnegative kernel W on probability spaces, the homomorphism density satisfies t_H(W) >= p^m, where p is the integral of W.
  • retained route statementCurrent reductionintermediate
  • retained route statementClosing targetintermediate
  • retained route statementFinite Witnessintermediate
  • retained route statementEntropy Equivalenceintermediate
  • retained route statementBounded Overheadintermediate
  • retained route statementControlled Classintermediate
  • Recorded relationshipThe source reports this as a route toward the conjecture; missing or unaudited premises remain and the reduction does not itself prove the target.supports · reported by source
  • Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
  • Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
  • Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
  • Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
  • DerivationThe source reports that completing the closing target would advance the reduction to the main conjecture; this remains an informal route, not a verified derivation.proposed
  • Useful failureSource-reported closed or invalid routereported failure
  • Useful failureSecond source-reported limitationreported failure
  • Research targetCompute the finite endpoint curvature K_1 explicitly.open
  • Research targetControl the positive radial covariance defect uniformly.open
  • Research targetClassify one-edge-saturated finite KKT supports.open
  • Research targetExact Conjectureopen
  • Research targetFull Bridge Openopen
  • ComputationThe source reports exact finite certificates for selected three-state ranks and counterexamples to several universal routes; ProofAtlas did not execute any attachment or verifier.These source-reported finite results constrain target-specific programs only and are not formal verification or a proof of the arbitrary-kernel conjecture. · reported unreproduced
  • Narrowed routeSource-reported closed or invalid routeDifferential edge-deletion induction is false even for P4, with an exact finite counterexample in the source. Compute and control the finite endpoint curvature K_1 and then bound the positive part of the radial covariance defect uniformly over finite alphabets; alternatively construct average-edge lifts with O_H(1) entropy overhead.
  • Narrowed routeSecond source-reported limitationUnrestricted monotonicity under adding a missing edge is also false; any viable edge-exposure method needs a global potential or extra hypothesis. Compute and control the finite endpoint curvature K_1 and then bound the positive part of the radial covariance defect uniformly over finite alphabets; alternatively construct average-edge lifts with O_H(1) entropy overhead.
How to interpret these counts

A statement may be a lemma, conditional reduction, special case, documented limitation, or open target. These counts describe the work's structure; they do not estimate distance to a proof.

Research outlook

Conditions that would advance the current route

Priority open bridgeCompute the finite endpoint curvature K_1 explicitly.

2 approaches have already been tested and narrowed. The task above is the current priority within the larger open route.

Evidence needed nextConcrete conditions for progress

A result can change the outlook by closing the bridge, narrowing its scope, or showing that the route cannot work.

  • Supply a complete argument with every imported premise identified.
  • Survive an independent attempt to falsify the proposed step.

Continue the mathematics

Contribute

ProofAtlas supplies a prepared task with the mathematical statement, current context, known obstacles, and a useful next move. Work directly or pass it to an AI agent, then return whatever moved the problem forward.

Read-only beta · actions unavailable
Prepared starting pointCompute the finite endpoint curvature K_1 explicitly.

Sidorenko’s Conjecture · ready to start

Mathematical updatesFollow this problem

Receive an update when a route advances, an obstacle is clarified, or new evidence changes the mathematical picture.

Research contextPrepared context for any AI agent

A random-like graph is conjectured to minimize the density of every fixed bipartite pattern among graphs with the same edge density. Many graph families and kernel classes are known, but the universal inequality is still open.

  • Exact question and boundaries
  • Current routes and known obstacles
  • What a useful result should report
Return mathematical workReturn what you or your agent found

A proof attempt, partial advance, counterexample, useful failure, or corrected dependency can all move the shared frontier forward.

Proof attempt or partial resultSupporting notes or data
Hosted agentRun this task with a hosted agent

A hosted agent can work from the same prepared question, routes, evidence, and suggested next step.

Your own AI agentConnect an outside research agent

Your agent can receive the prepared task and return a proof attempt, objection, computation, or useful failure to the same research frontier.

Sources and references4 cited works · next context review by Nov 15, 2026

The mathematical context was checked on Aug 15, 2026. Status can be refreshed sooner after a material result or claim.

  1. 1
    Inequalities for functionals generated by bipartite graphsoriginal source · A. F. Sidorenko · Diskretnaya Matematika / Discrete Mathematics and Applications · 1991 · DOI 10.1515/dma.1992.2.5.489 · MR MR1138091 · accessed Aug 15, 2026
  2. 2
    A correlation inequality for bipartite graphsoriginal source · Alexander Sidorenko · Graphs and Combinatorics · 1993-08-11 · DOI 10.1007/BF02988307 · MR MR1225933 · accessed Aug 15, 2026
  3. 3
    Sidorenko's conjecture for subdivisions and theta substitutionspeer reviewed result · Combinatorics, Probability and Computing · 2026-03 · DOI 10.1017/S0963548325100242 · accessed Aug 15, 2026
  4. 4
    Extremal Numbers and Sidorenko's Conjecturepeer reviewed result · Alexander Sidorenko · International Mathematics Research Notices · 2024-04-24 · DOI 10.1093/imrn/rnae071 · accessed Aug 15, 2026

Important qualifications

  • This was a bounded current-status check, not an exhaustive priority or attribution review.
  • Preprints remain labeled as preprints and were not upgraded to peer-reviewed posture.
  • Current open status was cross-checked against recent official or primary sources where available.
  • No source-package attachment was executed or rendered, and no URL copied from a submitted packet was fetched.
  • Metadata has no proof, review, acceptance, credit, publication, or deployment effect.

Continue exploring

Compare another research frontier

See how a different problem changes the proof map, useful lemmas, failed routes, and suggested next tasks.

Explore all research workspaces

Expanded visual

Open original image