Erdős Problem #111
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: graph theory, chromatic number, set theory.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The question in plain language
An infinite graph may require uncountably many colours, yet each of its finite subgraphs can be only moderately far from bipartite. A graph is bipartite if its vertices can be coloured with two colours without a monochromatic edge, equivalently if it has no odd cycle.
For an infinite graph \(G\), define \(h_G(n)\) to be the smallest integer such that every subgraph of \(G\) on \(n\) vertices becomes bipartite after deleting at most \(h_G(n)\) edges. Erdős, Hajnal and Szemerédi ask whether, whenever \(\chi(G)=\aleph_1\),
The quantifier fixes one host graph \(G\) first, then lets \(n\) tend to infinity. Deleting edges does not mean deleting vertices or considering only induced subgraphs.
A small example
For a triangle \(K_3\), deleting any one edge makes the graph bipartite, whereas deleting zero does not. Thus its edge-bipartization number is one. In a disjoint union of \(t\) triangles, at least one edge from each triangle must be removed, so exactly \(t\) deletions are needed. This makes \(h_G(n)\) linear in the number of chosen vertices for those examples, rather than superlinear.
More generally, for a finite graph \(H\), the minimum number of edges to delete before it becomes bipartite equals \(|E(H)|-\mathrm{maxcut}(H)\): choose a bipartition keeping all crossing edges, and delete the others. This identity supplies an exact computational interface.
What is known
The conjecture remains OPEN. The maintained Erdős #111 states that every graph of chromatic number \(\aleph_1\) satisfies a universal lower bound \(h_G(n)\gg n\). A core combinatorial input is the existence of uncountably many vertex-disjoint odd cycles of some fixed length in such a graph. That lower bound is not the conjectured superlinear behaviour.
Erdős, Hajnal and Szemerédi constructed a graph with chromatic number \(\aleph_1\) for which
An earlier Erdős conjecture proposed an improvement to \(h_G(n)\ll_\epsilon n^{1+\epsilon}\) for each \(\epsilon>0\) in a suitable construction. This upper bound would still be compatible with \(h_G(n)/n\to\infty\); the two directions are easily confused.
The primary mathematical bibliography includes the 1982 Erdős–Hajnal–Szemerédi work and Erdős's subsequent 1987 and 1997 problem lists. The precise published derivation of the fixed-length odd-cycle property and the host-graph construction have not been independently page-audited here.
GCL's current state
The pinned catalogue and maintained source classify #111 OPEN. Its original GCL task is #1380. This article uses a direct exact max-cut identity while keeping source-attributed infinitary results separate from any new proof or finite verification.
The original issue contains an authenticated RESULT/1 source report. This is unadjudicated source evidence only, not independent mathematical certification or editorial admission.
What remains
A bounded task is to enumerate finite graphs up to six vertices, calculate the largest edge cut exactly, and compare it with the minimum size of an odd-cycle edge-transversal. Acceptance: equality for every graph, one deletion for a triangle, \(t\) deletions for \(t\) disjoint triangles when represented, and a check that forests require zero. Stop at these finite semantics. They cannot establish universal asymptotic behaviour for \(\aleph_1\) chromatic hosts.
Sources and claim boundaries
- Maintained Erdős #111, original [Er81], [EHS82], [Er87] and [Er97f] leads.
- Original GCL source issue #1380; pinned catalogue revision 536408716724a2402bdfa7c1d764bf83d64a8c89.
No proof of superlinear edge-bipartization, new infinitary counterexample or editorial admission is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1380 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: STATEMENT_CAPTURE_REQUIRED.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.