Pith. sign in

REVIEW 2 major objections 5 minor 14 references

A Resolution of Erd\H{o}s Problems 593 and 1177: Obligatory Triple Systems and Exact Spectra

T0 review · 2 major / 5 minor · reviewed 2026-08-02 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Every finite triple system is either forced in all uncountably chromatic hosts or avoidable at every uncountable chromatic number.

desk verdict The Part I classification is a real solution to Erdős #593 and looks right; the exact-spectrum half is credible but leans on an imported EGH quantifier and an unshipped Lean-4 claim that a referee should check. read the letter →

arxiv 2606.24882 v2 pith:BKQXVFIM submitted 2026-06-23 math.CO

Eric Li (Trinity College , University of Cambridge) This is my paper · ORCID
classification math.CO MSC 05C6505C1503E0505D10
keywords obligatorytriplesystemsuncountablechromaticnumberLevigraphBergecycleexactspectrumlinearprivate-vertexexpansionbridgeselector
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper attempts to settle two long-standing questions about which finite triple systems must appear in every triple system of uncountable chromatic number. It claims a full classification: a finite triple system is obligatory exactly when, after deleting isolated vertices, it is linear, every hyperedge-node of its Levi graph is incident with a bridge, and every Berge cycle has even length. Equivalently, it belongs to the class built from private-vertex expansions of finite bipartite graphs by disjoint unions and one-point amalgamations. The paper further constructs, for every uncountable cardinal, a linear triple system of exactly that chromatic number, which yields a dichotomy for exact avoidance spectra: either no uncountably chromatic F-free system exists, or such systems exist at every uncountable cardinal. If correct, this resolves Problems 593 and 1177 with the truth values yes, no, yes.

What carries the argument

The carrying object is the complete-rank one-apex sequence lift Lift(A,κ): its vertices are pairs (σ,x), where σ is a transfinite sequence of edges of a graph A and x is a vertex of A, and its triples consist of two vertices on a common sequence node and a third vertex on a proper extension whose next edge is the base pair. This lift transfers the chromatic number of A to a linear triple system, and the bridge-trace theorem characterises exactly which finite linear systems embed into it. On the finite side, the bridge selector and the graph derivative of each component of the Levi graph after deleting selected bridges turn the embeddability question into an embedding problem for ordinary gra

What would settle it

Find one uncountable cardinal λ and one finite triple system F outside the classified class for which no F-free triple system of exact chromatic number λ exists; or exhibit a colouring of the imported edge-labelled graph on 2^ℵ0 vertices with fewer than the required number of colours but no single colour class hitting every label. Either observation would refute the spectrum dichotomy.

Watch

Extended reading notes

Core claim

The central claim is that obligatoriness of finite triple systems is a purely finite, checkable property. The proof shows that every obligatory finite triple system admits a bridge selector — one chosen Levi-graph bridge at every hyperedge-node — and that after deleting these incidences, the remaining components are private-vertex expansions of bipartite graph derivatives; the original system is rebuilt by gluing these pieces along at most one point at a time. Conversely, every system built this way is shown obligatory, using the fact that private-vertex expansions of complete bipartite graphs are obligatory and that obligatoriness is closed under subhypergraphs, disjoint unions, and one-poi

Load-bearing premise

The lower-bound half of the exact-calibration construction depends on an imported simultaneous edge-labelling property whose strong quantifier order — one colour class must contain an edge of every label — is not proved in this paper; if only a weaker label-by-label version holds, the argument that every colouring with fewer than κ colours fails would collapse.

Editorial extensions

