pith. sign in

arxiv: 2606.24882 · v1 · pith:BKQXVFIMnew · submitted 2026-06-23 · 🧮 math.CO

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

Eric Li (Trinity College , University of Cambridge) This is my paper

Pith reviewed 2026-06-25 22:29 UTC · model grok-4.3

classification 🧮 math.CO
keywords triple systemshypergraph chromatic numberobligatory structuresLevi graphBerge cyclesErdős problemsavoidance spectrumone-point amalgamation
5
0 comments X

The pith

Finite triple systems occur in every uncountably chromatic triple system precisely when generated from private-vertex expansions of finite bipartite graphs by disjoint unions and one-point amalgamations.

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

The paper characterizes exactly which finite triple systems must appear inside every triple system of uncountable chromatic number. These are the systems obtained from private-vertex expansions of finite bipartite graphs through finite disjoint unions and one-point amalgamations; equivalently, after isolated vertices are removed, the linear systems in which every hyperedge-node of the Levi graph has an incident bridge and every Berge cycle is even. The same ingredients produce linear triple systems of every uncountable chromatic number κ (with vertex count at most 2^{2^μ} when κ equals μ^+) and thereby an exact class-valued avoidance-spectrum dichotomy for any finite forbidden triple system. This settles Erdős problem 593 outright and assigns the truth values yes, no, and yes to the three parts of problem 1177.

Core claim

The finite triple systems that are obligatory in every uncountably chromatic triple system are precisely 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 relies on an exact bridge-trace theorem for complete-rank one-apex sequence lifts. Together with the existence, for every uncountable cardinal κ, of a linear triple system of chromatic number exactly κ with at most 2^{2^μ} vertices when κ=μ^

What carries the argument

The exact bridge-trace theorem for complete-rank one-apex sequence lifts, which traces bridges to establish membership in the obligatory class.

If this is right

  • There exists a linear triple system of chromatic number exactly κ for every uncountable cardinal κ, with size at most 2^{2^μ} when κ=μ^+.
  • For every finite forbidden triple system the avoidance spectrum is exactly determined as a class of cardinals.
  • Erdős problem 1177 receives the answers yes, no, and yes.
  • The obligatory class is closed under the stated generative operations.

Where Pith is reading between the lines

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

  • The generative description via expansions, unions, and amalgamations supplies an explicit enumeration procedure for all obligatory systems of any given size.
  • The Levi-graph conditions (linearity, bridges, even Berge cycles) give a finite checkable criterion that could be applied directly to small candidate systems without constructing an ambient uncountably chromatic host.
  • The size bound 2^{2^μ} for chromatic number μ^+ leaves open whether smaller constructions exist under additional set-theoretic hypotheses.
  • The same bridge-trace technique might adapt to produce obligatory systems at other infinite cardinals beyond the uncountable case treated here.

Load-bearing premise

The characterization and the spectrum dichotomy rest on an exact bridge-trace theorem for complete-rank one-apex sequence lifts whose full statement and applicability conditions are invoked but not supplied.

What would settle it

A linear triple system in which every hyperedge-node of the Levi graph has an incident bridge and every Berge cycle is even, yet which fails to embed into some uncountably chromatic triple system (or the explicit failure of the bridge-trace theorem for the relevant lifts).

Figures

Figures reproduced from arXiv: 2606.24882 by Eric Li (Trinity College, University of Cambridge).

Figure 1
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… view at source ↗
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.

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

1 major / 0 minor

Summary. The manuscript resolves Erdős Problems #593 and #1177. Problem #593 is answered by characterizing the finite triple systems obligatory in every uncountably chromatic triple system as exactly the class generated from private-vertex expansions of finite bipartite graphs by finite disjoint unions and one-point amalgamations; equivalently, after removing isolated vertices, the system is linear, every hyperedge-node of its Levi graph has an incident bridge, and every Berge cycle is even. The proof invokes an exact bridge-trace theorem for complete-rank one-apex sequence lifts. The paper also proves that for every uncountable cardinal κ there exists a linear triple system of chromatic number exactly κ (of size at most 2^{2^μ} when κ=μ^+), yielding a class-valued exact avoidance-spectrum dichotomy for every finite forbidden triple system and implying that Erdős Problem #1177 has truth values yes, no, and yes.

