Ghasemi–Grange conjecture on order-invariant CFO
For every class of finite graphs of bounded degree and every order-invariant cluster first-order logic sentence , there exists a first-order sentence such that, for every graph , if and only if ; equivalently, order-invariant collapses to on every bounded-degree graph class.
References
- Order-Invariant CFO Contains Local-Order-Invariant FO — arXiv — Derek R. Aoki
Source: arXiv
Progress summary
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 collapses to 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 is contained in on every bounded-degree graph class.
- Theorem 4.1 derives fixed-parameter tractability for model checking order-invariant there.
- The paper says the bounded-degree hypothesis is essential, separating the unrestricted case using .
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.