If this is right

  • If the classification is correct, recognition of obligatory finite triple systems reduces to checking linearity, locating Levi bridges, and testing derivatives for bipartiteness — an essentially linear-time criterion once linearity is certified.
  • Every non-obligatory finite triple system is avoidable at every uncountable cardinal, so the exact avoidance spectrum has only two possible values: empty or all uncountable cardinals.
  • The three clauses of Problem 1177 are settled: a small witness exists when one ℵ1-witness exists; some pairs of forbidden systems have nonempty but disjoint ℵ1-avoidance classes; and existence at one uncountable cardinal transfers to all uncountable cardinals.
  • Every obligatory finite triple system is strongly tripartite, and the loose 7-cycle is linearly obligatory without being obligatory, showing linearity is essential in the exact spectrum statement.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A natural next step is to test whether the same bridge-selector/derivative decomposition generalises to k-uniform hypergraphs for k>3; the private-vertex expansions of bipartite graphs would be a first candidate for the positive atoms.
  • The reservoir-recursion calibration is a reusable template: it should be possible to force additional avoidance properties in the constructed exact-κ systems by choosing the base graph A with prescribed odd girth, giving fine control over which Berge cycles are omitted.
  • The dichotomy suggests a broader heuristic for hereditary hypergraph properties: a finite configuration that fails to be unavoidable at one uncountable chromatic cardinal may be avoidable at all of them; testing this for other classes would clarify how common the all-or-nothing spectrum is.
  • The paper asserts all results are machine-checked; if that claim is audited, the classification and spectrum theorem become machine-checked mathematics. Until then, the human proof of the lower-bound lemma carries the weight.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper claims to resolve two Erdős problems. Part I gives a structural classification of obligatory finite triple systems (Theorems 1.1/5.7): F is obligatory iff F∈B iff, after deleting isolated vertices, F is linear, every hyperedge-node of I(F) is incident with a bridge, and every Berge cycle is even. Part II constructs, for every uncountable cardinal κ, a linear triple system of chromatic number exactly κ (Theorem 6.14 / Corollary 6.16), and combines this with Part I to obtain an exact-spectrum dichotomy (Corollary 7.1) and the three answers to Problem #1177 (Corollary 7.2). The proofs use a bridge-trace theorem for sequence lifts and a transfinite reservoir construction over labelled Specker graphs. The abstract asserts complete Lean-4 formal verification, but no artifact or description is supplied.

Significance. If correct, the paper is a major contribution to infinite combinatorics. The classification is explicit, intrinsic, and efficiently recognizable (Remark 5.10), and the exact-calibration theorem provides ZFC constructions at every uncountable cardinal. The paper is unusually transparent about external dependencies, listing them in Section 2.2 and Appendix A. The central internal proofs are detailed and coherent. The main reservations are the unverifiable formal-verification claim and the reliance on a strong imported quantifier-order property for the exact-calibration lower bound.

major comments (2)
  1. [Abstract and entire manuscript] The sentence "All results of this paper have been formally verified in Lean-4" is unsupported. The manuscript contains no Lean code, no repository identifier, no build instructions, and no description of which imported theorems are formalized versus assumed as axioms. This is an extraordinary claim that cannot be checked. Please either provide the artifact with precise instructions and an axiom ledger, or remove the claim from the abstract.
  2. [§6.3, Lemma 6.13, Appendix A.3] The lower bound χ(Lκ)≥κ relies on applying the common-colour form of property P to the captured copy B. The argument needs the quantifier order ∀c∃a∀i∃e: if the imported theorem only gives per-label colours ∀i∃a_i, the edge of label i_a could lie in a different colour class and the construction would not yield a monochromatic triple. Appendix A.3 asserts that [7, Definition 6.2] has exactly the strong form, but it does not reproduce the original text, and no Lean artifact covers the import. Please quote the relevant passage from [7] verbatim, or supply a formal certificate, so that this load-bearing premise is auditable.
minor comments (5)
  1. [Corollary 1.4] The sentence "The three assertions ... have truth values yes, no, and yes" followed by the bullet list is confusing. Bullet (2) states the existence of a counterexample, which is a true statement, yet the verdict for the original assertion (2) is "no". Please clarify that the bullets are the resolutions (including the counterexample), while the "yes/no/yes" applies to the original Problem #1177 formulations.
  2. [§6.1 after Theorem 6.3] The statement "Since S is a simple graph on the infinite cardinal ρ, it has at most ρ edges" relies on ρ^2=ρ. It would be clearer to mention this explicitly.
  3. [Appendix A.1] In the specialization of the Erdős–Hajnal–Rothschild theorem, the parameter β=ω^ξ should specify ξ>0 so that the resulting linear system is uncountably chromatic.
  4. [Lemma 6.8] The phrase "there are at most Λ choices for X_i, including the empty choice" would be clearer if it said there are 1 + |[V_{<α}]^ρ| ≤ 1 + Λ^ρ = Λ choices.
  5. [Corollary 7.2 Part (2)] In the definition of T0, state explicitly that c≠d (the two triples are distinct).

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the derivation chain reduces to its own lemmas and to genuinely external imported theorems, not to the target results.

full rationale

