pith. sign in

arxiv: 2604.05231 · v1 · submitted 2026-04-06 · 🧮 math.LO

The colored edge theory of A. Bulatov and binary absorption in minimal Taylor algebras

Zarathustra Brady , Petar {\DJ}api\'c , Petar Markovi\'c , Aleksandar Proki\'c , Vlado Uljarevi\'c This is my paper

Pith reviewed 2026-05-10 18:30 UTC · model grok-4.3

classification 🧮 math.LO
keywords colored edge graphsminimal Taylor algebrasbinary absorptionuniversal algebraconstraint satisfactionBulatov theory
0
0 comments X

The pith

Minimal Taylor algebras admit a new definition of colored edge graphs that includes Bulatov's graphs and supports simplified reproofs of the main results.

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

The paper introduces a new definition for colored edge graphs specifically tailored to minimal Taylor algebras. This definition is designed to encompass the graphs originally defined by A. Bulatov. Using this, the authors reprove the key theorems from Bulatov's colored edge theory but with several simplifications that arise in the restricted setting of minimal Taylor algebras. A sympathetic reader would care because this provides a more accessible entry point into the theory for this important class of algebras, which are central in the study of constraint satisfaction problems and universal algebra. The work focuses on how binary absorption interacts with these graphs in the minimal case.

Core claim

We find a new definition of colored edge graphs of finite algebras in the case of minimal Taylor algebras, a definition which includes the graphs invented by A. Bulatov. Next we proceed to reprove the main results of A. Bulatov's theory in the case of minimal Taylor algebras and in our setting, finding several simplifications compared to the more general case of smooth algebras Bulatov considered.

What carries the argument

The new definition of colored edge graphs for minimal Taylor algebras, which incorporates binary absorption to simplify the structure compared to general smooth algebras.

Load-bearing premise

The new definition of colored edge graphs must both include all of Bulatov's original graphs and be sufficient to carry through the full set of main results with the claimed simplifications.

What would settle it

A counterexample where a minimal Taylor algebra has a colored edge graph under the new definition that differs from Bulatov's or where one of the reproved main results fails to hold.

read the original abstract

We find a new definition of colored edge graphs of finite algebras in the case of minimal Taylor algebras, a definition which includes the graphs invented by A. Bulatov. Next we proceed to reprove the main results of A. Bulatov's theory in the case of minimal Taylor algebras and in our setting, finding several simplifications compared to the more general case of smooth algebras Bulatov considered.

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 introduces a new definition of colored edge graphs tailored to finite minimal Taylor algebras. This definition is claimed to contain all graphs originally constructed by A. Bulatov. The authors then reprove the core theorems of Bulatov's colored-edge theory within the restricted setting of minimal Taylor algebras, obtaining simplifications that exploit the minimality and Taylor conditions.

Significance. If the new definition is inclusive and the reproofs are correct, the work supplies a streamlined treatment of colored-edge techniques for minimal Taylor algebras, a class central to the algebraic approach to the constraint satisfaction problem. The explicit verification that Bulatov's graphs are recovered ensures backward compatibility, while the simplifications may reduce technical overhead for future applications. The absence of free parameters or circular constructions in the reported argument is a positive feature.

minor comments (3)
  1. The abstract states that 'several simplifications' are obtained but does not enumerate them; a brief list or pointer to the specific theorems that become shorter would help readers assess the gain immediately.
  2. Section 2 (presumably containing the new definition) should include an explicit statement of the precise conditions under which the new colored-edge relation coincides with Bulatov's original one, beyond the inclusion claim.
  3. The reproofs would benefit from a short 'comparison' subsection that isolates the steps that are shortened by the Taylor and minimality hypotheses, rather than leaving the reader to compare the arguments with Bulatov's original papers.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary and significance assessment of our manuscript. The recommendation for minor revision is noted, but no specific major comments appear in the report. We are pleased that the referee views the new definition of colored edge graphs and the simplified reproofs as a valuable streamlined treatment for minimal Taylor algebras with ensured backward compatibility.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper introduces a specialized definition of colored edge graphs for minimal Taylor algebras that is constructed to contain Bulatov's original graphs, then carries out direct reproofs of the main results in this restricted setting to obtain simplifications. No load-bearing step reduces by definition, by fitted parameter, or by self-citation chain to its own inputs; the argument relies on external prior work by Bulatov (distinct authors) and performs independent verification within the new framework. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review supplies no concrete free parameters, axioms, or invented entities; the paper appears to work within the standard framework of universal algebra and Bulatov's existing theory.

