pith. sign in

arxiv: 2604.09894 · v2 · submitted 2026-04-10 · 🧮 math.LO

The Henson graphs: colorings and codings

Peter Cholak , Natasha Dobrinen , Charlie McCoy This is my paper

Pith reviewed 2026-05-10 15:52 UTC · model grok-4.3

classification 🧮 math.LO
keywords Henson graphsbig Ramsey degreescomputable coloringshomogeneous structurescomputability theoryjump operatorclique-free graphsRamsey theory
0
0 comments X

The pith

For any finite G with at least two vertices in a Henson graph, a computable coloring of its copies exists such that every minimal-color subcopy computes the (|G|-1)th jump of the empty set.

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

The paper shows that the exact finite big Ramsey degrees known for the Henson graphs can be realized by finite computable colorings of the copies of any fixed finite subgraph G. When G has size at least two, every copy of the full Henson graph that uses only the minimal number of colors on those subgraphs must compute a high iterate of the jump of the empty set and therefore the halting set. This connects the combinatorial minimality guaranteed by big Ramsey degrees directly to the arithmetic hierarchy inside the structure itself. A sympathetic reader cares because the result exhibits an explicit coding mechanism by which color assignments in an infinite graph force computational strength without extra hypotheses.

Core claim

If |G| ≥ 2, then there exists a finite computable coloring C of the copies of G in the Henson graph H_{n+1} such that every substructure tilde H isomorphic to H_{n+1} that realizes at most k(G,n) colors on the copies of G computes the (|G|-1)th jump of the empty set (and hence the halting set).

What carries the argument

Exact finite big Ramsey degree k(G,n) realized by a finite computable coloring that forces jump computation in all minimal subcopies.

If this is right

  • Every copy of the Henson graph that minimizes the colors on G must compute the halting set whenever |G| ≥ 2.
  • The forcing holds uniformly across all n and all such finite G.
  • Computable colorings alone suffice to embed this arithmetic information into the minimal substructures.
  • The construction supplies a concrete coding from color classes into the arithmetic hierarchy.

Where Pith is reading between the lines

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

  • The same coding technique might separate computability degrees inside other Fraisse limits that possess exact big Ramsey degrees.
  • One could test whether non-computable colorings can force strictly higher jumps or other invariants.
  • The result suggests examining the computable content of the minimal number k(G,n) itself across different homogeneous structures.

Load-bearing premise

The exact big Ramsey degree from prior work can be achieved by some finite computable coloring that additionally forces every minimal subcopy to compute the required jump.

What would settle it

For some fixed G with |G| ≥ 2, produce a computable coloring that achieves the exact degree k(G,n) yet admits at least one tilde H using only k colors whose degree does not compute empty to the power |G|-1.

read the original abstract

By recent work of \citet{DobrinenICM} and \citet{Balko7} we know that every finite $G$ in the Henson graph $\mathbb{H}_{n+1}$ (the universal ultrahomogeneous $(n+1)$-clique free graph) has exact finite big Ramsey degree $k({G,n})$. That is, there is a positive integer $k({G,n})$ such that for each finite coloring $C$ of the copies of $G$ in $\mathbb{H}_{n+1}$, there is $\tilde{\mathbb{H}}$, a substructure of $\mathbb{H}_{n+1}$ and isomorphic to $\mathbb{H}_{n+1}$, such that in $\tilde{\mathbb{H}}$ at most $k({G,n})$ colors are used on the copies of $G$ in $\tilde{\mathbb{H}}$. Moreover, for exactness, for some coloring and all corresponding $\tilde{\mathbb{H}}$, all $k({G,n})$ colors are needed. The ultimate result here is that if $|G|\geq 2$, then there is a finite computable coloring $C$ such that, for all such $\tilde{\mathbb{H}}$, we have that $\tilde{\mathbb{H}}$ computes $\emptyset^{(|G|-1)}$ (and hence the halting set).

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

2 major / 2 minor

Summary. The paper claims that every finite G in the Henson graph H_{n+1} has exact finite big Ramsey degree k(G,n) by prior results of Dobrinen and Balko. It further asserts that when |G| >= 2 there exists a finite computable coloring C of the copies of G such that every isomorphic copy tilde H realizing exactly k(G,n) colors computes the (|G|-1)th Turing jump of the empty set (hence the halting problem).

Significance. If the central construction holds, the result links exact big Ramsey degrees with computability by exhibiting computable minimal colorings that encode arithmetic information. It strengthens the non-effective partition theorems cited in the abstract by adding an effective coding step that forces computational strength into the color classes while preserving exactness. This is a substantive contribution at the interface of Ramsey theory and computability, provided the forcing construction is fully rigorous.

