pith. sign in

arxiv: 2604.08365 · v1 · submitted 2026-04-09 · 🧮 math.CO

Equivalences of promise compactness principles

Bertalan Bodor This is my paper

Pith reviewed 2026-05-10 16:55 UTC · model grok-4.3

classification 🧮 math.CO
keywords promise compactnessultrafilter principleOlšák polymorphismrelational structureshomomorphismsZF set theorygraph coloringconstraint satisfaction
0
0 comments X

The pith

When a pair of finite structures lacks an Olšák polymorphism, its promise compactness principle is equivalent to the ultrafilter principle over ZF.

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

The paper shows that for pairs of finite relational structures A and B where A homomorphically maps to B but the pair lacks an Olšák polymorphism, the principle K_(A,B) is equivalent to the ultrafilter principle in ZF set theory. K_(A,B) states that any structure I is homomorphic to B whenever all its finite substructures are homomorphic to A. This result covers concrete cases such as coloring cliques K3 to K5 and not-all-equal structures H2 to Hc. A reader cares because it reveals that these apparent compactness results for infinite objects are actually equivalent to a strong form of the axiom of choice. If the equivalence holds, then in set-theoretic models lacking ultrafilters, counterexamples to these compactness statements must exist.

Core claim

If (A, B) is a pair of finite relational structures with a homomorphism from A to B and no Olšák polymorphism, then over ZF the statement K_(A,B) is equivalent to the ultrafilter principle. The statement K_(A,B) asserts that for every structure I with the same signature, if every finite substructure of I homomorphically maps to A then I homomorphically maps to B. In particular this equivalence holds for the pairs (K3, K5) and (H2, Hc) with c at least 2.

What carries the argument

The absence of an Olšák polymorphism on the pair (A, B), which serves as the condition allowing the compactness principle K_(A,B) to be shown equivalent to the ultrafilter principle.

If this is right

  • K_(K3, K5) holds if and only if the ultrafilter principle holds over ZF.
  • K_(H2, Hc) holds for each c at least 2 if and only if the ultrafilter principle holds over ZF.
  • If the ultrafilter principle fails in a ZF model then for such pairs there exists a structure I where every finite substructure maps homomorphically to A but I itself does not map to B.
  • The equivalence supplies a uniform algebraic criterion for when a homomorphism compactness statement is equivalent to the ultrafilter principle.

Where Pith is reading between the lines

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

  • The presence or absence of specific polymorphisms may classify which other compactness statements in combinatorics are provable in ZF alone.
  • Analogous equivalences could apply to further relational structures arising in constraint satisfaction beyond the clique and not-all-equal cases treated here.
  • These results link infinite homomorphism problems directly to the existence of ultrafilters, suggesting a broader dictionary between algebraic conditions and choice axioms.

Load-bearing premise

The pair (A, B) has no Olšák polymorphism while still admitting a homomorphism from A to B.

What would settle it

A model of ZF set theory in which the ultrafilter principle fails but K_(K3, K5) still holds would falsify the claimed equivalence.

read the original abstract

For a pair of finite relational structures $(\mathfrak{A},\mathfrak{B})$ such that $\mathfrak{A}$ homomorphically maps to $\mathfrak{B}$ we denote by $K_{(\mathfrak{A},\mathfrak{B})}$ the following statement: for all structures $\mathfrak{I}$ with the same signature as $\mathfrak{A}$ if all finite substructures of $\mathfrak{I}$ homomorphically maps to $\mathfrak{A}$ then $\mathfrak{I}$ homomorphically maps to $\mathfrak{B}$. In this article, we show that if $(\mathfrak{A},\mathfrak{B})$ has no Ol\v{s}\'{a}k polymorphism, then $K_{(\mathfrak{A},\mathfrak{B})}$ is equivalent to the ultrafilter principle over $\operatorname{ZF}$. This includes the statements $K_{(K_3,K_5)}$ and $K_{(H_2,H_c)}$ for all $c\geq 2$ where $K_n$ denotes the clique of size $n$ and $H_k$ denotes the ternary not-all-equal structure on a $k$-element set. This means, for example, that in any $\operatorname{ZF}$ model, if every finitely 3-colourable graph can be coloured by 5 colours then all these graphs can in fact be coloured by 3 colours.

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 paper proves that for finite relational structures 𝔄 and 𝔅 with a homomorphism from 𝔄 to 𝔅 and no Olšák polymorphism, the promise compactness principle K_{(𝔄,𝔅)} is equivalent over ZF to the ultrafilter principle. Concrete instances include K_{(K_3,K_5)} and K_{(H_2,H_c)} for c≥2, with the forward direction holding generally and the reverse obtained via the algebraic condition on polymorphisms.

Significance. If correct, the result supplies an algebraic criterion (absence of Olšák polymorphism) that characterizes when certain homomorphism compactness statements are equivalent to the ultrafilter principle in ZF. It yields concrete equivalences for graph coloring and not-all-equal structures, clarifying the set-theoretic strength of promise problems without choice and connecting polymorphism theory to compactness principles.

