{"id":"f24c8477-cc37-4135-b003-fe7307c05818","arxiv_id":"2502.02090","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Chains of quasi Jónsson operations imply bounded width and polynomial-time solvability for CSPs over first-order expansions of k-neoliberal structures with finite duality.","lead":"This paper proves that constraint satisfaction problems over many infinite relational structures are solvable in polynomial time when the structure is invariant under a chain of quasi Jónsson operations. It is the first purely algebraic tractability criterion of this kind for the infinite-domain setting, covering templates, such as multi-colored hypergraphs, that previously had no complexity classification.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 9 invokes Observation 16, whose proof requires A to be a model-complete core, but neither Theorem 9 nor Corollary 10 states that hypothesis; k-neoliberality plus finite duality does not imply it (random graph), so the proof covers fewer templates than claimed.","rationale":"The central claim is novel and the proof structure is coherent, but the reader identified the exact place where the statement and proof diverge. I agree. My independent check of the random graph shows that the natural 'B is automatically a core' fix fails: R is within the class (2-neoliberal, finite duality) but is not a model-complete core. Therefore Observation 16 cannot be applied in the lemmas as written. This is load-bearing because idempotency on finite S is used in the induction and contradiction arguments of Lemmas 26, 28, 40, and 43, and without it the chain identities are not available pointwise. The issue is a fixable hypothesis mismatch rather than a collapse of the overall method; if the authors add model-completeness or prove the missing observation, the conditional acceptance is justified. I therefore keep the reader's CONDITIONAL verdict unchanged.","tokens_in":44060,"tokens_out":25397,"duration_ms":269621,"concrete_test":"Two-part check. (1) Verify that the random graph R is a 2-neoliberal finite-duality structure that is not a model-complete core, using the non-injective endomorphism onto an infinite clique; this shows the missing hypothesis is not implied by the theorem's assumptions. (2) Inspect Lemma 26 at the sentence 'by Observation 16, we may assume without loss of generality that all the operations ... are idempotent on S' and determine whether any earlier proposition or surrounding argument supplies the required local automorphisms without model-completeness. If not, the statement of Theorem 9 and Corollary 10 must be restricted to model-complete cores, or a core-free proof of Observation 16 must be supplied.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 9 passes through Lemmas 26, 28, 40, and 43, each of which assumes only that A is a first-order expansion of a k-neoliberal finite-duality B and then calls on Observation 16 to make a chain of quasi Jónsson operations idempotent on a chosen finite set S. Observation 16 is stated and proved only for an ω-categorical model-complete core; its proof uses the defining property of a model-complete core that every unary endomorphism agrees with an automorphism on any finite set. The hypotheses of Theorem 9 do not imply this. In particular, the random graph R is 2-neoliberal and has finite duality (forbid a loop), yet it is not a model-complete core: pick two nonadjacent vertices u and v and an infinite clique C disjoint from them; mapping u and v to one vertex of C and all other vertices injectively into C gives a graph endomorphism of R that is not injective, and hence it cannot agree with an automorphism on {u, v}. Thus the central proof step 'by Observation 16, we may assume idempotency on S' is unjustified under the stated hypotheses. The gap is not cosmetic: idempotency on the finite configuration S is exactly what lets the chain identities be applied pointwise in the contradiction arguments of Lemmas 26, 28, 40, and 43. The theorem may be salvageable by adding 'model-complete core' to the statement or by proving a version of Observation 16 for first-order expansions of k-neoliberal finite-duality structures that admit a quasi Jónsson chain, but neither is present.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies infinite-domain constraint satisfaction problems over first-order expansions of k-neoliberal, finitely bounded homogeneous structures with finite duality. Its central claims are Theorem 9 and Corollary 10: if such an expansion A is invariant under a chain of quasi Jónsson operations, then A is implicationally simple on injective instances, has relational width (k, max(k+1, b_B)), and hence CSP(A) is in P. The proof proceeds through lemmas showing that certain implications and critical relations cannot be preserved by quasi Jónsson chains, and through a reduction from CSP(A) to CSPInj(A). The paper also discusses examples, including structures for which no complexity classification is known, and positions the result as the first non-trivial purely algebraic height-1 Maltsev condition implying bounded width for this class.","tokens_in":44362,"tokens_out":13172,"duration_ms":141077,"significance":"If the central claims hold, the paper is a meaningful advance: it gives an explicit relational-width bound and tractability for a broad class of infinite-domain CSPs under a purely algebraic hypothesis, extending the finite-domain bounded-width theory beyond the quasi near-unanimity case. The proof is detailed, largely self-contained, and includes the omitted arguments in an appendix, and the examples cover natural multi-colored graph and hypergraph structures. However, the model-complete-core gap described below is load-bearing for the main theorem, so the significance is contingent on repairing that gap or explicitly restricting the statement.","major_comments":[{"comment":"Observation 16, whose proof in Appendix A uses that A is an ω-categorical model-complete core, is invoked at a load-bearing point in the proof of Theorem 9. Specifically, Lemma 26, Lemma 28, and Lemma 40 use Observation 16 to assume that a chain of quasi Jónsson operations is idempotent on a chosen finite set S; the pointwise equalities in the subsequent contradiction arguments rely on exactly this idempotency. But Theorem 9 and Corollary 10 do not assume that A is a model-complete core, and k-neoliberality plus finite duality does not imply it: the random graph is 2-neoliberal, has finite duality, and is not a model-complete core, since it has non-injective graph endomorphisms. Thus the proof, as written, covers fewer templates than the stated theorems. The theorems may be salvageable by adding a model-complete-core hypothesis, which is standard in the Bodirsky-Pinsker conjecture, or by proving an analogue of Observation 16 for first-order expansions of k-neoliberal finite-duality structures admitting a quasi Jónsson chain; neither is currently present in the manuscript.","section":"III.C and Appendix A"},{"comment":"The proof of Corollary 25 invokes Lemma 22 to pass from an essential polymorphism to a binary essential polymorphism, but Lemma 22 is stated for an ω-categorical countable model-complete core whose automorphism group has at most two orbits. The structure A of Corollary 25 is only assumed to be a first-order expansion of a k-neoliberal finite-duality structure B; the proof does not verify that A is a model-complete core, nor that its automorphism group has at most two orbits. Even if the model-complete-core assumption is added globally, the expansion by first-order definable relations can in principle reduce Aut(A) relative to Aut(B), so the orbit condition needs an explicit justification. As written, the reduction from CSP(A) to CSPInj(A) in Corollary 25 is not established, and this reduction is needed for the proof of Corollary 10.","section":"Appendix E (proof of Corollary 25)"}],"minor_comments":[{"comment":"There is a typo in Definition 11: 'boudnedness' should be 'boundedness'.","section":"Definition 11"},{"comment":"In the induction step of Claim 27, the displayed equation has subscript typos: 'an_1' and 'a1_1' should be 'an_ℓ' and 'a1_ℓ'; the same typo pattern appears in Claim 45 in the proof of Lemma 28.","section":"Lemma 26, Claim 27"},{"comment":"The first line of Lemma 28 contains a grammatical typo: 'an let B' should be 'and let B'.","section":"Lemma 28"},{"comment":"The proof of Observation 16 should explicitly state that the unary operations J_i(x,x,x) are all equal (or can be chosen equal) across i, and therefore a single automorphism can be used for the conjugation. If distinct automorphisms α_i were used, the chain identities would not automatically survive the conjugation.","section":"Appendix A"},{"comment":"The notation in Lemmas 46 and 49 is sometimes unclear: for example, 'projuρ = projvρ = E' and later 'ρB' appear without specifying whether the ambient structure is A or B; the intended meaning should be spelled out.","section":"Appendix L (Lemmas 46 and 49)"}],"recommendation":"major_revision","confidential_remarks":"The main issue is the unstated model-complete-core hypothesis in Theorem 9 and Corollary 10, and the similar missing hypothesis in the use of Lemma 22 in Corollary 25. Since model-complete cores are standard in the Bodirsky-Pinsker conjecture, the result is likely repairable by adding that assumption and making the orbit condition in the Corollary 25 proof explicit. I recommend major revision rather than rejection, but the authors should either strengthen the hypotheses or give a genuine proof of the idempotency step under the stated assumptions."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know this is a genuine result, not a routine transfer. The paper gives the first purely algebraic height 1 Maltsev condition—chains of quasi Jónsson operations—that provably implies bounded width for a substantial class of infinite-domain CSPs inside the Bodirsky-Pinsker framework. Prior infinite-domain tractability results under polymorphism conditions were either canonical pseudo-Siggers (which needs topology) or quasi near-unanimity (a direct finite-domain transfer). The proof here is genuinely different, going through implicational simplicity and critical relations, and it covers templates like multi-hypergraphs with more than two edge colors, where no complexity classification is known. That is a meaningful advance.\n\nThe soft spot is real and load-bearing. The proof of Theorem 9 invokes Observation 16 in Lemmas 26, 28, 40, and 43 to make the chain of quasi Jónsson operations idempotent on a finite set S. But Observation 16 is stated and proved only for ω-categorical model-complete cores; its proof uses the defining property that every endomorphism agrees with an automorphism on any finite set. Theorem 9 and Corollary 10 only assume B is k-neoliberal with finite duality and A is a first-order expansion of B. Those assumptions do not imply A is a model-complete core—the random graph is 2-neoliberal, has finite duality, and is not a model-complete core. So the step \"by Observation 16\" is unjustified under the stated hypotheses. This is not cosmetic: idempotency on S is exactly what lets the chain identities be applied pointwise in the contradiction arguments. The fix is likely simple—add \"model-complete core\" to the statement, which matches the Bodirsky-Pinsker setup used in the introduction, or prove a version of Observation 16 for these structures—but as written the proof covers fewer templates than claimed.\n\nI don't see other major problems. The paper leans on earlier work by the same group for Lemmas 22, 23, and Proposition 24, but those are independent theorems and the reliance is honest. I didn't verify every long lemma in the appendix, but the structure is clear and I found no other gap. The reader's conditional verdict is right, and the stress-test concern lands.\n\nBottom line: this deserves a serious referee. The central idea is sound and important; the flaw is a fixable scope problem, not a broken argument. Send it to review, and tell the authors to sort out the model-complete core hypothesis.","headline":"A real first: height 1 Maltsev conditions giving bounded width for infinite-domain CSPs, but the theorem as stated silently assumes model-complete cores, so the proof covers fewer templates than claimed.","tokens_in":44943,"tokens_out":5650,"would_cite":true,"duration_ms":54319,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q27","08A70","03C15"],"pacs":[],"model":"deepseek-v4-flash","headline":"Quasi Jónsson chains imply bounded width for infinite CSPs","keywords":["constraint satisfaction problem","bounded width","local consistency","chain of quasi Jónsson operations","homogeneous structures","finite duality","k-neoliberal","infinite-domain CSP"],"falsifier":"Construct a first-order expansion A of a k-neoliberal structure B with finite duality that is preserved by a chain of quasi Jónsson operations, and exhibit a non-trivial (k, max(k+1,b_B))-minimal instance of CSP(A) with no solution; Corollary 10 would then be false. More sharply, look for a directed cycle in the injective implication graph of such an A, which would refute Theorem 9 directly.","tokens_in":43814,"feed_emoji":"🧩","tokens_out":7601,"duration_ms":72648,"temperature":0.7,"pith_summary":"Constraint satisfaction problems over infinite homogeneous structures lack a full dichotomy, and few polymorphism conditions had been known to guarantee polynomial-time solvability. This paper proves that if the ground structure is k-neoliberal and has finite duality, and the template is a first-order expansion preserved by a chain of quasi Jónsson operations, then the template is implicationally simple on injective instances. From that the authors obtain the concrete relational-width bound $(k, \\max(k+1, b_B))$, so local consistency checking solves the CSP in polynomial time. This is the first non-trivial purely algebraic height-1 Maltsev condition shown to imply bounded width for this natural subclass of infinite-domain templates, and it includes templates whose complexity was previously unclassified.","feed_headline":"Quasi Jónsson chains imply bounded width for infinite CSPs","feed_subtitle":"A height-1 algebraic condition yields local-consistency solving for k-neoliberal homogeneous templates of finite duality.","key_machinery":"The load-bearing object is the chain of quasi Jónsson operations, a sequence $(J_1,\\ldots,J_{2n+1})$ of ternary operations obeying $J_1(x,x,y)=J_1(x,x,x)$, $J_i(x,y,x)=J_i(x,x,x)$ for every $i$, $J_{2i-1}(x,y,y)=J_{2i}(x,y,y)$, $J_{2i}(x,x,y)=J_{2i+1}(x,x,y)$, and $J_{2n+1}(x,y,y)=J_{2n+1}(y,y,y)$. The other central object is the injective implication graph of the template, whose vertices are pairs of pp-definable $k$-ary relations and whose arcs are 'implications' between them; the theorem shows that the algebraic condition makes this graph acyclic, and acyclicity is what yields the width bound. The $k$-neoliberal and finite-duality assumptions on $B$ supply the structural lemma that every minimal instance with single-orbit projections has a solution, and they make it possible to extract the large finite witness sets used in the contradiction proofs against quasi Jónsson preservation.","core_discovery":"The central claim is that invariance under a chain of quasi Jónsson operations is incompatible with pp-defining a 'critical relation', and therefore forces the injective implication graph to be acyclic. Theorem 9 states this as: for every $k \\ge 2$, every $k$-neoliberal $B$ with finite duality, and every first-order expansion $A$ of $B$, if $A$ is invariant under a chain of quasi Jónsson operations, then $A$ is implicationally simple on injective instances. Corollary 10 converts acyclicity into a width statement: $A$ has relational width $(k, \\max(k+1, b_B))$, which means that enforcing $(k,\\max(k+1,b_B))$-minimality on any non-trivial instance is guaranteed to find a solution when one exists. The proof runs by contradiction: a directed cycle in the injective implication graph is refined into a critical relation, and then a long chain of identity manipulations shows that no chain of quasi Jónsson operations can preserve such a relation.","pith_inferences":["I would expect the argument to extend to templates that pp-define injective pairs but lack the full $k$-neoliberal assumption, since finite duality appears to enter only when constructing large witness sets; this suggests a broader class of finitely bounded structures may admit the same bound.","A profitable next step is to test the bound on multi-colored hypergraph CSPs with more than two edge colors, where no classifications exist; one could check whether $(k, \\max(k+1, b_B))$ is tight there.","If the model-completeness gap turns out to matter, a natural experiment is to construct a non-core first-order expansion satisfying the algebraic condition but failing implicational simplicity; such an example would force either a revised theorem or a revised proof strategy."],"forward_implications":["Every such template $A$ has relational width $(k, \\max(k+1, b_B))$, so any non-trivial minimal instance is solvable by local consistency checking.","Consequently $\\mathsf{CSP}(A)$ is in $\\mathsf{P}$ for every first-order expansion of a $k$-neoliberal finite-duality structure preserved by a chain of quasi Jónsson operations.","The result covers templates over the random graph, Henson digraphs, the homogeneous C-relation, $k$-uniform hypergraphs, and multi-colored multi-hypergraphs, including cases with no known complexity classification.","By implications noted in the paper, the bound also applies to templates preserved by chains of quasi directed Jónsson operations and by chains of quasi Pixley operations.","The width bound is optimal for any structure in the class."],"supporting_citations":[{"why":"Supplies the finite-domain precedent that congruence distributivity implies bounded width, the result being lifted here.","marker":"[27]"},{"why":"Provides the finite-domain characterization of bounded width via local consistency that motivates the height-1 Maltsev-condition approach.","marker":"[28]"},{"why":"Contributes the implication-digraph framework and the strategy of reducing width to acyclicity of an implication graph for binary cores.","marker":"[36]"},{"why":"Supplies Lemmas 22 and 23 on binary essential operations and binary injections, used to reduce the CSP to its injective-instance version.","marker":"[37]"},{"why":"Provides hypergraph width-bound machinery and a lemma used in the proof that injective width transfers to full width.","marker":"[12]"},{"why":"Gives a general upper bound on relational width for templates with canonical pseudo-totally symmetric polymorphisms, which the present bound matches.","marker":"[41]"},{"why":"Shows relational width for first-order expansions of homogeneous graphs under quasi near-unanimity operations, the starting point for the present generalization.","marker":"[33]"},{"why":"Supplies definitions of chains of quasi Jónsson operations, k-neoliberal structures, and the model-complete-core framework used throughout.","marker":"[20]"}],"fun_headline_variants":["Quasi Jónsson chains yield bounded width for infinite CSPs","New condition gives bounded width to infinite-domain CSPs","Infinite CSPs: quasi Jónsson chains ensure local consistency","Critical relations blocked: quasi Jónsson gives bounded width","Algebraic chain condition achieves bounded width for infinite CSPs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof requires that the template be an omega-categorical model-complete core so that the chain of quasi Jónsson operations can be made idempotent on every finite set; the theorem as stated assumes only a first-order expansion of B, leaving that step unjustified for templates that are not model-complete cores.","fun_headline_variants_meta":{"raw":{"variants":["Quasi Jónsson chains yield bounded width for infinite CSPs","New condition gives bounded width to infinite-domain CSPs","Infinite CSPs: quasi Jónsson chains ensure local consistency","Critical relations blocked: quasi Jónsson gives bounded width","Algebraic chain condition achieves bounded width for infinite CSPs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000681,"raw_usage":{"total_tokens":3088,"prompt_tokens":938,"completion_tokens":2150,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":554,"completion_tokens_details":{"reasoning_tokens":2066}},"tokens_in":554,"tokens_out":2150,"duration_ms":16149,"temperature":1.0,"reasoning_tokens":2066,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T13:21:56.270089+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a first-order expansion A of a k-neoliberal structure B with finite duality that is preserved by a chain of quasi Jónsson operations, and exhibit a non-trivial (k, max(k+1,b_B))-minimal instance of CSP(A) with no solution; Corollary 10 would then be false. More sharply, look for a directed cycle in the injective implication graph of such an A, which would refute Theorem 9 directly.","supporting_citations":[{"cited_title":"Congruence distributivity impl ies bounded width,","cited_arxiv_id":null,"evidence_quote":"Supplies the finite-domain precedent that congruence distributivity implies bounded width, the result being lifted here."},{"cited_title":"On the relational width of first-order expans ions of finitely bounded homogeneous binary cores with bounded strict width ,","cited_arxiv_id":null,"evidence_quote":"Contributes the implication-digraph framework and the strategy of reducing width to acyclicity of an implication graph for binary cores."},{"cited_title":"Smooth approximations and cs ps over finitely bounded homogeneous structures,","cited_arxiv_id":null,"evidence_quote":"Supplies Lemmas 22 and 23 on binary essential operations and binary injections, used to reduce the CSP to its injective-instance version."},{"cited_title":"Collapsing the bounded width hierarchy for infinite-domain CSPs: when symmetries are enough","cited_arxiv_id":"2102.07531","evidence_quote":"Gives a general upper bound on relational width for templates with canonical pseudo-totally symmetric polymorphisms, which the present bound matches."},{"cited_title":"Relational width of first-order expansions o f homogeneous graphs with bounded strict width,","cited_arxiv_id":null,"evidence_quote":"Shows relational width for first-order expansions of homogeneous graphs under quasi near-unanimity operations, the starting point for the present generalization."},{"cited_title":"Bodirsky, Complexity of Infinite-Domain Constraint Satisfaction , ser","cited_arxiv_id":null,"evidence_quote":"Supplies definitions of chains of quasi Jónsson operations, k-neoliberal structures, and the model-complete-core framework used throughout."}],"review_version":1}