Graph-theory open problems

Directed forcing characterization via homomorphism

AX_directed_sidorenko_forcing_cycle_homomorphism

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

Conjecture 1.7 · 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 the forcing conjecture: the same 35-vertex bipartite graph, oriented from one side to the other, has a cycle and a homomorphism to an edge but lacks the directed forcing property.

Reviewer notes. Literature status before this model-generated claim: open. Conjecture 1.7 from arXiv:2210.16971 posits that admitting a homomorphism to a directed edge and having a cycle in the underlying undirected graph are together sufficient for an oriented graph to have the directed forcing property — a directed analogue of the Skokan–Thoma forcing conjecture. The source paper (published in Electronic Journal of Combinatorics) proves these two conditions are necessary (Theorem 1.6) but the conjectured sufficiency remains open. A wide web search covering related work on directed Sidorenko and forcing properties found no follow-up paper resolving the conjecture as of May 2026.

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. The manuscript's forcing corollary gives $p \in (0,1)$ and a nonconstant symmetric graphon $W$ with $t(K_2,W) = p$ and $t(H,W) = p^{66}$. Read as a bipartite graphon, $W$ shows that $H$, with its point/triple bipartition, lacks the asymmetric forcing property. By Theorem 1.8 of the source paper, $H$ oriented from points to triples then lacks the directed forcing property.

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

Caveat. The forcing corollary lies outside the family's Lean formalization, which covers only the Sidorenko counterexample.

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 an oriented graph with a homomorphism to an edge and whose underlying undirected graph has a cycle, then $B$ has the directed forcing property.

Context

Theorem 1.6 establishes that admitting a homomorphism to a directed edge and having a cycle in the underlying undirected graph are both necessary conditions for the directed forcing property. The authors conjecture these two conditions together are also sufficient, providing a directed analogue of the Skokan–Thoma forcing 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

  • implies Directed Sidorenko property for K₂-homomorphic bipartite 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.