minor comments (3)
  1. [Abstract] Abstract, line 3: the phrase 'all finite substructures of 𝔄 homomorphically maps to 𝔄' contains a grammatical error ('maps' should be 'map'); this recurs in the statement of K_{(𝔄,𝔅)} and should be corrected for precision.
  2. [Introduction] The paper would benefit from an explicit statement of the two directions of the equivalence (K ⇒ UP and UP ⇒ K) in a single theorem, with the algebraic precondition isolated; currently the reverse direction is only sketched via the no-Olšák condition.
  3. [Section 2] Notation for the structures K_n and H_k is introduced in the abstract but not recalled with a formal definition before the examples; a short preliminary section or paragraph defining cliques and the not-all-equal relation would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript, the accurate summary of the main results, and the recommendation of minor revision. The referee's description correctly captures the algebraic condition (absence of Olšák polymorphisms) and the resulting equivalences to the ultrafilter principle, including the concrete cases for graph coloring and not-all-equal structures.

Circularity Check

0 steps flagged

No significant circularity; direct ZF equivalence proof

full rationale

The paper establishes an equivalence K_{(A,B)} ⇔ ultrafilter principle in ZF whenever (A,B) satisfies the algebraic precondition of having no Olšák polymorphism (with A → B). This is a standard model-theoretic reduction using the definitions of homomorphisms, polymorphisms, and finite relational structures; no step reduces by construction to a fitted parameter, self-definition, or load-bearing self-citation. The concrete instances (K_{(K3,K5)}, K_{(H2,Hc)}) are immediate corollaries of the general theorem rather than independent derivations that loop back to the inputs. The argument is self-contained against external ZF benchmarks and does not rename known results or smuggle ansatzes via citation.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the standard axioms of ZF set theory together with the definitions of relational structures, homomorphisms, and Olšák polymorphisms; no free parameters or invented entities are introduced.

axioms (1)
  • standard math ZF set theory (Zermelo-Fraenkel without choice)
    The equivalence is proved inside ZF; invoked throughout the statement of the main theorem.

pith-pipeline@v0.9.0 · 5516 in / 1284 out tokens · 38773 ms · 2026-05-10T16:55:29.284482+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