The central classification (Theorem 5.7) is not circular. The equivalence (ii)⇔(iii) is proved as Proposition 5.4 from internal structural lemmas (bridge selector, cycle–selector correspondence, quotient forest, expansion pieces, running-intersection), and the step from B to obligatoriness uses Reiher's theorem as an external positive atom together with closure lemmas proved in the paper. The negative half uses external Erdős–Hajnal–Rothschild and Erdős–Hajnal graphs plus the internally proved bridge-trace theorem; none of these is identified with the conclusion. Part II's exact calibration is likewise non-circular: Theorem 6.3 imports an external Erdős–Galvin–Hajnal property P with a strong common-colour quantifier, and Lemma 6.13 applies that property to a captured labelled copy to force a monochromatic triple. This is a premise-to-conclusion use of an external result, not a fitted parameter renamed as a prediction, and not a self-citation. The paper contains no load-bearing author self-citations; the imported results are external and would be independent evidence if the source statements are correct. The notable caveats—the EGH property is not quoted verbatim and the claimed Lean-4 artifact is not shipped—are soundness/verification risks about the imports, not circularity of the derivation. Even if the strong quantifier order were not supplied by the source, that would falsify an imported premise rather than make the paper's construction equivalent to its inputs. Thus no circular step is exhibited, and the honest finding is score 0.

Assumptions & free parameters 0 free parameters · 7 assumptions · 2 invented entities

No fitted parameters appear: the cardinal parameters are bound variables or inputs, and nothing is tuned to data. The central claims rest on five imported external theorems recorded in §2.2; these are not self-citations. The new mathematical objects are explicit constructions whose properties are proved, so they do not carry an independent-evidence burden in the sense used for empirical entities.

assumptions (7)
  • domain assumption Erdős–Hajnal–Rothschild obstruction (E1): a finite uniform hypergraph with two edges meeting in at least two vertices is non-obligatory.
    Used as Theorem 2.2 to eliminate nonlinear obligatory systems; imported from [4] without proof.
  • domain assumption Erdős–Hajnal exact high odd girth (E2): for every uncountable κ and positive integer s, there is an exact-κ graph with no odd cycle of length at most 2s+1.
    Used in the positive-obstruction case where F has an odd Berge cycle; imported from [8] via [7, Theorem C].
  • domain assumption Erdős–Galvin–Hajnal property P for GS2(ρ) (E3): a single colour class can contain an edge of every label for every colouring with fewer than δ(ρ) colours.
    Needed for the exact lower bound in the Lκ construction (Lemma 6.13); the strong quantifier order is load-bearing.
  • domain assumption Reiher's theorem (E4): K+_{n,n} is obligatory for every positive n.
    The positive atom for the classification; used in Theorem 5.7 to show bipartite expansions are obligatory.
  • domain assumption Hajnal–Komjáth theorem (E5): the loose cycle C7^(3) is linearly obligatory.
    Used only in Problem #1177(2) to force C7^(3) in every uncountably chromatic linear triple system.
  • standard math de Bruijn–Erdős compactness for finite graph colourings.
    Used in Lemma 5.5 to prove closure of obligatory systems under one-point amalgamation.
  • standard math ZFC transfinite recursion and cardinal arithmetic facts (e.g., cf(2^μ)>μ, (2^ρ)^ρ=2^ρ).
    Used throughout Part II for the reservoir construction and exact cardinal bounds.
invented entities (2)
  • Complete-rank one-apex lift Lift(A,κ)
    purpose: Host triple system with prescribed chromatic number that omits specified finite forbidden systems.
    Defined in §3; existence and chromatic properties are proved as Theorem 3.2. It is an explicit construction, not an ungrounded physical postulate.
  • Transfinite reservoir system Lκ
    purpose: Exact-κ linear triple system used for the exact avoidance spectrum.
    Defined by transfinite recursion in §6.3; linearity and exact chromatic number are proved in Lemmas 6.10–6.13.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Resolution of Erd\H{o}s Problems 593 and 1177: Obligatory Triple Systems and Exact Spectra." pith.science (2026). https://pith.science/paper/BKQXVFIM

@misc{pith2026260624882,
  author       = {Pith},
  title        = {Pith review of: A Resolution of Erd\Hos Problems 593 and 1177: Obligatory Triple Systems and Exact Spectra},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BKQXVFIM}},
  note         = {Machine review of arXiv:2606.24882}
}
read the original abstract

We resolve Erd\H{o}s Problems #593 and #1177. Problem #593 asks which finite triple systems occur in every uncountably chromatic triple system; the answer is exactly the class generated from private-vertex expansions of finite bipartite graphs by finite disjoint unions and one-point amalgamations. Equivalently, after isolated vertices are removed, a finite triple system is obligatory precisely when it is linear, every hyperedge-node of its Levi graph has an incident bridge, and every Berge cycle is even. The proof uses an exact bridge-trace theorem for complete-rank one-apex sequence lifts. We also prove that, for every uncountable cardinal kappa, there is a linear triple system of chromatic number exactly kappa, with at most 2^{2^mu} vertices when kappa=mu^+. These two ingredients give a class-valued exact avoidance-spectrum dichotomy for every finite forbidden triple system. As a consequence, Erd\H{o}s Problem #1177 has truth values yes, no, and yes. All results of this paper have been formally verified in Lean-4.

