arxiv: 2604.27693 · v1 · submitted 2026-04-30 · 💻 cs.LO

Recognition: unknown

Order-invariant cluster first-order logic on graph classes of bounded degree

Fatemeh Ghasemi, Julien Grange

Pith reviewed 2026-05-07 05:31 UTC · model grok-4.3

classification 💻 cs.LO

keywords order-invariant logiccluster first-order logicbounded degree graphsexpressive powerfirst-order logicgraph classesorder invariancesimilarity preservation

0 comments

The pith

Order-invariant cluster first-order logic has the same expressive power as plain first-order logic on bounded-degree graph classes.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces cluster first-order logic, a restricted fragment of first-order logic created to isolate the effects of order invariance. Order-invariant formulas use an order symbol in their vocabulary but must yield the same truth value regardless of how the order is interpreted. The central result is that while order-invariant cluster first-order logic can define properties beyond plain first-order logic on arbitrary structures, the two logics coincide in expressive power when evaluated only on graph classes of bounded degree. This equivalence is obtained by explicitly building linear orders on the universes of similar structures so that the expanded structures remain similar. A sympathetic reader cares because the result clarifies exactly when and how the addition of an order can or cannot create new definable properties in the presence of degree bounds, which are a standard restriction in graph logic and database theory.

Core claim

The paper establishes that order-invariant cluster first-order logic is included in first-order logic on classes of graphs with bounded degree. This is shown by constructing linear orders on the universes such that, whenever two structures are similar, the structures obtained by expanding them with these orders remain similar. The construction proceeds from local similarities to a global order in a way that preserves the necessary indistinguishability relations.

What carries the argument

The local-to-global similarity-preserving construction of linear orders on bounded-degree structures.

If this is right

Any property definable by an order-invariant cluster first-order formula on a bounded-degree graph class is also definable by a plain first-order formula.
The similarity-preserving order construction succeeds precisely because the degree bound limits how far local distinctions can propagate.
The technique supplies a concrete method for proving that order invariance adds no expressive power on certain restricted classes.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same order-construction method could be tested on plain first-order logic to address the open question of whether order-invariant first-order logic equals first-order logic on bounded-degree graphs.
The result indicates that bounded degree prevents orders from revealing distinctions that locality would otherwise hide.
Similar local-to-global order constructions might apply to other graph parameters such as bounded expansion or nowhere dense classes.

Load-bearing premise

Linear orders can always be found on the universes of any two sufficiently similar bounded-degree structures so that the expanded structures remain similar.

What would settle it

A pair of bounded-degree graphs that are indistinguishable by first-order logic but become distinguishable after expansion by every possible linear order, or an explicit property that is definable by an order-invariant cluster first-order formula but not by any first-order formula on a bounded-degree class.

read the original abstract

We introduce a new logic, called \emph{cluster first-order logic}, a restricted fragment of first-order logic specifically designed to study order invariance. An order-invariant formula is one on a vocabulary that contains an order; however, whether a structure satisfies it or not is independent of the interpretation of the order. We show that while order-invariant cluster first-order logic can define properties outside the scope of plain first-order logic in general, its expressive power is included in that of first-order logic when it comes to classes of bounded degree. We establish this result by explicitly constructing linear orders such that similar structures remain similar when they are expanded with these orders. This similarity-preserving, local-to-global approach is technically involved and somewhat counterintuitive, since adding an order usually reveals distinctions that are otherwise hidden due to the locality of first-order logic. We believe that this work can be a stepping stone toward applying such techniques to plain first-order logic and toward settling the question of the expressive power of order-invariant plain first-order logic.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Cluster FO matches plain FO on bounded-degree graphs via an explicit similarity-preserving order construction.

read the letter

The main thing to know is that this paper defines cluster first-order logic and proves that its order-invariant version has exactly the same expressive power as ordinary first-order logic on any class of bounded-degree graphs. They do it with a direct construction of linear orders that keep similar structures similar after the expansion, moving from local to global while respecting the cluster syntax. This is the opposite of the usual locality story, where orders tend to expose distinctions that FO misses. The bounded-degree hypothesis is used to make the construction go through, and the argument stays non-circular by building the orders explicitly rather than assuming the conclusion. The new fragment itself is the clearest novelty; nothing like it appears in the cited literature, and the similarity-preserving device is a fresh technical move that could travel to other settings. The paper is upfront that the construction is involved and counterintuitive, which matches what one would expect for a local-to-global order lift. No load-bearing gaps or hidden assumptions jump out from the stated approach, and the result is presented as a stepping stone rather than a final answer for full FO. The main soft spot is that the details of the construction will need careful referee scrutiny to confirm the similarity relation survives the expansion in all cases, but the abstract gives no sign of a breakdown on bounded degree. This is for readers working in finite model theory, especially those tracking order invariance, locality, and definability on sparse graph classes. Someone following the open question about plain order-invariant FO will see a concrete technique worth thinking about. It shows honest engagement with the problem and the literature, so it deserves a serious referee even if the proof presentation needs tightening.

