pith. sign in

arxiv: 2501.17060 · v2 · submitted 2025-01-28 · 💻 cs.LO

The sorrows of a smooth digraph: the first hardness criterion for infinite directed graph-colouring problems

Johanna Brunar , Marcin Kozik , Tom\'a\v{s} Nagy , Michael Pinsker This is my paper

Pith reviewed 2026-05-23 04:47 UTC · model grok-4.3

classification 💻 cs.LO
keywords smooth digraphalgebraic lengthpp-constructionoligomorphic groupconservative colouringNP-hardnessomega-categorical structureinfinite CSP
0
0 comments X

The pith

Smooth digraphs of algebraic length 1 without pseudo-loops pp-construct every finite structure using orbit pairs and are therefore NP-hard for conservative graph colouring.

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

The paper proves that any smooth digraph of algebraic length 1, when combined with pairs of orbits from an oligomorphic subgroup of its automorphism group, can pp-construct every finite structure unless the digraph contains a pseudo-loop. This directly implies that the conservative graph-colouring problem for such a digraph is NP-hard. The result lifts earlier finite-domain dichotomies for conservative templates and for smooth digraphs to the infinite omega-categorical setting, where previous lifting attempts had been limited to undirected-graph results.

Core claim

Any smooth digraph of algebraic length 1 pp-constructs, together with pairs of orbits of an oligomorphic subgroup of its automorphism group, every finite structure unless the digraph has a pseudo-loop, i.e., an edge within an orbit.

What carries the argument

pp-construction that incorporates pairs of orbits from an oligomorphic automorphism group; the construction transfers the capacity to build all finite structures and thereby imports NP-hardness.

If this is right

  • Conservative graph-colouring problems on these digraphs are NP-hard unless a pseudo-loop is present.
  • Omega-categorical structures enriched by pairs of orbits now carry a new algebraic invariant that detects failure to pp-construct some finite structure.
  • Structural dichotomies previously known only for finite smooth digraphs extend to the infinite case.
  • Hardness lifting for directed graphs now surpasses the earlier Hell-Nesetril-style generalisations that stopped at undirected graphs.

Where Pith is reading between the lines

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

  • The same orbit-pair technique may classify the complexity of additional infinite constraint problems whose templates are built from digraphs.
  • Absence of a pseudo-loop could serve as a uniform obstruction for tractability across families of omega-categorical templates.
  • Checking for pseudo-loops might become a practical first test before attempting to solve an infinite colouring instance.

Load-bearing premise

The digraph must be smooth, have algebraic length 1, and possess an oligomorphic automorphism group so that pairs of orbits remain available for the construction.

What would settle it

Exhibit one smooth digraph of algebraic length 1 with no pseudo-loop such that, even after adjoining all pairs of orbits, it fails to pp-construct at least one finite structure.

Figures

Figures reproduced from arXiv: 2501.17060 by Johanna Brunar, Marcin Kozik, Michael Pinsker, Tom\'a\v{s} Nagy.

