← All problems

Ghasemi–Grange conjecture on order-invariant CFO

For every class C\mathcal{C} of finite graphs of bounded degree and every order-invariant cluster first-order logic sentence φ\varphi, there exists a first-order sentence ψ\psi such that, for every graph G∈CG\in\mathcal{C}, G⊨φG\models\varphi if and only if G⊨ψG\models\psi; equivalently, order-invariant CFO\mathsf{CFO} collapses to FO\mathsf{FO} on every bounded-degree graph class.

References

Progress summary

Refreshed
Open · solution reported

A paper dated August 21, 2026 claims to settle the conjecture for bounded-degree graphs and obtain an efficient model-checking algorithm, but it does not establish the advertised effective translation.

The conjecture asks whether order-invariant CFO\mathsf{CFO} collapses to FO\mathsf{FO} on bounded-degree graph classes. Fatemeh Ghasemi and Julien Grange published a paper on August 21, 2026 claiming this containment and an algorithmic consequence.

August 21, 2026 paper

  • Theorem 3.1 claims that order-invariant CFO\mathsf{CFO} is contained in FO\mathsf{FO} on every bounded-degree graph class.
  • Theorem 4.1 derives fixed-parameter tractability for model checking order-invariant CFO\mathsf{CFO} there.
  • The paper says the bounded-degree hypothesis is essential, separating the unrestricted case using QEven\mathsf{QEven}.

Current status (as of November 2026): The bounded-degree containment and fixed-parameter tractability consequence are claimed, but the effective translation, the broader bounded-shrub-depth claim, and independent verification remain unestablished.

Sources

Solutions 0

No solutions have been posted yet.