Referee Report

0 major / 3 minor

Summary. The paper introduces cluster first-order logic, a restricted fragment of first-order logic designed to study order invariance. It shows that order-invariant cluster FO can define properties outside plain FO in general, but that its expressive power is contained in that of plain FO on classes of bounded-degree graphs. The inclusion is established by an explicit construction of linear orders on the universes of similar structures such that the expanded structures remain similar, via a local-to-global similarity-preserving technique.

Significance. If the central construction holds, the result resolves the expressive-power question for this fragment on bounded-degree classes and supplies a concrete, constructive case in which order-invariance does not increase power. This is a useful stepping-stone toward the open problem for plain order-invariant FO. The explicitness of the order construction and the counter-intuitive local-to-global lifting are strengths that could support verification and extensions.

minor comments (3)

The abstract and introduction would benefit from a concise, self-contained definition or key syntactic restriction of cluster first-order logic before the main claims are stated.
A small concrete example of a property definable in order-invariant cluster FO but not in plain FO (outside bounded degree) would help readers contrast the general and bounded-degree regimes.
In the presentation of the local-to-global construction, a short roadmap or diagram indicating how local similarity is lifted would improve readability of the technically involved argument.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript and the recommendation for minor revision. The referee's summary accurately captures our introduction of cluster first-order logic and the main result that order-invariant cluster FO is contained in FO on bounded-degree graph classes. We are pleased that the referee recognizes the significance of the explicit similarity-preserving order construction as a potential stepping-stone toward the open question for plain order-invariant FO. Since the report lists no major comments, we have no specific points to address.

Circularity Check

0 steps flagged

No significant circularity: direct constructive proof

full rationale

The paper establishes its main result—that order-invariant cluster FO is no more expressive than plain FO on bounded-degree graph classes—via an explicit construction of linear orders on structure universes such that similar structures remain similar after expansion. This is described as a similarity-preserving local-to-global technique. No load-bearing steps reduce by definition, by fitting a parameter then relabeling it a prediction, or by a self-citation chain whose cited result itself depends on the target claim. The derivation is self-contained; the abstract presents the construction as the proof, with no equations or lemmas that equate the output to the input by construction. Minor self-citation (if any) is not load-bearing for the central inclusion result.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The central claim rests on (1) the newly introduced syntax and semantics of cluster first-order logic, (2) the standard locality theorem for first-order logic on bounded-degree structures, and (3) the existence of the similarity-preserving order expansions whose construction is the main technical work. No numerical parameters are fitted; the only invented object is the cluster fragment itself.

axioms (2)

standard math First-order logic is local on structures of bounded degree (Gaifman locality).
Invoked to argue that local similarity can be lifted to global similarity once suitable orders are chosen.
domain assumption Satisfaction of an order-invariant formula is independent of the concrete linear order chosen.
Definition of order-invariance used throughout.

invented entities (1)

Cluster first-order logic no independent evidence
purpose: A syntactically restricted fragment of first-order logic whose formulas are easier to analyze for order-invariance.
Newly defined in the paper; no independent evidence outside the paper is supplied.

pith-pipeline@v0.9.0 · 5472 in / 1615 out tokens · 54609 ms · 2026-05-07T05:31:33.081076+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

3 extracted references

[1]

In the following, we assume they chose (A,<A)– the case(B,<B)is defined analogously

Spoiler picks a structure(A,<A)and( B,<B). In the following, we assume they chose (A,<A)– the case(B,<B)is defined analogously. 2.Spoiler then makes either a(n)... ...introduction move (ifS=∅):Spoiler places pebblep 0 εon an element ofA. ...introduction move (ifS̸=∅): Spoiler choosesw∈Σ∗andα∈Σsuch that( w, 0)∈S and(wα,0)/∈S. Then they place pebblep0 wαon ...
[2]

x∈]a,b [

Then Duplicator answers by placing the corresponding pebble in the other structure. In the case of a(n)... ...introduction move (ifS=∅),Duplicator placesq 0 εon an element ofB. ...introduction move (ifS̸=∅),Duplicator placesq 0 wαon an element ofB. ...continuation move, Duplicator placesqi w on an element ofB that is adjacent toqj w. If such an element do...

2016
[3]

Thek-contextC k (A,<)(v)ofvin(A,<)is defined as Ck (A,<)(v) := ( (A,<)|N k A(v), g, f )

Let(A,< )|N k A(v) be the restriction of the ordered graph(A,< )to the k-neighbourhood of CVIT 2016 23:18 Order-invariant cluster first-order logic on graph classes of bounded degree vinA, let f: { Int(A,<)(Nk A(v))→P(CONTEXT k−1) ]a,b[↦→{C k−1 (A,<)(x) :x∈]a,b[} and g: { Nk A(v)→CONTEXT k−1 a↦→C k−1 (A,<)(a) . Thek-contextC k (A,<)(v)ofvin(A,<)is defined...

2016