Figure 1
Figure 1. Figure 1: ω vs. α is not. C. Structure of the proof of Theorem I.3 We now present a sketch of the core ideas involved in proving the main result, and of the organisation of the sections pertaining to this proof. While in Section IV-A, we construct a refinement α of ω subject to the properties outlined above, Section VI is devoted to proving Theorem I.3. The proof is guided by the case distinction presented in [PITH… view at source ↗
Figure 2
Figure 2. Figure 2: Overview of the proof the restriction of α(G, Ω) to H still provides an equivalence that inherits from α(G, Ω) desirable properties, which we encapsulate in the following definition: Definition IV.4. Any refinement of ω that satisfies all three items from Lemma IV.3 is said to finitise (G, Ω). The strength of the following lemma lies, especially, in the fact that it does not apply only to α(G, Ω), but to a… view at source ↗
read the original abstract

Two major milestones on the road to the full complexity dichotomy for finite-domain constraint satisfaction problems were Bulatov's proof of the dichotomy for conservative templates, and the structural dichotomy for smooth digraphs of algebraic length 1 due to Barto, Kozik, and Niven. We lift the combined scenario to the infinite, and prove that any smooth digraph of algebraic length 1 pp-constructs, together with pairs of orbits of an oligomorphic subgroup of its automorphism group, every finite structure -- and hence its conservative graph-colouring problem is NP-hard -- unless the digraph has a pseudo-loop, i.e. an edge within an orbit. We thereby overcome, for the first time, previous obstacles to lifting structural results for digraphs in this context from finite to $\omega$-categorical structures; the strongest lifting results hitherto not going beyond a generalisation of the Hell-Ne\v{s}et\v{r}il theorem for undirected graphs. As a consequence, we obtain a new algebraic invariant of arbitrary $\omega$-categorical structures enriched by pairs of orbits which fail to pp-construct some finite structure.

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.

Referee Report

0 major / 3 minor

Summary. The manuscript claims to lift the Barto-Kozik-Niven structural dichotomy for smooth digraphs of algebraic length 1 to the ω-categorical setting. It proves that any smooth digraph of algebraic length 1, together with pairs of orbits of an oligomorphic subgroup of its automorphism group, pp-constructs every finite structure unless the digraph has a pseudo-loop (an edge within an orbit). Consequently, the conservative graph-colouring problem is NP-hard in the absence of a pseudo-loop. The result overcomes prior obstacles to such liftings (previously limited to generalizations of the Hell-Nešetřil theorem) and yields a new algebraic invariant for arbitrary ω-categorical structures enriched by pairs of orbits.

Significance. If the central claim holds, the work is significant: it supplies the first lifting of a structural dichotomy result for digraphs from the finite to the ω-categorical case, using pp-constructions augmented by orbit pairs under oligomorphic groups. This produces a new algebraic invariant and extends the combined Bulatov conservative and Barto-Kozik-Niven scenarios to infinite domains. The conditional nature of the result (smoothness, algebraic length 1, oligomorphicity) is clearly stated.

minor comments (3)
  1. [Abstract] The abstract is information-dense; consider breaking the main theorem statement into two sentences to improve immediate readability for readers outside the immediate subfield.
  2. [Introduction] Early in the introduction, provide a brief reminder of the definition of 'pp-construction' and 'pseudo-loop' (even if standard in the area) to aid readers who may not have the finite-domain papers at hand.
  3. Ensure that the precise statement of the main theorem (including the exact role of the oligomorphic subgroup and the orbit-pair relations) is highlighted in a numbered theorem environment rather than only in prose.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, recognition of the significance of lifting the Barto-Kozik-Niven dichotomy to the ω-categorical setting, and recommendation of minor revision. No major comments appear in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The paper derives a new pp-construction lifting the finite Barto-Kozik-Niven dichotomy for smooth digraphs of algebraic length 1 to the ω-categorical case, using oligomorphic automorphism groups and orbit pairs. This construction is presented as a fresh argument overcoming prior obstacles, conditional on the stated structural hypotheses (smoothness, algebraic length 1, oligomorphicity, pseudo-loop absence). The citation to the finite result (Barto-Kozik-Niven) is to an independent prior theorem and does not reduce the new infinite lifting to a self-citation chain or definition. No self-definitional steps, fitted inputs renamed as predictions, or ansatz smuggling appear in the abstract or described claim. The result remains externally falsifiable via the pp-construction definition and is not equivalent to its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on standard definitions from universal algebra and model theory for omega-categorical structures; no new free parameters or invented entities are introduced in the abstract.

axioms (1)
  • standard math Definitions of pp-constructions, oligomorphic permutation groups, algebraic length, and smoothness for digraphs
    Invoked throughout the statement of the main theorem

pith-pipeline@v0.9.0 · 5738 in / 1068 out tokens · 30656 ms · 2026-05-23T04:47:34.087759+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. When Darwin met Ianus: dichotomies of expressivity

    cs.LO 2025-09 unverdicted novelty 7.0

    Tractable temporal and phylogeny constraint languages have limited pp-interpretative power and admit 4-ary pseudo-Siggers polymorphisms, revealing a common core in their proofs.

Reference graph

Works this paper leans on

76 extracted references · 76 canonical work pages · cited by 1 Pith paper

  1. [1]

    A finer redu ction of constraint problems to digraphs,

    J. Bul´ ın, D. Delic, M. Jackson, and T. Niven, “A finer redu ction of constraint problems to digraphs,” Logical Methods in Computer Science , vol. 11, no. 4, 2015

    work page 2015

  2. [2]

    The computational structure of monotone monadic SNP and constraint satisfaction: A study through Da talog and group theory,

    T. Feder and M. Y . V ardi, “The computational structure of monotone monadic SNP and constraint satisfaction: A study through Da talog and group theory,” SIAM Journal on Computing , vol. 28, pp. 57–104, 1999

    work page 1999

  3. [3]

    Monotone monadic SNP and constraint satisfaction,

    ——, “Monotone monadic SNP and constraint satisfaction, ” in Proceed- ings of the Symposium on Theory of Computing (STOC) , 1993, pp. 612 – 622

    work page 1993

  4. [4]

    The complexity of satisfiability proble ms,

    T. J. Schaefer, “The complexity of satisfiability proble ms,” in Proceed- ings of the Symposium on Theory of Computing (STOC) , 1978, pp. 216– 226

    work page 1978

  5. [5]

    A dichotomy theorem for nonuniform CSPs,

    A. A. Bulatov, “A dichotomy theorem for nonuniform CSPs, ” in 58th IEEE Annual Symposium on F oundations of Computer Science, F OCS 2017, Berkeley, CA, USA, October 15-17 , 2017, pp. 319–330

    work page 2017

  6. [6]

    A proof of CSP dichotomy conjecture,

    D. N. Zhuk, “A proof of CSP dichotomy conjecture,” in 58th IEEE Annual Symposium on F oundations of Computer Science, FOCS 2 017, Berkeley, CA, USA, October 15-17 , 2017, pp. 331–342

    work page 2017

  7. [7]

    A proof of the CSP dichotomy conjecture,

    D. Zhuk, “A proof of the CSP dichotomy conjecture,” Journal of the ACM, vol. 67, no. 5, pp. 30:1–30:78, 2020

    work page 2020

  8. [8]

    On the structure of polynomial time reduci bility,

    R. E. Ladner, “On the structure of polynomial time reduci bility,” Journal of the ACM , vol. 22, no. 1, pp. 155–171, 1975

    work page 1975

  9. [9]

    On the complexity of H-colori ng,

    P . Hell and J. Neˇ setˇ ril, “On the complexity of H-colori ng,” Journal of Combinatorial Theory, Series B , vol. 48, pp. 92–110, 1990

    work page 1990

  10. [10]

    A dichotomy theorem for constraint sati sfaction prob- lems on a 3-element set,

    A. A. Bulatov, “A dichotomy theorem for constraint sati sfaction prob- lems on a 3-element set,” Journal of the ACM, vol. 53, no. 1, pp. 66–120, 2006

    work page 2006

  11. [11]

    The CSP dichotomy hold s for digraphs with no sources and no sinks (a positive answer to a c onjecture of Bang-Jensen and Hell),

    L. Barto, M. Kozik, and T. Niven, “The CSP dichotomy hold s for digraphs with no sources and no sinks (a positive answer to a c onjecture of Bang-Jensen and Hell),” SIAM Journal on Computing , vol. 38, no. 5, pp. 1782–1802, 2009

    work page 2009

  12. [12]

    Absorbing Subalgebras, Cyclic T erms and the Constraint Satisfaction Problem,

    L. Barto and M. Kozik, “Absorbing Subalgebras, Cyclic T erms and the Constraint Satisfaction Problem,” Logical Methods in Computer Science , vol. 8:1, no. 07, pp. 1–26, 2012

    work page 2012

  13. [13]

    Optimal s trong Mal’cev conditions for omitting type 1 in locally finite varieties,

    K. A. Kearnes, P . Markovi´ c, and R. McKenzie, “Optimal s trong Mal’cev conditions for omitting type 1 in locally finite varieties,” Algebra Universalis, vol. 72, no. 1, pp. 91–100, 2015

    work page 2015

  14. [14]

    Constraint satisfacti on with countable homogeneous templates,

    M. Bodirsky and J. Neˇ setˇ ril, “Constraint satisfacti on with countable homogeneous templates,” Journal of Logic and Computation , vol. 16, no. 3, pp. 359–373, 2006

    work page 2006

  15. [15]

    Topological Birkhoff,

    M. Bodirsky and M. Pinsker, “Topological Birkhoff,” Transactions of the American Mathematical Society , vol. 367, pp. 2527–2549, 2015

    work page 2015

  16. [16]

    The wonderland of reflections,

    L. Barto, J. Oprˇ sal, and M. Pinsker, “The wonderland of reflections,” Israel Journal of Mathematics , vol. 223, no. 1, pp. 363–398, 2018

    work page 2018

  17. [17]

    Total ordering problem,

    J. Opatrny, “Total ordering problem,” SIAM Journal on Computing , vol. 8, no. 1, pp. 111–114, 1979

    work page 1979

  18. [18]

    Bodirsky, Complexity of Infinite-Domain Constraint Satisfaction , ser

    M. Bodirsky, Complexity of Infinite-Domain Constraint Satisfaction , ser. Lecture Notes in Logic (52). Cambridge, United Kingdom; New Y ork, NY: Cambridge University Press, 2021

    work page 2021

  19. [19]

    Current challenges in infinite-domain con straint satisfac- tion: Dilemmas of the infinite sheep,

    M. Pinsker, “Current challenges in infinite-domain con straint satisfac- tion: Dilemmas of the infinite sheep,” in 52nd IEEE International Symposium on Multiple-V alued Logic, ISMVL 2022, Dallas, TX , USA, May 18-20, 2022 , 2022, pp. 80–87

    work page 2022

  20. [20]

    Projective clone homo- morphisms,

    M. Bodirsky, M. Pinsker, and A. Pongr´ acz, “Projective clone homo- morphisms,” Journal of Symbolic Logic , vol. 86, no. 1, pp. 148–161, 2021

    work page 2021

  21. [21]

    The algebraic dichotomy conje cture for infinite domain Constraint Satisfaction Problems,

    L. Barto and M. Pinsker, “The algebraic dichotomy conje cture for infinite domain Constraint Satisfaction Problems,” in Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science , ser. LICS ’16, 2016, p. 615–622

    work page 2016

  22. [22]

    The equivalence of two dichotomy conjectures for infinite domai n constraint satisfaction problems,

    L. Barto, M. Kompatscher, M. Olˇ s´ ak, T. V . Pham, and M. Pinsker, “The equivalence of two dichotomy conjectures for infinite domai n constraint satisfaction problems,” in Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science , ser. LICS ’17, 2017, pp. 1–12

    work page 2017

  23. [23]

    Equations in oligomorphic clones and the constraint satis faction prob- lem for ω-categorical structures,

    L. Barto, M. Kompatscher, M. Olˇ s´ ak, V . P . Trung, and M. Pinsker, “Equations in oligomorphic clones and the constraint satis faction prob- lem for ω-categorical structures,” Journal of Mathematical Logic , vol. 19, no. 02, p. 1950010, 2019

    work page 2019

  24. [24]

    Topology Is Irrelevant (In a Di chotomy Conjecture for Infinite Domain Constraint Satisfaction Pro blems),

    L. Barto and M. Pinsker, “Topology Is Irrelevant (In a Di chotomy Conjecture for Infinite Domain Constraint Satisfaction Pro blems),” SIAM Journal on Computing , vol. 49, no. 2, pp. 365–393, 2020

    work page 2020

  25. [25]

    Symmetries of Graphs and Structures that Fail to Interpret a Finite Thin g,

    L. Barto, B. Bodor, M. Kozik, A. Mottet, and M. Pinsker, “ Symmetries of Graphs and Structures that Fail to Interpret a Finite Thin g,” in Proceedings of the 38th Annual ACM/IEEE Symposium on Logic i n Computer Science , ser. LICS ’23. IEEE, 2023, pp. 1–13

    work page 2023

  26. [26]

    A dichotomy theorem for constraints on a three- element set,

    A. A. Bulatov, “A dichotomy theorem for constraints on a three- element set,” in Proceedings of the Annual Symposium on F oundations of Computer Science (FOCS) , 2002, pp. 649–658

    work page 2002

  27. [27]

    Tractable conservative constraint satisfaction problems,

    ——, “Tractable conservative constraint satisfaction problems,” in Pro- ceedings of the 18th IEEE Symposium on Logic in Computer Scie nce, ser. LICS ’03, Ottawa, Canada, 2003, pp. 321–330

    work page 2003

  28. [28]

    The Dichotomy for Conservative Constraint S atisfaction Prob- lems Revisited,

    L. Barto, “The Dichotomy for Conservative Constraint S atisfaction Prob- lems Revisited,” in Proceedings of the 26th Annual IEEE Symposium on Logic in Computer Science , ser. LICS ’11, 2011, pp. 301–310

    work page 2011

  29. [29]

    CSP for binary conservative relational stru ctures,

    A. Kazda, “CSP for binary conservative relational stru ctures,” Algebra universalis, vol. 75, no. 1, pp. 75–84, Dec. 2015

    work page 2015

  30. [30]

    Conservative constraint satisfaction re-revisited,

    A. A. Bulatov, “Conservative constraint satisfaction re-revisited,” Jour- nal Computer and System Sciences , vol. 82, no. 2, pp. 347–356, 2016

    work page 2016

  31. [31]

    The expressibility of functions on the boolean domain, wit h applica- tions to counting csps,

    A. A. Bulatov, M. Dyer, L. A. Goldberg, M. Jerrum, and C. M cquillan, “The expressibility of functions on the boolean domain, wit h applica- tions to counting csps,” Journal of the ACM , vol. 60, no. 5, Oct. 2013

    work page 2013

  32. [32]

    The complexity of approximating conservativ e counting csps,

    X. Chen, M. Dyer, L. A. Goldberg, M. Jerrum, P . Lu, C. McQu illan, and D. Richerby, “The complexity of approximating conservativ e counting csps,” Journal of Computer and System Sciences , vol. 81, no. 1, pp. 311–329, 2015

    work page 2015

  33. [33]

    The complexity of conservative valued csps,

    V . Kolmogorov and S. ˇZivn´ y, “The complexity of conservative valued csps,” Journal of the ACM , vol. 60, no. 2, May 2013

    work page 2013

  34. [34]

    Hell and A

    P . Hell and A. Rafiey, The Dichotomy of List Homomorphisms for Digraphs, pp. 1703–1713

    work page

  35. [35]

    Bi-arc digraphs: Recog nition algo- rithm and applications,

    P . Hell, A. Rafiey, and A. Rafiey, “Bi-arc digraphs: Recog nition algo- rithm and applications,” in LATIN 2024: Theoretical Informatics , J. A. Soto and A. Wiese, Eds. Cham: Springer Nature Switzerland, 2 024, pp. 31–45

    work page 2024

  36. [36]

    L. Egri, P . Hell, B. Larose, and A. Rafiey, Space complexity of list H- colouring: a dichotomy , pp. 349–365

    work page

  37. [37]

    Sur certaines relations qui g´ en´ eralisent l’ordre des nombres rationnels,

    R. Fra¨ ıss´ e, “Sur certaines relations qui g´ en´ eralisent l’ordre des nombres rationnels,” Comptes Rendus de l’Acad´ emie des Sciences , vol. 237, pp. 540–542, 1953

    work page 1953

  38. [38]

    Universal graphs wit h forbidden subgraphs and algebraic closure,

    G. Cherlin, S. Shelah, and N. Shi, “Universal graphs wit h forbidden subgraphs and algebraic closure,” Advances in Applied Mathematics , vol. 22, pp. 454–491, 1999

    work page 1999

  39. [39]

    All those ramsey classe s (ramsey classes with closures and forbidden homomorphisms),

    J. Hubiˇ cka and J. Neˇ setˇ ril, “All those ramsey classe s (ramsey classes with closures and forbidden homomorphisms),” Advances in Mathemat- ics, vol. 356, p. 106791, 2019

    work page 2019

  40. [40]

    A proof of t he algebraic tractability conjecture for monotone monadic SNP,

    M. Bodirsky, F. R. Madelaine, and A. Mottet, “A proof of t he algebraic tractability conjecture for monotone monadic SNP,” SIAM Journal on Computing, vol. 50, no. 4, pp. 1359–1409, 2021

    work page 2021

  41. [41]

    The complexity of temporal co nstraint satisfaction problems,

    M. Bodirsky and J. K´ ara, “The complexity of temporal co nstraint satisfaction problems,” Journal of the ACM , vol. 57, no. 2, pp. 1– 41, 2009, an extended abstract appeared in the Proceedings o f the Symposium on Theory of Computing (STOC)

    work page 2009

  42. [42]

    Minimal operations over per mutation groups,

    P . Marimon and M. Pinsker, “Minimal operations over per mutation groups,” 2024, preprint arXiv:2410.22060

    work page arXiv 2024

  43. [43]

    Smooth approximations and cs ps over finitely bounded homogeneous structures,

    A. Mottet and M. Pinsker, “Smooth approximations and cs ps over finitely bounded homogeneous structures,” in Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science , ser. LICS ’22, 2022

    work page 2022

  44. [44]

    Schaefer’s theorem for gra phs,

    M. Bodirsky and M. Pinsker, “Schaefer’s theorem for gra phs,” Journal of the ACM , vol. 62, no. 3, p. 52 pages (article number 19), 2015, a conference version appeared in the Proceedings of STOC 2011 , pages 655-664

    work page 2015

  45. [45]

    An order out of nowhe re: a new algorithm for infinite-domain csps,

    A. Mottet, T. Nagy, and M. Pinsker, “An order out of nowhe re: a new algorithm for infinite-domain csps,” in Proceedings of the 51st EATCS International Colloquium on Automata, Languages and Progr amming (ICALP), 2024, pp. 148:1–148:18

    work page 2024

  46. [46]

    Smooth approximations: An al gebraic approach to csps over finitely bounded homogeneous structur es,

    A. Mottet and M. Pinsker, “Smooth approximations: An al gebraic approach to csps over finitely bounded homogeneous structur es,” Journal of the ACM , vol. 71, no. 5, Oct. 2024

    work page 2024

  47. [47]

    Cores of Countably Categorical Structur es,

    M. Bodirsky, “Cores of Countably Categorical Structur es,” Logical Methods in Computer Science (LMCS) , vol. 3, no. 1, pp. 1–16, 2007

    work page 2007

  48. [48]

    Loop conditions,

    M. Olˇ s´ ak, “Loop conditions,”Algebra Universalis, vol. 81, no. 2, 2020

    work page 2020

  49. [49]

    Pseudo-loo p conditions,

    P . Gillibert, J. Jonuˇ sas, and M. Pinsker, “Pseudo-loo p conditions,” Bulletin of the London Mathematical Society , vol. 51, no. 5, pp. 917– 936, 2019

    work page 2019

  50. [50]

    A strong Mal’cev condition for varietie s omitting the unary type,

    M. H. Siggers, “A strong Mal’cev condition for varietie s omitting the unary type,” Algebra Universalis, vol. 64, no. 1, pp. 15–20, 2010

    work page 2010

  51. [51]

    Existence theorems for wea kly symmetric operations,

    M. Mar´ oti and R. McKenzie, “Existence theorems for wea kly symmetric operations,” Algebra Universalis, vol. 59, no. 3, 2008

    work page 2008

  52. [52]

    Optimal strong Mal’cev conditions for congruence meet-semidistributivi ty in locally finite varieties,

    J. Jovanovi´ c, P . Markovi´ c, R. McKenzie, and M. Moore,“Optimal strong Mal’cev conditions for congruence meet-semidistributivi ty in locally finite varieties,” Algebra Universalis, vol. 76, pp. 305–325, 2016

    work page 2016

  53. [53]

    Canonical functions: a pro of via topo- logical dynamics,

    M. Bodirsky and M. Pinsker, “Canonical functions: a pro of via topo- logical dynamics,” Homogeneous Structures, A W orkshop in Honour of Norbert Sauer’s 70th Birthday, Contributions to Discrete M athematics, vol. 16, no. 2, pp. 36–45, 2021

    work page 2021

  54. [54]

    On the unique games conjecture,

    S. Khot, “On the unique games conjecture,” in 46th Annual IEEE Symposium on F oundations of Computer Science (FOCS’05) , 2005, p. 3

    work page 2005

  55. [55]

    I. G. Rosenberg, ¨Uber die funktionale V ollst¨ andigkeit in den mehrwer- tigen Logiken: Struktur der Funktionen von mehreren V er¨ an derlichen auf endlichen Mengen , ser. Rozpravy ˇCeskoslovensk´ e Akademie Vˇ ed: ˇRada matematick` ych a pˇ r´ ırodn´ ıch vˇ ed. Academia naklad atelstv´ ı ˇCeskoslovensk´ e akademie vˇ ed, 1970

    work page 1970

  56. [56]

    Mi nimal Taylor algebras as a common framework for the three algebraic appro aches to the CSP,

    L. Barto, Z. Brady, A. Bulatov, M. Kozik, and D. Zhuk, “Mi nimal Taylor algebras as a common framework for the three algebraic appro aches to the CSP,” in Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science , ser. LICS ’21. New Y ork, NY , USA: Association for Computing Machinery, 2021. APPENDIX A. Missing proofs from Section IV...

    work page 2021

  57. [57]

    F or all A,B ∈ G/α contained in the same weakly connected component of G/α , it holds that ΩA = Ω B

    work page

  58. [58]

    If X⊆ G is α -stable and such that X +S is contained in the same weakly connected component of G/α as X, then X +S is α -stable

    work page

  59. [59]

    F or all ω -classesP,Q andα -classesA,B ⊆ P such that A,B,A +S andB +S are contained in the same weakly connected component of G/α , there exists a bijection between the sets ((A +S)∩Q)/α and ((B +S)∩Q)/α . Proof. To prove the first item, let f ∈ ΩA. Since A,B are contained in the same weakly connected component of G/α , there exists an Ω-orbit-labelled pa...

    work page

  60. [60]

    U← V Then there exists a realisable Ω-orbit-labelled path µ from U to V and a realisable relabelling µ ′ thereof from U ′ to V ′ such that (µ,µ ′) is properly separated, and such that µ extendsU→ V or U← V , respectively. The conclusion of the lemma can then be derived from the claim by induction as follows: let π = ( p, (O1,...,O n)), where O1 = On = O; ...

    work page

  61. [61]

    By Case 2., there exists a pair (µ 2,µ ′

    for U → V and V → W as in the claim. By Case 2., there exists a pair (µ 2,µ ′

    work page

  62. [62]

    Finally, labelling ← by the labels (V ′,V ) and (W ′,W ), we get a pair (µ 3,µ ′

    for V → W and V ′→ W ′. Finally, labelling ← by the labels (V ′,V ) and (W ′,W ), we get a pair (µ 3,µ ′

    work page

  63. [63]

    Now, (µ 1 +µ 2 +µ 3,µ ′ 1 +µ ′ 2 +µ ′ 3) has the required properties

    for V ′← V and W ′← W . Now, (µ 1 +µ 2 +µ 3,µ ′ 1 +µ ′ 2 +µ ′ 3) has the required properties. By the remark after the claim, this concludes the proof of the lemma. Lemma IV .9. Let G = (G;→ ) be a smooth digraph, let Ω≤ Aut(G) be oligomorphic, and suppose that G/ Ω has no loops. LetO,P be two→ -adjacentω -classes. Then G together with all unions of pairs ...

    work page

  64. [64]

    Proposition VI.6

    Central or OR (proof of Proposition VI.6 ): Let us restate the first step in the course of proving Proposition VI.3 . Proposition VI.6. G together with Ω-orbits and the restric- tions of α to ω -classes pp-define one of the following

    work page

  65. [66]

    Note that if H ={A1}, then H⊕ R =H +R

    the relation OR(T,T ) for an α -stable TSR-relation T For the proof of Proposition VI.6 , we need to introduce the following notion: for a binary relation R, and a set H⊆ G that is a union of α -classes A1,...,A ℓ, we write H⊕ R for the unary relation H⊕ R(x)≡∃ x1,...,x ℓ ⋀ i∈ [ℓ] (xi∈ Ai∧ R(xi,x )). Note that if H ={A1}, then H⊕ R =H +R. Furthermore, obs...

    work page

  66. [67]

    a relation that is central modulo α , or

    work page

  67. [68]

    a binary relation R and a unary relation C such that there exists an ω -classO with the property that for every α -classA⊆ O, ((A⊕ R)∩C)− R =G but ((O⊕ R)∩ C)− R̸=G. Proof. If k → is central modulo α , then we have already found a relation as in the first item. Let us therefore assume that th is is not the case. Since G/α is k-linked and k → is not central...

    work page

  68. [69]

    F or all g∈ Ω, and for every s, ¯s∈ (g(S))n, the relation defined by φ(s, ¯s, v) is Gk

    work page

  69. [70]

    F or all g, ¯g∈ Ω with g(S)̸= ¯g(S), and for every s∈ g(S1)×···× g(Sn) and ¯s∈ ¯g(S1)×···× ¯g(Sn), the formula φ(s, ¯s, v) defines a subset of T

    work page

  70. [71]

    F or every t∈ T , there exist g∈ Ω and s∈ g(S1)×···× g(Sn), ¯s∈ gf (S1)×···× gf (Sn) such that φ(s, ¯s, t) holds true. Proof. Let u1,...,u m be representatives of all α -classes in U ⊕− R, and let OU be the m-orbit of (u1,...,u m) under Ω. Note that m≥ k as U⊆ U ⊕ − R. We define φ(x, y, v) as follows: ∃w1,...,w m,w ′ 1,...,w ′ m,v ′ 1,...,v ′ k, xw1 1 ,......

    work page

  71. [72]

    for every g∈ Ω. Thus, if g, ¯g∈ Ω satisfy g(S)̸= ¯g(S), x takes a value s∈ g(S1)×···× g(Sn), and y takes a value ¯s∈ ¯g(S1)×···× ¯g(Sn), then there needs to exist i∈ [ℓ] such that ¯g(¯si) /∈ g(S) by the choice of ℓ. Indeed, otherwise, g− 1¯g(¯si)∈ S for every i∈ [ℓ], whence |S∩ g− 1¯g(S)| ≥ℓ, and g− 1¯g(S) ̸= S in contradiction to the choice of ℓ. Hence, ...

    work page

  72. [73]

    Proposition VI.7

    From central to OR (proof of Proposition VI.7 ): In the case of Item 1 of Proposition VI.6 , we proceed by construct- ing a relation OR(DL,D R) for some unary, ω -stable relations DL and DR. Proposition VI.7. Let R be a relation that is central modulo α and Ω-invariant. Then G,R , α -classes, ω -classes, and the restrictions of α to unions of pairs of → -...

    work page

  73. [74]

    Thus, by pickinga∈ Oin for everya′∈ O′ out as above, we eventually pick a representative of every α -class in Oin

    /∈ α , then also (a1,a 2) /∈ α . Thus, by pickinga∈ Oin for everya′∈ O′ out as above, we eventually pick a representative of every α -class in Oin. Fix elements a,a ′,b a′, accordingly. Since (π,π ′) is properly separated, we have a +γπ ∨ π ′⊆ O′ out. In particular, again by Lemma IV .3, we get ba′ /∈ a + γπ ∨ π ′ + (R/α )α . By α -stability of SR, hencef...

    work page

  74. [75]

    The following statement allows us to replicate the correspondi ng proofs from [ 25]

    Improving OR: In this section, we will prove the remain- ing lemmata needed for the proof of Proposition VI.3 . The following statement allows us to replicate the correspondi ng proofs from [ 25]. Lemma A.10. LetJ :=G/α , and letR1,...,R m be relations on J. If S⊆ J n is pp-definable from R1,...R m, then its α - blow-up Sα⊆ Gn is pp-definable from Rα 1,...,...

    work page

  75. [76]

    If n≥ 3, then R equality-free pp-defines a proper α - stable TSR-relation T which is P-central or PQ-central

    work page

  76. [77]

    If n = 2 and R is additionally linked, then R equality- free pp-defines a proper α -stable TSR-relation T which is P-central or PQ-central. Proof. Let J := G/α . By Lemma A.10 and α -stability of R, it suffices to pp-define from R – considered as a relation on J – a suitable TSR-relation on J as its α -blow-up will then satisfy the required properties. By fin...

    work page