Figures

Figures reproduced from arXiv: 2606.24882 by the authors.

Figure 1
Figure 1. The Levi graph and quotient forest from Example 5.3. Rooting the quotient at C1, one reconstructs F by taking FC1 first, amalgamating FC0 at v, amalgamating FC2 at d, and finally amalgamating FC3 at q. The inactive component U contributes no edge. This example exhibits attachment through both an active component and an inactive singleton point component. Proposition 5.4 (Finite bridge decomposition). For a finite tr… view at source ↗

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

14 extracted references · 5 canonical work pages

  1. [7]

    Erdős, F

    P. Erdős, F. Galvin, and A. Hajnal,On set-systems having large chromatic number and not containing prescribed subsystems, inInfinite and Finite Sets(Keszthely, 1973), Colloq. Math. Soc. János Bolyai, vol. 10, North-Holland, 1975, pp. 425–513

    1973

  2. [1]

    N. G. de Bruijn and P. Erdős,A colour problem for infinite graphs and a problem in the theory of relations, Nederl. Akad. Wetensch. Proc. Ser. A54= Indag. Math.13(1951), 369–373

    1951

  3. [2]

    Erdős,On some problems in combinatorial set theory, Publ

    P. Erdős,On some problems in combinatorial set theory, Publ. Inst. Math. (Beograd) (N.S.)57(71)(1995), 61–65

    1995

  4. [3]

    T. F. Bloom,Erdős Problem #593, Erdős Problems,https://www.erdosproblems.com/593, accessed 23 June 2026

    2026

  5. [4]

    Erdős, A

    P. Erdős, A. Hajnal, and B. L. Rothschild,On chromatic number of graphs and set-systems, inCambridge Summer School in Mathematical Logic(Cambridge, 1971), Lecture Notes in Mathematics, vol. 337, Springer, Berlin–New York, 1973, pp. 531–538

    1971

  6. [5]

    Bollobás et al

    B. Bollobás et al. (collectors),Some of Paul’s Favorite Problems, booklet circulated at the conferencePaul Erdős and his Mathematics, Budapest, July 1999, Problem 7.94, p. 14,https://web.math.pmf.unizg.hr/~vjekovac/ EP/Some_of_Pauls_favorite_problems.pdf

    1999

  7. [6]

    T. F. Bloom,Erdős Problem #1177, Erdős Problems,https://www.erdosproblems.com/1177, accessed 23 June 2026

    2026

  8. [8]

    Erdős and A

    P. Erdős and A. Hajnal,On chromatic number of graphs and set-systems, Acta Math. Acad. Sci. Hungar.17 (1966), 61–99, doi:10.1007/BF02020444

    work page doi:10.1007/bf02020444 1966

Show all 14 references
  1. [9]

    Hajnal and P

    A. Hajnal and P. Komjáth,Obligatory subsystems of triple systems, Acta Math. Hungar.119(2008), no. 1–2, 1–13, doi:10.1007/s10474-007-6231-2

    2008 doi

  2. [10]

    Komjáth,An uncountably chromatic triple system, Acta Math

    P. Komjáth,An uncountably chromatic triple system, Acta Math. Hungar.121(2008), no. 1–2, 79–92, doi:10.1007/s10474-008-7179-6

    2008 doi

  3. [11]

    Komjáth,Some remarks on obligatory subsystems of uncountably chromatic triple systems, Combinatorica21 (2001), no

    P. Komjáth,Some remarks on obligatory subsystems of uncountably chromatic triple systems, Combinatorica21 (2001), no. 2, 233–238, doi:10.1007/s004930100021

    2001 doi

  4. [12]

    Y. Wang, M. Duan, D. Gerbner, and H. Hama Karim,On the largest chromatic number ofF-free hypergraphs, preprint, 2026, arXiv:2604.21551

    2026 arXiv

  5. [13]

    Reiher,Obligatory hypergraphs, Proc

    C. Reiher,Obligatory hypergraphs, Proc. Amer. Math. Soc., to appear, doi:10.1090/proc/17021

    doi

  6. [14]

    Reiher,Graphs of large girth, preprint, 2024, arXiv:2403.13571

    C. Reiher,Graphs of large girth, preprint, 2024, arXiv:2403.13571

    2024 arXiv

Pith tools

Reviewed August 2, 2026 · model on record in the stance chip above.