major comments (2)
  1. [main construction (likely §3 or the proof of the ultimate theorem)] The load-bearing step is the explicit construction of a computable finite coloring C that simultaneously (i) realizes the exact degree k(G,n) in every minimal tilde H and (ii) arranges the color distinctions so that any such tilde H computes empty^{(|G|-1)}. The abstract recalls the non-effective existence from DobrinenICM and Balko7 but does not indicate how the new computable C is built without increasing the number of colors used in some copies or violating the exactness property; this transition requires a detailed, self-contained argument.
  2. [proof that tilde H computes the jump] It is not shown that the coding of the jump is compatible with the minimality condition. Concretely, the argument must demonstrate that any tilde H using only the k(G,n) colors of C is forced to solve the jump computation, while still satisfying the universal property that some tilde H uses at most k colors; without an explicit description of how the color classes are defined (e.g., via a computable enumeration or forcing condition), the claim that tilde H computes empty^{(|G|-1)} remains under-supported.
minor comments (2)
  1. [abstract] Notation for copies (tilde H, tilde H) and colorings should be standardized throughout; the abstract uses both tilde H and tilde{H} inconsistently.
  2. [statement of main theorem] The statement 'finite computable coloring C' should specify the domain (copies of G inside H_{n+1}) and the range (a finite set of colors) more explicitly to avoid ambiguity about what 'computable' means for an infinite structure.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their detailed and constructive report. The comments highlight the need for greater explicitness in the construction and its compatibility with minimality, which we address below. We will incorporate expanded explanations and a self-contained description of the computable coloring into the revised manuscript.

read point-by-point responses

  1. Referee: The load-bearing step is the explicit construction of a computable finite coloring C that simultaneously (i) realizes the exact degree k(G,n) in every minimal tilde H and (ii) arranges the color distinctions so that any such tilde H computes empty^{(|G|-1)}. The abstract recalls the non-effective existence from DobrinenICM and Balko7 but does not indicate how the new computable C is built without increasing the number of colors used in some copies or violating the exactness property; this transition requires a detailed, self-contained argument.

    Authors: We agree that the transition from the non-effective results to the computable coloring requires a more self-contained presentation. Section 3 constructs C via a computable enumeration of potential copies of G, combined with a forcing condition that assigns colors from a fixed finite palette of size k(G,n) while embedding the jump information into the color classes. The exactness is preserved because the forcing ensures that every minimal tilde H must use all k colors (by the cited partition theorems), and the computability of C does not increase the number of colors used in minimal copies. We will revise the manuscript to include a detailed, standalone exposition of this enumeration and forcing condition, making the argument independent of external references for the computable step. revision: yes

  2. Referee: It is not shown that the coding of the jump is compatible with the minimality condition. Concretely, the argument must demonstrate that any tilde H using only the k(G,n) colors of C is forced to solve the jump computation, while still satisfying the universal property that some tilde H uses at most k colors; without an explicit description of how the color classes are defined (e.g., via a computable enumeration or forcing condition), the claim that tilde H computes empty^{(|G|-1)} remains under-supported.

    Authors: The manuscript's proof establishes compatibility by showing that the color classes are defined so that the distinctions between the k colors directly code the oracle queries for the (|G|-1)th jump; any tilde H realizing exactly k colors must contain, for each stage, a copy that decodes the next bit of the jump. The universal property (existence of some tilde H using at most k colors) is inherited from the non-effective theorems and is not disturbed by the computable coding, as the forcing condition is satisfied by the same minimal subcopies. We will revise the relevant proof subsection to provide an explicit description of the color-class definition via the computable enumeration and to include a lemma verifying that minimality forces the jump computation without violating the universal property. revision: yes

Circularity Check

0 steps flagged

No significant circularity; new computable coding construction is independent of cited background

full rationale

The paper cites external prior results (DobrinenICM, Balko7) solely for the existence of exact finite big Ramsey degrees k(G,n) as background. The central claim asserts existence of a finite computable coloring C that preserves exactness while forcing every corresponding tilde H to compute the (|G|-1)th jump. No equation, definition, or step in the abstract reduces this existence claim to a tautological redefinition, fit, or renaming of the cited k(G,n) values; the computability and coding properties are presented as a separate construction. Self-citation of overlapping authors is present but not load-bearing for the new result, which remains externally falsifiable via the explicit coloring.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on the standard definition of Henson graphs as universal ultrahomogeneous (n+1)-clique-free graphs and on the exact finite big Ramsey degree property established in the cited external papers.

axioms (2)
  • domain assumption The Henson graph H_{n+1} is the universal ultrahomogeneous (n+1)-clique free graph.
    Standard background definition invoked in the abstract.
  • domain assumption Every finite G has an exact finite big Ramsey degree k(G,n).
    Invoked directly from the cited works of DobrinenICM and Balko7.

pith-pipeline@v0.9.0 · 5534 in / 1422 out tokens · 49108 ms · 2026-05-10T15:52:29.775655+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

