Graph-theory open problems

Directed Sidorenko property for K₂-homomorphic bipartite

AX_directed_sidorenko_bipartite_homomorphism

Source: arXiv:2210.16971 — A note on directed analogues of the Sidorenko and forcing conjectures

Conjecture 1.4 · arXiv:2210.16971

arXiv Conjecture high confidence— first stated 2022-10-30
Authors: Jacob Fox, Zoe Himwich, Nitya Mani, Yunkun Zhou

Status ai-disproved high confidence

Disproved via OpenAI's counterexample to Sidorenko's conjecture: the 35-vertex bipartite graph, oriented from one side to the other, lacks the directed Sidorenko property.

Reviewer notes. Literature status before this model-generated claim: open. No paper resolving Conjecture 1.4 of arXiv:2210.16971 was found. The source paper itself shows that the directed Sidorenko property for bipartite oriented graphs is equivalent to an asymmetric undirected Sidorenko property, reducing the conjecture to an open undirected analogue rather than proving it. The two internal-corpus references (arXiv:2312.15333, Nguyen-Scott-Seymour) were verified to concern a different 'Conjecture 1.4' from a Fox-Sudakov induced-subgraph-density paper and are unrelated to the directed Sidorenko setting. Web searches revealed active interest in directed Sidorenko questions but no specific resolution of this conjecture.

Auto-reviewed 2026-10-07 with claude-opus-5-5 (manual match against the OpenAI catalogue; TeX sources read).

OpenAI manuscript collection ai-disproved

Why it applies. Orient every edge of the manuscript's graph $H$ from its 13 point vertices to its 22 triple vertices; the result $B$ maps to $\vec K_2$. By Theorem 1.5 of the source paper, $B$ has the directed Sidorenko property only if $H$ has the asymmetric Sidorenko property, which implies the ordinary one, as that paper notes. $H$ fails the ordinary property.

Family 161: Counterexamples to Sidorenko’s conjecture and the forcing conjecture · Lean formalization scope

These manuscripts were produced by an unreleased OpenAI model and released on 2026-10-06 in github.com/openai/math. They have not been peer reviewed. Lean formalizations are OpenAI's own and cover only the scope stated on their scope page; this project has not run or reviewed them. The status above records the claim; before it, the literature review rated this entry open. Its confidence rates whether the manuscript's theorem settles this entry, not whether the manuscript is correct.

Conjecture. If $B$ is a bipartite oriented graph with a homomorphism $B \to \vec{K}_2$, then $B$ has the directed Sidorenko property.

Context

Observation 3.1 establishes that having a homomorphism to a directed edge is a necessary condition for the directed Sidorenko property. The authors conjecture this condition is also sufficient for bipartite oriented graphs, giving a directed analogue of Sidorenko's conjecture.

Notes. PDF source.

Source paper

A note on directed analogues of the Sidorenko and forcing conjectures
Jacob Fox, Zoe Himwich, Nitya Mani, Yunkun Zhou · 2022-10-30
https://arxiv.org/abs/2210.16971 PDF source

Related conjectures

  • implied by Directed forcing characterization via homomorphism ai-disproved Any B with hom to K2vec is bipartite. If its underlying graph has a cycle, Conjecture 1.7 gives directed forcing, and directed forcing implies directed Sidorenko by the standard interpolation argument: if t(B,U)<q^{e(B)} for an oriented graphon of arc density q, mix U with a one-directional bipartite-block graphon of equal density with t(B)>q^{e(B)} (possible since B->K2vec and e(B)>=v(B)); IVT yields a non-quasirandom sequence with t(B) exactly q^{e(B)}, contradicting Definition 2.13 - the directed analogue of the classical fact that forcing graphs are Sidorenko (CFS10). If B is an oriented forest, Theorem 1.5 reduces directed Sidorenko to the asymmetric Sidorenko property, which holds for forests by Sidorenko's original functional (non-symmetric kernel) inequality for trees. Direction correct: forcing is the stronger conjecture.

View in the relation graph — relations are AI-reviewed, not formally verified.