Erdős, Hajnal & Szemerédi (1982) — an $\\aleph_1$-chromatic graph with $h_G(n)=O(n^{3/2})$

Statement

For a graph $G$, let $h_G(n)$ be the least number such that every induced subgraph of $G$ on $n$ vertices can be made bipartite by deleting at most $h_G(n)$ edges (erdosproblems.com/111's notation; equals $f^3_\mathscr{G}(n)$ in the primary source's notation). The still-open Erdős #111 asks for the behaviour of $h_G(n)$ over graphs $G$ with $\chi(G)=\aleph_1$ — in particular whether $h_G(n)/n\to\infty$ for *every* such $G$ — and records Erdős's [Er81] conjecture that the bound below can be sharpened from $n^{3/2}$ to $n^{1+\varepsilon}$ for every $\varepsilon>0$.

This page documents the solved piece that #111 builds on and asks to sharpen

Erdős, Hajnal & Szemerédi's 1982 theorem that a graph $G$ with $\chi(G)=\aleph_1$ (indeed with $\chi(G)>\kappa$ for *any* prescribed cardinal $\kappa\ge\omega$) *can* achieve the polynomial bound $h_G(n) \le 2n^{3/2}$ — settling the "does some ℵ₁-chromatic graph even admit a sub-quadratic, in fact sub-$n^2$, near-bipartite repair rate" existence question, and supplying the explicit construction + counting technique that any attack on the open exponent-sharpening question ($3/2\to1+\varepsilon$) would need to refine.

Facts

- Source: P. Erdős, A. Hajnal, E. Szemerédi, "On Almost Bipartite Large Chromatic Graphs," *Annals of Discrete Mathematics* 12 (1982), 117–123 — this is exactly [EHS82], the origin reference cited on erdosproblems.com/111. Read in full from the primary PDF. - Result (their Theorem 3(a)): for all cardinals $\kappa\ge\omega$ there is a graph $\mathscr{G}$ with $\chi(\mathscr{G})>\kappa$ such that $f^3_\mathscr{G}(n) = h_\mathscr{G}(n) \le 2n^{3/2}$ for every finite $n$. - The witness graph: $\mathscr{G} = \mathscr{G}_0(\alpha,2)$, the classical shift graph. Vertices $=$ unordered pairs $\{x,y\}\subset\alpha$ for a sufficiently large ordinal $\alpha$; pairs $X=\{x_0<x_1\}$ and $Y=\{y_0<y_1\}$ are adjacent iff $y_0=x_1$ (share an endpoint, in the specific min/max order pattern of a shift graph). - Why $\chi$ is forced large: by their Lemma 1.1(a) (from the companion papers Erdős–Galvin–Hajnal [3] and Erdős–Hajnal 1966 [4]), $\chi(\mathscr{G}_0(\alpha,2))>\kappa$ once $\alpha\to(4)^2_\kappa$ (an Erdős–Rado partition relation); concretely $\alpha\ge(2^\kappa)^+$ suffices. Taking $\kappa=\aleph_0$ gives $\chi(\mathscr{G})\ge\aleph_1$. - Matching lower bound (why $n^{3/2}$ is close to tight in exponent, not just "some bound"): by their Lemma 2.1, any $G$ with $\chi(G)>\omega$ contains $\aleph_1$ vertex-disjoint odd cycles of some fixed length $2i+1$, forcing $h_G(n)\gg n$ unconditionally — this is exactly the "$h_G(n)\gg n$ always" fact quoted on erdosproblems.com/111. So the open exponent question is squeezed between $1$ (trivial lower bound) and $3/2$ (this paper's construction); Erdős's [Er81] conjecture targets $1+\varepsilon$. - A partial push toward $n^{1+\varepsilon}$ already in this same paper (their Theorem 3(b)/Theorem 4): for every $\varepsilon>0$ there is a finite $r$ and a graph $\mathscr{G}$ with $\chi(\mathscr{G})>\kappa$ such that every $n$-subgraph can be reduced to chromatic number $\le r$ (not necessarily $\le2$, i.e. not necessarily bipartite) by deleting only $O(n^{1+\varepsilon})$ edges, proved by an inductive "ordered edge graph" amplification (below). The gap between this (solved, $\chi\le r$ target) and Er81's still-open conjecture (bipartite, $\chi\le2$ target, same $n^{1+\varepsilon}$ rate) is precisely the content of open #111. - Related problems: Erdős #74 — almost-bipartite graph of infinite chromatic number — cross-linked directly on erdosproblems.com/111 ("See also [74]").

Solution

The transferable technique has two layers: (1) a generic recipe for forcing $\chi>\kappa$ via order-based adjacency + a partition relation, and (2) a "hub-isolation + positional parity coloring" counting argument that gets a genuinely sub-quadratic bipartite-repair rate for free once the adjacency rule is order-based.

Layer 1 — manufacture large chromatic number almost for free (shift graphs). Pick an ordinal $\alpha$ large enough that the Erdős–Rado-type partition relation $\alpha\to(2k)^k_\kappa$ holds (for $k=2$: $\alpha\ge(2^\kappa)^+$ works). Define $\mathscr{G}_0(\alpha,k)$: vertices $=[\alpha]^k$ ($k$-subsets of $\alpha$), edges join $X=\{x_0<\dots<x_{k-1}\}$ to $Y=\{y_0<\dots<y_{k-1}\}$ iff $y_j=x_{j+1}$ for all $j<k-1$ (consecutive-overlap / shift adjacency). The partition relation forces $\chi(\mathscr{G}_0(\alpha,k))>\kappa$. This is the reusable move for manufacturing arbitrarily-large-chromatic graphs that are still "locally sparse" in various senses: index vertices by tuples from a big enough ordinal, connect by an order-based (not random, not algebraic) adjacency rule, and cite a Ramsey/partition relation to lower-bound $\chi$ combinatorially rather than probabilistically.

Layer 2 — the quantitative $O(n^{3/2})$ bipartite-repair bound (hub isolation, EHS82 Theorem 3.A(a)). Given any $n$-element set of vertices $A\subset[\alpha]^2$ (i.e. $n$ pairs): 1. For each ground-set point $x\in\alpha$, let $v(x)=\#\{\text{pairs in }A\text{ containing }x\}$. Since $\sum_x v(x)=2n$, at most $n^{1/2}$ points can have $v(x)\ge n^{1/2}$ — call this sparse "hub" set $H$, $|H|\le n^{1/2}$. 2. Split $A$ into $A_0$ (pairs disjoint from $H$), $A_1$ (pairs with exactly one endpoint in $H$), $A_2$ (pairs with both endpoints in $H$). 3. Every shift-graph edge touching $A_0\cup A_2$ is charged to either a low-degree point ($v(x)<n^{1/2}$) or a hub point ($x\in H$, $|H|\le n^{1/2}$); a direct counting argument (each of $A$'s $\le 2n$ point-incidences contributes $O(n^{1/2})$ such edges) bounds the *total* number of shift-graph edges touching $A_0\cup A_2$ by $O(n^{3/2})$. Delete them all. 4. What remains is the induced subgraph on $A_1$ — pairs with exactly one endpoint in $H$ — and this is bipartite for free: 2-color by whether the $H$-endpoint of a pair is its min or its max element. Because shift-graph adjacency requires two pairs to share an endpoint in a fixed min/max "role" ($y_0=x_1$), that role is exactly what the 2-coloring reads off, so no edge of the shift graph can stay monochromatic under it.

Total deletions: $O(n^{3/2})$, proving $h_\mathscr{G}(n)\le 2n^{3/2}$.

The reusable idea, stated abstractly: don't try to 2-color a hard finite piece directly. Instead (i) isolate a vanishingly small ($\sqrt n$-size) set of "popular" ground-set elements ("hubs"), (ii) pay a *polynomial-but-subquadratic* edge-deletion cost to disconnect them from everything else — this is the step whose exponent ($3/2$ here) is exactly what open #111 wants pushed down toward $1$ — and (iii) exploit that the surviving "one hub-incidence per edge" graph inherits a free bipartition directly from the positional/order rule that defined adjacency in the first place. This "hub isolation → positional parity coloring" pattern generalizes to any graph built from an order-based tuple-adjacency rule (shift graphs, the paper's "Specker graphs" $\mathscr{G}_1(\alpha,k,i)$, etc.), and it is exactly the mechanism a future improvement of the $3/2$ exponent — or a resolution of erdosproblems.com's stated question "$h_G(n)/n\to\infty$ always?" — would need to sharpen or defeat.