15 extracted references · 15 canonical work pages

  1. [1]

    Carlson-Simpson’s lemma and applications in reverse mathematics.Ann

    Paul-Elliot Anglès d’Auriac, Lu Liu, Bastien Mignoty, and Ludovic Patey. Carlson-Simpson’s lemma and applications in reverse mathematics.Ann. Pure Appl. Logic, 174(9):Paper No. 103287, 16 pp., 2023

    work page 2023

  2. [2]

    Balko, D

    M. Balko, D. Chodounský, N. Dobrinen, J. Hubička, M. Konečný, L. Vena, and A. Zucker. Exact big Ramsey degrees for finitely constrained binary free amalgamation classes.J. Eur. Math. Soc., 28(5):2101–2150, 2026

    work page 2026

  3. [3]

    The Ramsey theory of the universal homogeneous triangle-free graph Part II: Exact big Ramsey degrees, 2020

    Natasha Dobrinen. The Ramsey theory of the universal homogeneous triangle-free graph Part II: Exact big Ramsey degrees, 2020. URLhttps: //arxiv.org/abs/2009.01985

    work page arXiv 2020

  4. [4]

    The Ramsey theory of the universal homogeneous triangle-free graph.J

    Natasha Dobrinen. The Ramsey theory of the universal homogeneous triangle-free graph.J. Math. Log., 20(2):Paper No. 2050012, 75 pp, 2020

    work page 2020

  5. [5]

    TheRamseytheoryofHensongraphs.J.Math.Log.,23(1): Paper No

    NatashaDobrinen. TheRamseytheoryofHensongraphs.J.Math.Log.,23(1): Paper No. 2250018, 88 pp., 2023

    work page 2023

  6. [6]

    3, Sections 1–4, pages 1462–1486, 2023

    NatashaDobrinen.Ramseytheoryofhomogeneousstructures: currenttrends and open problems.ICM—International Congress of Mathematicians, Vol. 3, Sections 1–4, pages 1462–1486, 2023

    work page 2023

  7. [7]

    Infinite-dimensionalRamseytheoryfor binaryfreeamalgamationclasses,2023

    NatashaDobrinenandAndyZucker. Infinite-dimensionalRamseytheoryfor binaryfreeamalgamationclasses,2023. URLhttps://arxiv.org/abs/2303. 04246

    work page 2023

  8. [8]

    Theindivisibilityofthehomogeneous 𝐾𝑛-free graphs.Journal of Combinatorial Theory, Series B, 47(2):162–170, 1989

    MohamedEl-ZaharandNorbertSauer. Theindivisibilityofthehomogeneous 𝐾𝑛-free graphs.Journal of Combinatorial Theory, Series B, 47(2):162–170, 1989

    work page 1989

  9. [9]

    Graphs with monochromatic complete subgraphs in every edge coloring.SIAM J

    Jon Folkman. Graphs with monochromatic complete subgraphs in every edge coloring.SIAM J. Appl. Math., 18:19–24, 1970. ISSN 0036-1399. doi: 10.1137/0118004. URLhttps://doi.org/10.1137/0118004. 30 PETER CHOLAK, NATASHA DOBRINEN, AND CHARLES MCCOY

    work page doi:10.1137/0118004 1970

  10. [10]

    A note on the indivisibility of the Henson graphs, 2023

    Kenneth Gill. A note on the indivisibility of the Henson graphs, 2023. URL https://arxiv.org/abs/2310.20097

    work page arXiv 2023

  11. [11]

    Hirschfeldt and Carl G

    Denis R. Hirschfeldt and Carl G. Jockusch, Jr. On notions of computability- theoretic reduction betweenΠ 1 2 principles.J. Math. Log., 16(1):1650002, 59,

    work page

  12. [12]

    and Jockusch, Jr., Carl G

    ISSN 0219-0613,1793-6691. doi: 10.1142/S0219061316500021. URL https://doi.org/10.1142/S0219061316500021

    work page doi:10.1142/s0219061316500021

  13. [13]

    Ramsey’stheoremandrecursiontheory.J.SymbolicLogic, 37:268–280, 1972

    CarlG.Jockusch,Jr. Ramsey’stheoremandrecursiontheory.J.SymbolicLogic, 37:268–280, 1972

    work page 1972

  14. [14]

    Coloring of universal graphs.Graphs and Combinatorics, 2(1):55–60, 1986

    Péter Komjáth and Vojtěch Rödl. Coloring of universal graphs.Graphs and Combinatorics, 2(1):55–60, 1986

    work page 1986

  15. [15]

    E. Specker. Ramsey’s theorem does not hold in recursive set theory. InLogic Colloquium’69(Proc.SummerSchoolandColloq.,Manchester,1969),volumeVol. 61 ofStud. Logic Found. Math., pages 439–442. North-Holland, Amsterdam- London, 1971. University of Notre Dame Email address:cholak@nd.edu Email address:ndobrine@nd.edu Email address:cmccoy@holycrossusa.org

    work page 1969