Erdős problem #111 — finite-density reduction and a sharp obstruction for the EHS shift witness
Date: 2026-07-26 (UTC)
This report does not solve problem #111. It gives:
1. an elementary equivalence that removes a potentially troublesome
uniformity-in-\(n\) step;
2. an elementary proof that the \(n^{3/2}\) exponent in the first
Erdős--Hajnal--Szemerédi ordered-shift witness is sharp;
3. an exact, reproducible finite computation that improves the constant in
that lower bound.
Claim labels used below are exactly:
- (a) elementary-rigorous;
- (b) rigorous modulo the explicitly named theorem;
- (c) plausible/structural-unverified;
- (d) computational-only.
0. Mandatory live-page gate
I fetched the live page through the
Bright Data browser on 2026-07-26. It displayed:
- status
OPEN; 0 comments on this problem;0 claimed proofs for this problem;Interested in collaborating: None;Currently working on this problem: None;- no other active-work or proof marker.
Thus the stop condition did not trigger.
The verbatim displayed statement was:
> 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\)?
The page's listed background was:
- this is a problem of Erdős, Hajnal, and Szemerédi;
- every such \(G\) has \(h_G(n)\gg n\), since for some \(r\), \(G\)
contains \(\aleph_1\) vertex-disjoint odd cycles of length \(2r+1\);
- Erdős, Hajnal, and Szemerédi constructed such a \(G\) with
\(h_G(n)\ll n^{3/2}\);
- Erdős conjectured in [Er81] that the construction bound can be improved
to \(\ll n^{1+\epsilon}\) for every \(\epsilon>0\);
- see also problem #74.
I treat those live-page statements, and not the stale tracker tags, as the
ground truth for the problem.
1. Source and literature audit
The primary paper is:
- P. Erdős, A. Hajnal, and E. Szemerédi,
On almost bipartite large chromatic graphs,
Annals of Discrete Mathematics 12 (1982), 117--123,
DOI 10.1016/S0304-0208(08)73497-273497-2).
I checked the full paper, not just its abstract. Definition 3.1 defines the
edge-deletion parameter. Theorem 3(a), reduced to Theorem 3.A, proves
\[ h_{W_0(\omega,2)}(n)<2n^{3/2}. \tag{1} \]Here \(W_0(\alpha,2)\) is the ordered 2-shift graph: its vertices are ordered
pairs \(x Every finite subgraph of \(W_0(\alpha,2)\), for infinite \(\alpha\), order-embeds in \(W_0(\omega,2)\), and conversely. Thus all infinite versions have the same finite defect profile. (a) The cited 1981 source is: On the combinatorial problems which I would most like to see solved, Combinatorica 1 (1981), 25--42, On pages 15--16, Erdős states the weaker-looking formulation: for every constant \(c\), a graph of chromatic number at least \(\aleph_1\) should have a finite subgraph that cannot be made bipartite by deleting \(cm\) edges, where \(m\) is its number of vertices. He then records the hoped-for \(m^{1+\epsilon}\) construction. Section 2 below proves that the first formulation is actually equivalent to the live page's full limit statement; the missing uniformity step is recoverable. I also checked the citation trail concerned with finite subgraphs of uncountably chromatic graphs: Finite subgraphs of uncountably chromatic graphs, J. Graph Theory 49 (2005), 28--38, DOI 10.1002/jgt.20060; On the growth rate of chromatic numbers of finite subgraphs, Adv. Math. 369 (2020), 107176, DOI 10.1016/j.aim.2020.107176. Those papers concern how slowly the chromatic numbers of finite subgraphs may grow. They do not give the required edge-bipartization density. The elementary inequality is only one-way: if \(d=\beta(F)\) edges make \(F\) bipartite, choosing one endpoint of each deleted edge leaves a bipartite graph after at most \(d\) vertices are removed, so \(\chi(F)\le d+2\). (a) Without control of \(|V(F)|\) in terms of \(\chi(F)\), (2) gives no lower bound on \(\beta(F)/|V(F)|\). Exact-title, citation, and keyword searches for the EHS paper and for uncountable-chromatic edge bipartization found no later primary source claiming a proof or counterexample to #111, nor an improvement of the two live-page bounds. This is a search miss, not a claim that no such paper exists. For a finite graph \(F\), write The equality holds because the edges retained by any bipartite spanning subgraph cross one of its bipartitions, and every cut itself is bipartite. (a) Consider the following two universal assertions. 1. For every \(G\) with \(\chi(G)=\aleph_1\), \(h_G(n)/n\to\infty\). 2. For every \(C>0\) and every \(G\) with \(\chi(G)=\aleph_1\), there is a finite \(F\subseteq G\) such that \[
\beta(F)>C|V(F)|.
\tag{3}
\] Assertions 1 and 2 are equivalent. (a) Assertion 1 immediately implies assertion 2: for a sufficiently large \(n\), the definition of \(h_G(n)\) supplies an \(n\)-vertex subgraph with defect greater than \(Cn\). Conversely, assume assertion 2 and fix \(G\) with \(\chi(G)=\aleph_1\). Fix a target \(L>0\). Recursively for every countable ordinal \(\xi<\omega_1\), remove the vertices used earlier and apply assertion 2, with \(C=2L\), to obtain a finite graph At stage \(\xi\), only countably many vertices have been removed. The remainder still has chromatic number \(\aleph_1\): otherwise a countable colouring of the remainder, together with separate colours for the removed countable set, would countably colour \(G\). There are only countably many isomorphism types of finite graphs. Therefore one fixed graph \(F\), with \(v=|V(F)|\) and \(b=\beta(F)>2Lv\), occurs among the pairwise vertex-disjoint \(F_\xi\)'s infinitely (indeed uncountably) often. For any \(n\), take \(\lfloor n/v\rfloor\) copies and pad to \(n\) vertices. If “subgraph” is interpreted non-induced, omit the padding and cross edges; if it is interpreted induced, restricting any deletion certificate to each copy gives the same lower bound. Hence Thus \(h_G(n)/n>L\) for every sufficiently large \(n\). Since \(L\) was arbitrary, assertion 1 follows. \(\square\) This proves that there is no additional “sparse witness sizes” gap: Erdős's 1981 finite-density conjecture already contains exactly the missing mathematics. The recursion above is the uniformity/finiteness step that must not be omitted. The live page's linear lower bound is the first instance of the same mechanism. Repeatedly remove an odd cycle; among the countably many possible odd lengths, one length occurs uncountably often. Packing copies then gives \(h_G(n)\gg n\). Let \(S_t\) be the finite shift graph with
2. A finite-density equivalence that recovers uniformity
Proposition
Proof
3. The EHS ordered 2-shift has a sharp \(n^{3/2}\) profile
its vertices is equivalently a red/blue colouring \(c(i,j)\) of the pairs.
The edges that must be deleted are precisely the triples \(i The five vertices form an induced \(C_5\) in \(S_5\). Therefore every two-colouring of \(V(S_5)\) has at least one bad edge. Now fix any two-colouring of \(V(S_t)\). Every five-element ground subset induces a copy of \(S_5\), so it contains a bad triple. Every fixed bad triple belongs to exactly \(\binom{t-3}{2}\) five-subsets. Double counting gives and hence This proof is elementary-rigorous. (a) Let \(H=W_0(\alpha,2)\) for any infinite \(\alpha\). It contains \(S_t\) on every \(t\)-element ground subset. Given a graph-vertex count \(n\), let \(t\) be maximal with \(\binom t2\le n\), and pad as in Section 2. Since \(t=\sqrt{2n}+O(1)\), (6) yields Combining (7) with EHS Theorem 3.A, equation (1), gives The lower bound is (a); the combined statement (8) is (b), modulo EHS Theorem 3.A. Consequently the ordered 2-shift used for the first EHS upper-bound witness cannot yield \(O(n^{1+\epsilon})\) when \(\epsilon<1/2\). Any realization of the hoped-for construction must alter the finite-subgraph class, rather than merely sharpen the threshold estimate in the proof of EHS Theorem 3.A. The standalone checker uses only the Python standard library. The exact dynamic program is as follows. Process ground vertices \(0,1,\ldots\). After processing \(0,\ldots,j-1\), let3.1 Elementary \(C_5\) lower bound
3.2 Exact computation through \(t=12\)
while making it blue creates \(i-r_i\). If exactly \(r\) of the \(j\) new
pairs are red, the minimum incremental cost is therefore
\[ \frac{j(j-1)/2-\sum_{imultiset of the \(d_i\)'s is a sufficient state, and trying every
\(0\le r\le j\) is exhaustive. Swapping red and blue negates all \(d_i\),
which provides a harmless symmetry reduction. This is an exact Bellman
recurrence, not a heuristic.
The run
python runs/erdos111_wave5i_verify.py
produced:
t beta_DP states balanced_upper
1 0 1 0
2 0 1 0
3 0 3 0
4 0 11 0
5 1 43 1
6 2 180 2
7 5 825 5
8 8 3937 8
9 14 19530 14
10 20 99372 20
11 30 519792 30
12 40 2767536 40
brute-force overlap verified through t=6
verified induced C5 in S_5
verified beta(S_12)=40 and 40/C(12,3)=2/11
elapsed_seconds=19.044
ALL CHECKS PASSED
The program independently:
- literally enumerates every pair-colouring through \(t=6\);
- checks that this agrees with the dynamic program;
- checks the displayed \(C_5\);
- checks an explicit balanced two-interval colouring;
- verifies the double-counting identities below.
Thus
\[ \beta(S_t)= 0,0,0,0,1,2,5,8,14,20,30,40 \quad(1\le t\le12) \tag{10} \]is (d), an exact computational result with an exhaustive checker.
In particular, every 12-element ground subset contains at least 40 bad
triples. Repeating the earlier double count, now over 12-subsets, gives
for all \(t\ge12\)
\[ \begin{aligned} \beta(S_t)\binom{t-3}{9} &\ge 40\binom t{12},\\ \boxed{\displaystyle \beta(S_t)} &\boxed{\displaystyle\ge \frac{40}{\binom{12}{3}}\binom t3 =\frac2{11}\binom t3.} \end{aligned} \tag{11} \]Equation (11) is an elementary double-counting consequence of the
computational lemma (10), so the overall claim remains labelled (d).
It improves (7) to the computationally certified constant
\[ h_H(n)\ge \left(\frac{2\sqrt2}{33}+o(1)\right)n^{3/2}. \tag{12} \]For \(t\le12\), the exact values equal
\[ \binom{\lfloor t/2\rfloor}{3} +\binom{\lceil t/2\rceil}{3}. \tag{13} \]The matching colouring divides the ordered ground set into two consecutive
balanced intervals and colours a pair according to whether its endpoints
are in the same interval. A triple is bad exactly when it lies wholly
inside one interval. Formula (13) for all \(t\) is only (c); the present
computation must not be promoted to a theorem. Proving its lower bound for
all \(t\), or merely obtaining the limiting fraction \(1/4\), would improve
the constant in (12), but would not settle #111.
The state count grew from \(519{,}792\) at \(t=11\) to \(2{,}767{,}536\) at
\(t=12\). A standard-library \(t=13\) run is projected to require roughly
\(15\) million tuple states, several GB of Python dictionary memory, and
more than a few CPU-minutes. I did not run that heavier computation; it is
not needed for the exponent result.
4. Exact remaining wall
By Section 2, the live question is reduced without loss to:
> For every \(C>0\), must every graph \(G\) with
> \(\chi(G)=\aleph_1\) contain a finite \(F\) with
> \(\beta(F)>C|V(F)|\)?
This is precisely the finite-density lemma missing from the standard
machinery. Compactness supplies finite subgraphs of arbitrarily large
chromatic number, but (2) gives only \(\beta(F)\ge\chi(F)-2\) and no useful
control relative to \(|V(F)|\). The obligatory disjoint odd cycles give
only one fixed positive linear density. Conversely, the EHS ordered
2-shift has much larger \(n^{3/2}\) defect, but Section 3 proves that this is
an intrinsic feature of that witness and therefore cannot be tuned down to
near-linear defect.
So the work here closes two technical escape routes:
1. a proof of the finite-density lemma would already give the full limit;
no additional scale-uniformity theorem is needed;
2. simply optimizing the EHS \(W_0(\alpha,2)\) estimate cannot produce the
conjectured \(n^{1+\epsilon}\) construction.
It does not decide whether the finite-density lemma is true.
PARTIAL: The universal limit is equivalent to Erdős's finite-density formulation, and the EHS ordered 2-shift is proved to have sharp \(\Theta(n^{3/2})\) defect; exact DP gives \(\beta(S_{12})=40\).