Layer 3 — an inductive amplifier toward $n^{1+\varepsilon}$, but only for the weaker $\chi\le r$ target (Theorem 3(b)/4). EHS82 define the ordered edge graph operation $\mathrm{OE}(\mathscr{G},\prec)$: vertices $=$ edges of $\mathscr{G}$, two "old edges" adjacent in $\mathrm{OE}$ iff they share an endpoint respecting the order $\prec$. They show (Lemma 1.2/1.3) this operation both preserves large $\chi$ and — crucially, their Theorem 4 — transports a repair-rate bound $O(n^{1+k^{-1}+\eta})$ for $\mathscr{G}$ into $O(n^{1+(k+1)^{-1}+\eta})$ for $\mathrm{OE}(\mathscr{G},\prec)$, at the cost of only guaranteeing chromatic number $\le r(\eta)$ (some finite $r$) rather than genuinely $\le2$ after deletion. Iterating $\mathrm{OE}$ pushes the exponent down toward $1+\varepsilon$ for arbitrary $\varepsilon$, but the induction's base bipartite step is exactly Layer 2's shift-graph argument, and each iteration trades exponent for allowed target chromatic number $r$ — it does not stay at $\chi\le2$ (bipartite). Transplanting this inductive-amplifier idea while keeping the target literally bipartite is the natural next attack surface on open #111 / Er81's conjecture.

Related

- Erdős #74 — almost-bipartite graph of infinite chromatic number — the odd-cycle problem, cross-linked directly on erdosproblems.com/111 ("See also [74]"); same EHS82/Erdős–Hajnal infinite-graph research programme. - concept/shift-graph — the $\mathscr{G}_0(\alpha,k)$ construction family (vertices $=$ $k$-subsets of an ordinal, order-based "consecutive overlap" adjacency); the generic engine, used throughout EHS82, for building large-chromatic, locally-sparse-in-some-sense graphs. - concept/erdos-rado-partition-relation — the ordinal-size threshold $\alpha\to(2k)^k_\kappa$ (concretely $\alpha\ge(2^\kappa)^+$ for $k=2$) that forces $\chi(\mathscr{G}_0(\alpha,k))>\kappa$; the standard tool (Erdős–Hajnal 1966; Erdős–Galvin–Hajnal) for lower-bounding chromatic number of these constructions. - concept/ordered-edge-graph — EHS82's $\mathrm{OE}(\mathscr{G},\prec)$ inductive operation (Theorem 4), the tool behind their separately-proved (and short of the genuinely-bipartite case) $n^{1+\varepsilon}$ result for "reduce to chromatic number $\le r$."