29 extracted references · 29 canonical work pages · 2 internal anchors

  1. [1]

    Hardness of 4-colouring g -colourable graphs

    Sergey Avvakumov, Marek Filakovsk \'y , Jakub Opr s al, Gianluca Tasinato, and Uli Wagner. Hardness of 4-colouring g -colourable graphs. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages 72--83, 2025

    work page 2025

  2. [2]

    (2+ )- Sat is NP -hard

    Per Austrin, Venkatesan Guruswami, and Johan H stad. (2+ )- Sat is NP -hard. SIAM Journal on Computing , 46(5):1554--1573, 2017

    work page 2017

  3. [3]

    Algebraic approach to promise constraint satisfaction

    Libor Barto, Jakub Bul \' n, Andrei Krokhin, and Jakub Opr s al. Algebraic approach to promise constraint satisfaction. Journal of the ACM (JACM) , 68(4):1--66, 2021

    work page 2021

  4. [4]

    New hardness results for graph and hypergraph colorings

    Joshua Brakensiek and Venkatesan Guruswami. New hardness results for graph and hypergraph colorings. In 31st Conference on Computational Complexity (CCC 2016) , pages 14--1. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2016

    work page 2016

  5. [5]

    Promise constraint satisfaction: Structure theory and a symmetric boolean dichotomy

    Joshua Brakensiek and Venkatesan Guruswami. Promise constraint satisfaction: Structure theory and a symmetric boolean dichotomy. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1782--1801. SIAM, 2018

    work page 2018

  6. [6]

    Absorbing subalgebras, cyclic terms and the constraint satisfaction problem

    Libor Barto and Marcin Kozik. Absorbing subalgebras, cyclic terms and the constraint satisfaction problem. Logical Methods in Computer Science , 8/1(07):1--26, 2012

    work page 2012

  7. [7]

    Combinatorial gap theorem and reductions between promise CSPs

    Libor Barto and Marcin Kozik. Combinatorial gap theorem and reductions between promise CSPs . In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1204--1220. SIAM, 2022

    work page 2022

  8. [8]

    Krokhin, and Jakub Opr s al

    Jakub Bul \' n, Andrei A. Krokhin, and Jakub Opr s al. Algebraic approach to promise constraint satisfaction. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019 , pages 602--613, 2019

    work page 2019

  9. [9]

    Complexity of infinite-domain constraint satisfaction , volume 52

    Manuel Bodirsky. Complexity of infinite-domain constraint satisfaction , volume 52. Cambridge University Press, 2021

    work page 2021

  10. [10]

    The wonderland of reflections

    Libor Barto, Jakub Opr s al, and Michael Pinsker. The wonderland of reflections. Israel Journal of Mathematics , 223(1):363--398, 2018

    work page 2018

  11. [11]

    When Darwin met Ianus: dichotomies of expressivity

    Johanna Brunar, Michael Pinsker, and Moritz Sch \"o bi. Janus-faces of temporal constraint languages: a dichotomy of expressivity. arXiv preprint arXiv:2509.04347 , 2025

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  12. [12]

    Andrei A. Bulatov. A dichotomy theorem for nonuniform CSP s. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017 , pages 319--330, 2017

    work page 2017

  13. [13]

    The hardness of 3-uniform hypergraph coloring

    Irit Dinur*, Oded Regev, and Clifford Smyth. The hardness of 3-uniform hypergraph coloring. Combinatorica , 25(5):519--535, 2005

    work page 2005

  14. [14]

    Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs

    Marek Filakovsk \'y , Tamio-Vesa Nakajima, Jakub Opr s al, Gianluca Tasinato, and Uli Wagner. Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs. ACM Transactions on Computation Theory , 2023

    work page 2023

  15. [15]

    Tom\'as Feder and Moshe Y. Vardi. The computational structure of monotone monadic SNP and constraint satisfaction: a study through D atalog and group theory. SIAM Journal on Computing , 28:57--104, 1999

    work page 1999

  16. [16]

    R. J. Gauntt. Axiom of choice for finite sets -- a solution to a problem of Mostowski . Notices Amer. Math. Soc. 17 , page 474, 1970

    work page 1970

  17. [17]

    The complexity of near-optimal graph coloring

    Michael R Garey and David S Johnson. The complexity of near-optimal graph coloring. Journal of the ACM (JACM) , 23(1):43--49, 1976

    work page 1976

  18. [18]

    On the hardness of 4-coloring a 3-colorable graph

    Venkatesan Guruswami and Sanjeev Khanna. On the hardness of 4-coloring a 3-colorable graph. SIAM Journal on Discrete Mathematics , 18(1):30--40, 2004

    work page 2004

  19. [19]

    Improved hardness of approximating chromatic number

    Sangxia Huang. Improved hardness of approximating chromatic number. In International Workshop on Approximation Algorithms for Combinatorial Optimization , pages 233--243. Springer, 2013

    work page 2013

  20. [20]

    About the axiom of choice

    Thomas J Jech. About the axiom of choice. In Studies in Logic and the Foundations of Mathematics , volume 90, pages 345--370. Elsevier, 1977

    work page 1977

  21. [21]

    Topology and adjunction in promise constraint satisfaction

    Andrei Krokhin, Jakub Opr s al, Marcin Wrochna, and Stanislav Z ivn \'y . Topology and adjunction in promise constraint satisfaction. SIAM Journal on Computing , 52(1):38--79, 2023

    work page 2023

  22. [22]

    The csp dichotomy, the axiom of choice, and cyclic polymorphisms

    Tam \'a s K \'a tay, L \'a szl \'o M \'a rton T \'o th, and Zolt \'a n Vidny \'a nszky. The CSP dichotomy, the axiom of choice, and cyclic polymorphisms. arXiv preprint arXiv:2310.00514 , 2023

    work page arXiv 2023

  23. [23]

    Coloring infinite graphs and the boolean prime ideal theorem

    Hans L \"a uchli. Coloring infinite graphs and the boolean prime ideal theorem. Israel Journal of Mathematics , 9:422--429, 1971

    work page 1971

  24. [24]

    Complexity of approximate conflict-free, linearly-ordered, and nonmonochromatic hypergraph colourings

    Tamio-Vesa Nakajima, Zephyr Verwimp, Marcin Wrochna, and Stanislav Z ivn \'y . Complexity of approximate conflict-free, linearly-ordered, and nonmonochromatic hypergraph colourings. arXiv preprint arXiv:2501.12062 , 2025

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  25. [25]

    The weakest nontrivial idempotent equations

    Miroslav Ol s \'a k. The weakest nontrivial idempotent equations. Bulletin of the London Mathematical Society , 49(6):1028--1047, 2017

    work page 2017

  26. [26]

    Logical compactness and constraint satisfaction problems

    Danny Rorabaugh, Claude Tardif, and David Wehlau. Logical compactness and constraint satisfaction problems. Logical Methods in Computer Science , 13, 2017

    work page 2017

  27. [27]

    Mark H. Siggers. A strong M al'cev condition for varieties omitting the unary type. Algebra Universalis , 64(1):15--20, 2010

    work page 2010

  28. [28]

    Constraint satisfaction problems, compactness and non-measurable sets

    Claude Tardif. Constraint satisfaction problems, compactness and non-measurable sets. arXiv preprint arXiv:2508.14838 , 2025

    work page arXiv 2025

  29. [29]

    A proof of the CSP dichotomy conjecture

    Dmitriy Zhuk. A proof of the CSP dichotomy conjecture. Journal of the ACM (JACM) , 67(5):1--78, 2020

    work page 2020