pith-pipeline@v0.9.0 · 5382 in / 975 out tokens · 26950 ms · 2026-05-10T18:30:39.801556+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.

Reference graph

Works this paper leans on

47 extracted references · 47 canonical work pages

  1. [1]

    Barto, L.: The collapse of the bounded width hierarchy. J. Logic Comput.26, 923–943 (2016)

    work page 2016

  2. [2]

    Barto, L.: Finitely related algebras in congruence modular varieties have few subpowers. J. Eur. Math. Soc.20, 1439–1471 (2018)

    work page 2018

  3. [3]

    Barto, L., Brady, Z, Bulatov, A., Kozik, M., Zhuk, D.: Unifying the Three Algebraic Approaches to the CSP via Minimal Taylor Algebras, TheoretiCS3, 1–76 (2024)

    work page 2024

  4. [4]

    Journal of the ACM611:03, 19 pp., (2014)

    Barto, L., Kozik, M.: Constraint satisfaction problems solvable by local consistency methods. Journal of the ACM611:03, 19 pp., (2014)

    work page 2014

  5. [5]

    Barto, L., Kozik, M.: Absorbing subalgebras, cyclic terms and the constraint satisfaction problem, Log. Meth. Comput. Sci.8, 1:07 26 pp. (2012)

    work page 2012

  6. [6]

    Barto, L., Kozik, M., Niven, T.: The CSP dichotomy holds for digraphs with no sources and no sinks (a positive answer to a conjecture of Bang-Jensen and Hell). SIAM J. on Comput.38no. 5, 1782–1802 (2009)

    work page 2009

  7. [7]

    Algebra Universalis74no

    Barto, L., Kozik, M., Stanovsky, D.: Mal’tsev conditions, lack of absorption, and solvability. Algebra Universalis74no. 1, 185–206 (2015)

    work page 2015

  8. [8]

    Brady, Z.: Notes on CSPs and Polymorphisms, manuscripthttps://www.notzeb.com/csp-notes.pdf

    work page

  9. [9]

    Berman, J., Idziak, P., Markovi´ c, P., McKenzie, R., Valeriote, M., Willard, R.: Varieties with few subalgebras of powers. Trans. Amer. Math. Soc.3621445–1473 (2010)

    work page 2010

  10. [10]

    Bulatov, A.: A dichotomy theorem for constraints on a three-element set. J. ACM53, 66–120 (2006)

    work page 2006

  11. [11]

    [Russian] Algebra i Logika,45655–686 (2006)

    Bulatov, A.: Complexity of Maltsev Constraints. [Russian] Algebra i Logika,45655–686 (2006)

    work page 2006

  12. [12]

    ACM Trans

    Bulatov, A.: Complexity of Conservative Constraint Satisfaction Problems. ACM Trans. Comput. Logic 12Article no. 24 66pp. (2011)

    work page 2011

  13. [13]

    104437, 14 pp., (2019)

    Bulatov, A.: Constraint Satisfaction Problems over semilattice block Mal’tsev algebras, Information and Computation268Article no. 104437, 14 pp., (2019)

    work page 2019

  14. [14]

    45, 45 pp

    Bulatov, A.: Graphs of finite algebras: edges, and connectivity, Algebra Universalis85Article no. 45, 45 pp. (2024)

    work page 2024

  15. [15]

    43, 38 pp

    Bulatov, A.: Graphs of finite algebras: maximality, rectangularity, and decomposition, Algebra Univer- salis85Article no. 43, 38 pp. (2024)

    work page 2024

  16. [16]

    Bulatov, A.: Separation of congruence intervals and implications, manuscripthttps://arxiv.org/abs/ 2007.07237

    work page arXiv 2007

  17. [17]

    In: Proc

    Bulatov, A.: Graphs of relational structures: restricted types. In: Proc. 31th IEEE Ann. Symp. on Logic in Comput. Sci. (LICS) New York, USA, 2016, pp. 642–651. doi: 10.1145/2933575.2933604 IEEE Computer Society, ISBN:978-1-4503-4391-6 COLORED EDGES AND BINARY ABSORPTION IN MINIMAL TAYLOR ALGEBRAS 38

    work page doi:10.1145/2933575.2933604 2016

  18. [18]

    11 Andrei A

    Bulatov, A.: A dichotomy theorem for nonuniform CSPs In: Proc. 2017 IEEE 58th Annual Symp. on Foundations of Comput. Sci. (FOCS), Berkeley, CA (USA, October 2017), pp. 319-330, doi: 10.1109/FOCS.2017.37, IEEE Computer Society Conference Publishing Service Los Alamitos, CA

    work page doi:10.1109/focs.2017.37 2017

  19. [19]

    Bulatov, A.: A dichotomy theorem for nonuniform CSPs, manuscript.https://arxiv.org/abs/1703. 03021

    work page

  20. [20]

    (eds) Language and Automata Theory and Applications

    Bulatov, A.: Constraint Satisfaction Problems: Complexity and Algorithms, In: Klein, S., Mart´ ın- Vide, C., Shapira, D. (eds) Language and Automata Theory and Applications. LATA 2018. Ramat Gan, (Israel, April 2018), pp. 1–25, doi: 10.1007/978-3-319-77313-1 Lecture Notes in Comput. Sci., vol 10792, (2018) Springer, New York

    work page doi:10.1007/978-3-319-77313-1 2018

  21. [21]

    Bulatov A., Dalmau, V.: Mal’tsev constraints are tractable. SIAM J. Comput.3616–27 (2006)

    work page 2006

  22. [22]

    Bulatov, A., Jeavons P., Krokhin, A., Classifying the complexity of constraints using finite algebras. SIAM J. Comp.34720–742 (2005)

    work page 2005

  23. [23]

    Bulin, J., Deli´ c, D., Jackson M., Niven, T.: A finer reduction of constraint problems to digraphs. Log. Meth. Comput. Sci.11, Article no. 18, 33 pp. (2015)

    work page 2015

  24. [24]

    Burris, S., Sankappanavar, H.P.: A course in universal algebra, Graduate Texts in Mathematics, vol

    work page

  25. [25]

    Springer, New York (1981)

    work page 1981

  26. [26]

    13., 4083–4101 (2023)

    -Dapi´ c, P., Markovi´ c, P., McKenzie, R., Proki´ c A.: SMB Algebras I: On the variety of SMB algebras, Filomat37no. 13., 4083–4101 (2023)

    work page 2023

  27. [27]

    Y.: The computational structure of monotone monadic SNP and constraint satis- faction: A study through Datalog and group theory, SIAM J

    Feder, T., Vardi, M. Y.: The computational structure of monotone monadic SNP and constraint satis- faction: A study through Datalog and group theory, SIAM J. Comput.2857–104 (1999)

    work page 1999

  28. [28]

    Freese, R., McKenzie, R.: Commutator theory for congruence modular varieties, London Math. Soc. Lecture Note vol. 125, Cambridge University Press (1987)

    work page 1987

  29. [29]

    Freese, R., McKenzie, R., McNulty, G., Taylor, W.: Algebras, lattices, varieties. Vol. II., Math. Surveys and Monographs, vol. 268, American Mathematical Society (2022)

    work page 2022

  30. [30]

    Freese, R., McKenzie, R., McNulty, G., Taylor, W.: Algebras, lattices, varieties. Vol. III., Math. Surveys and Monographs, vol. 269, American Mathematical Society (2022)

    work page 2022

  31. [31]

    Contemporary Mathematics, vol

    Hobby, D., McKenzie, R.: The structure of finite algebras. Contemporary Mathematics, vol. 76. Amer- ican Mathematical Society, Providence (1988)

    work page 1988

  32. [32]

    Idziak, P., Markovi´ c, P., McKenzie, R., Valeriote, M., Willard, R.: Tractability and learnability arising from algebra with few subpowers. SIAM J. Comput.39, 3023–3037 (2010)

    work page 2010

  33. [33]

    Master Thesis, Charles University, Prague, 2022.https://dspace.cuni.cz/bitstream/handle/20.500.11956/174285/120418680.pdf

    Jankovic, F.: Minimal Taylor Clones on Three Elements. Master Thesis, Charles University, Prague, 2022.https://dspace.cuni.cz/bitstream/handle/20.500.11956/174285/120418680.pdf

    work page 2022

  34. [34]

    G.: On the algebraic structure of combinatorial problems

    Jeavons, P. G.: On the algebraic structure of combinatorial problems. Theor. Comp. Sci.200185–204 (1998)

    work page 1998

  35. [35]

    Algebra Universalis72, 91–100 (2014)

    Kearnes, K., Markovi´ c, P., McKenzie, R.: Optimal strong Mal’cev conditions for omitting type1in locally finite varieties. Algebra Universalis72, 91–100 (2014)

    work page 2014

  36. [36]

    Kun, G.: Constraints, MMSNP, and Expander Relational Structures Combinatorica33335–347 (2013)

    work page 2013

  37. [37]

    Order 29(02), 345–359 (2012)

    Markovi´ c, P., Mar´ oti, M., McKenzie, R.: Finitely related clones and algebras with cube terms. Order 29(02), 345–359 (2012)

    work page 2012

  38. [38]

    submitted for publication

    Markovi´ c, P., Mar´ oti, M., McKenzie, R., Proki´ c, A: SMB algebras II: On the Constraint Satisfaction Problem over Semilattices of Mal’cev Blocks. submitted for publication. (2025)

    work page 2025

  39. [39]

    (early version untitled), manuscript

    Markovi´ c, P., McKenzie, R.: On the Constraint Satisfaction Problem over semilattices of Mal’cev blocks. (early version untitled), manuscript

    work page

  40. [40]

    manuscript,http://www.math.u-szeged.hu/ ~mmaroti/pdf/200x% 20Maltsev%20on%20top.pdf

    Mar´ oti, M.: Maltsev on top. manuscript,http://www.math.u-szeged.hu/ ~mmaroti/pdf/200x% 20Maltsev%20on%20top.pdf

    work page

  41. [41]

    Mar´ oti, M.: Tree on top of Maltsev, manuscript.http://www.math.u-szeged.hu/~mmaroti/pdf/200x% 20Tree%20on%20top%20of%20Maltsev.pdf

    work page

  42. [42]

    N.: Existence theorems for weakly symmetric operations

    Mar´ oti, M., McKenzie, R. N.: Existence theorems for weakly symmetric operations. Algebra Universalis 59463–489 (2008)

    work page 2008

  43. [43]

    McKenzie, R., McNulty, G., Taylor, W.: Algebras, lattices, varieties. Vol. I. The Wadsworth & Brooks/Cole Mathematics Series, Wadsworth & Brooks/Cole Advanced Books & Software, Monterey (1987)

    work page 1987

  44. [44]

    Algebra Universalis64, 15–20 (2010)

    Siggers, M.: A strong Mal’cev condition for locally finite varieties omitting the unary type. Algebra Universalis64, 15–20 (2010)

    work page 2010

  45. [45]

    Algebra Universalis44, 15–26 (2000) COLORED EDGES AND BINARY ABSORPTION IN MINIMAL TAYLOR ALGEBRAS 39

    Waldhauser, T.: Minimal clones generated by majority operations. Algebra Universalis44, 15–26 (2000) COLORED EDGES AND BINARY ABSORPTION IN MINIMAL TAYLOR ALGEBRAS 39

    work page 2000

  46. [46]

    A Proof of

    Zhuk, D.: A proof of CSP dichotomy conjecture, In: Proc. 2017 IEEE 58th Annual Symp. on Foundations of Comput. Sci. (FOCS), Berkeley, CA (USA, October 2017), pp. 331-342, doi: 10.1109/FOCS.2017.38, IEEE Computer Society Conference Publishing Service Los Alamitos, CA

    work page doi:10.1109/focs.2017.38 2017

  47. [47]

    Zhuk, D.: A Proof of the CSP Dichotomy Conjecture, Journal of the ACM675:30, 78 pp., (2020) Department of Mathematics and Informatics, University of Novi Sad, Serbia Email address:petarn@dmi.uns.ac.rs Department of Mathematics and Informatics, University of Novi Sad, Serbia Email address:pera@dmi.uns.ac.rs F aculty of Technical Sciences, University of Nov...

    work page 2020