Significance. If the central claims hold, the work supplies exact resolutions to two longstanding open problems in extremal hypergraph theory, including a precise structural characterization of obligatory triple systems and an exact spectrum dichotomy. These are high-impact results for the field.

major comments (1)
  1. [Abstract] Abstract: the resolution of both Erdős problems and the exact characterization rest on an exact bridge-trace theorem for complete-rank one-apex sequence lifts (invoked to establish the equivalence between the obligatory class and the private-vertex expansions of finite bipartite graphs under disjoint unions and one-point amalgamations). The abstract states that the proof uses this theorem but supplies neither its statement nor its proof. If the theorem does not hold, or if the one-apex lifts arising from the Levi graphs of the candidate triple systems fail the complete-rank or applicability hypotheses, then neither the obligatory characterization nor the class-valued spectrum dichotomy follows.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their thorough summary and for recognizing the potential impact of the resolutions to Erdős Problems #593 and #1177. We address the single major comment below.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the resolution of both Erdős problems and the exact characterization rest on an exact bridge-trace theorem for complete-rank one-apex sequence lifts (invoked to establish the equivalence between the obligatory class and the private-vertex expansions of finite bipartite graphs under disjoint unions and one-point amalgamations). The abstract states that the proof uses this theorem but supplies neither its statement nor its proof. If the theorem does not hold, or if the one-apex lifts arising from the Levi graphs of the candidate triple systems fail the complete-rank or applicability hypotheses, then neither the obligatory characterization nor the class-valued spectrum dichotomy follows.

    Authors: The exact bridge-trace theorem for complete-rank one-apex sequence lifts is fully stated, proved, and applied in Section 3 of the manuscript. There we also confirm that the one-apex lifts constructed from the Levi graphs of the candidate triple systems meet the complete-rank and applicability hypotheses. The abstract is a high-level summary of the proof architecture and does not contain the detailed statement of this auxiliary result, which is standard practice. We are prepared to expand the abstract with a concise statement of the theorem if the referee considers that necessary for clarity. revision: partial

Circularity Check

0 steps flagged

No circularity; claims rest on independent combinatorial theorem

full rationale

The paper characterizes obligatory triple systems via an exact bridge-trace theorem for complete-rank one-apex sequence lifts and derives the resolution of the Erdős problems from that theorem together with a construction of linear triple systems of prescribed uncountable chromatic number. No quoted step reduces by definition, by fitting, or by self-citation chain to the target result itself; the derivation is presented as a self-contained combinatorial argument whose load-bearing components are external to any re-derivation of the inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work is a pure set-theoretic combinatorics proof; it relies on standard axioms of ZFC set theory and basic facts about graphs and hypergraphs but introduces no new free parameters or invented entities visible in the abstract.

axioms (1)
  • standard math ZFC set theory
    Background foundation for all cardinal arithmetic and existence statements in the paper.

pith-pipeline@v0.9.1-grok · 5715 in / 1353 out tokens · 29946 ms · 2026-06-25T22:29:11.492711+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

14 extracted references · 5 canonical work pages

  1. [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

  2. [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

  3. [3]

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

    2026

  4. [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

  5. [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

  6. [6]

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

    2026

  7. [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

  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

  9. [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

    work page doi:10.1007/s10474-007-6231-2 2008

  10. [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

    work page doi:10.1007/s10474-008-7179-6 2008

  11. [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

    work page doi:10.1007/s004930100021 2001

  12. [12]

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

    Pith/arXiv arXiv 2026

  13. [13]

    Reiher,Obligatory hypergraphs, Proc

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

    work page doi:10.1090/proc/17021

  14. [14]

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

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

    arXiv 2024