ERDŐS/DAILY ▸

← back to the ledger

ERDőS #111 · PARTIAL

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;

  1. an elementary proof that the \(n^{3/2}\) exponent in the first

Erdős--Hajnal--Szemerédi ordered-shift witness is sharp;

  1. an exact, reproducible finite computation that improves the constant in

that lower bound.

Claim labels used below are exactly:

0. Mandatory live-page gate

I fetched the live page through the Bright Data browser on 2026-07-26. It displayed:

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:

contains \(\aleph_1\) vertex-disjoint odd cycles of length \(2r+1\);

\(h_G(n)\ll n^{3/2}\);

to \(\ll n^{1+\epsilon}\) for every \(\epsilon>0\);

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:

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<y\), and \((x,y)\) is adjacent to \((y,z)\) for \(x<y<z\). 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, DOI 10.1007/BF02579174.

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

\[ \beta(F)\geq \chi(F)-2 \tag{2} \]

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.

2. A finite-density equivalence that recovers uniformity

For a finite graph \(F\), write

\[ \beta(F):=\min\{|D|:D\subseteq E(F),\ F-D\text{ is bipartite}\} =|E(F)|-\operatorname{MaxCut}(F). \]

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\).

  1. 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} \]

Proposition

Assertions 1 and 2 are equivalent. (a)

Proof

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

\[ F_\xi\subseteq G-\bigcup_{\eta<\xi}V(F_\eta), \qquad \beta(F_\xi)>2L|V(F_\xi)|. \tag{4} \]

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

\[ \frac{h_G(n)}n \geq \frac{\lfloor n/v\rfloor b}{n} \longrightarrow \frac bv>2L. \]

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\).

3. The EHS ordered 2-shift has a sharp \(n^{3/2}\) profile

Let \(S_t\) be the finite shift graph with

\[ V(S_t)=\binom{[t]}2,\qquad E(S_t)= \left\{\{(i,j),(j,k)\}:0\le i<j<k<t\right\}. \]

It has \(\binom t2\) vertices and \(\binom t3\) edges. A two-colouring of 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<j<k\) for which

\[ c(i,j)=c(j,k). \tag{5} \]

3.1 Elementary \(C_5\) lower bound

The five vertices

\[ (0,1),(1,2),(2,3),(3,4),(1,3) \]

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

\[ \beta(S_t)\binom{t-3}{2} \geq \binom t5, \]

and hence

\[ \boxed{\displaystyle \beta(S_t)\geq \frac1{10}\binom t3.} \tag{6} \]

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

\[ h_H(n)\geq \left(\frac{\sqrt2}{30}+o(1)\right)n^{3/2}. \tag{7} \]

Combining (7) with EHS Theorem 3.A, equation (1), gives

\[ \boxed{h_H(n)=\Theta(n^{3/2}).} \tag{8} \]

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.

3.2 Exact computation through \(t=12\)

The standalone checker erdos111_wave5i_verify.py 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\), let

\[ r_i=\#\{a<i:c(a,i)=\text{red}\},\qquad d_i=2r_i-i. \]

When adding \(j\), making \((i,j)\) red creates \(r_i\) new bad triples, 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_{i<j}d_i}{2} +\text{(sum of the \(r\) smallest \(d_i\)'s)}. \tag{9} \]

For future stages the only new datum is \(d_j=2r-j\). Thus the sorted multiset 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:

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;

  1. 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\).

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger