Erdős Problem #74

Erdős Problem 74: local edge bipartization

1) Statement and current negative resolution

2) A bounded certificate for short odd cycles

We prove by induction that every $k$-rich family has a $k$-rich subfamily whose union has at most $B_k$ edges. At $k=0$ choose the empty family; the defining assertion is vacuous. Suppose the result holds for $k$ and let $\mathcal S$ be $(k+1)$-rich. It is nonempty, so choose $C\in\mathcal S$. For $e\in E(C)$, let $\mathcal S_e$ consist of those cycles avoiding $e$. If some set $F$ of fewer than $k$ edges hit every member of $\mathcal S_e$, then $F\cup\{e\}$, of size at most $k$, would hit every member of $\mathcal S$. This is impossible. Hence each $\mathcal S_e$ is $k$-rich and has a suitable subfamily $\mathcal S'_e$ on at most $B_k$ edges.

Take $\mathcal S'=\{C\}\cup\bigcup_{e\in E(C)}\mathcal S'_e$. Its edge union has size at most $L+LB_k=B_{k+1}$. Given $|F|<k+1$, either $F$ misses $C$, or choose $e\in F\cap E(C)$. In the latter case $|F\setminus\{e\}|<k$, so some cycle of $\mathcal S'_e$ misses $F\setminus\{e\}$. It also misses $e$ and hence misses $F$. This proves the induction, including for an infinite original family.

Consequently, if every subgraph with at most $B_{d+1}$ edges can be made bipartite by deleting at most $d$ edges, then all odd cycles of length at most $L$ in the entire graph can be hit with at most $d$ edges. Otherwise the family would be $(d+1)$-rich; its finite certificate would contradict the assumed bipartization bound.

3) Checking the four-layer coloring join

The recolored vertices are independent: an edge between two of them would have both endpoints of color $2$ under the proper coloring $a$. At the inner boundary, a recolored vertex meets only colors $1,2$ in layer $t$; the same holds at the outer boundary with layer $t+3$. Edges within an unchanged-color region remain proper. The only possible original conflict therefore crossed from $u$ in layer $t+1$ to $v$ in layer $t+2$ with $a(u)=b(v)$. If this common value is $1$, properness of $a$ gives $a(v)=2$, so $v$ is recolored. If it is $2$, properness of $b$ gives $b(u)=1$, so $u$ is recolored. Exactly one endpoint is recolored in either case. Every edge is therefore properly colored.

4) Parameter issue and remaining gap

What is still missing from this attempt is a fully specified sequence of cycle-length cutoffs, deletion budgets and neighborhood radii which always supplies the required four-layer overlaps and preserves the coloring induction. The certificate and the join do not alone establish that sequence. The source's stated disproof is accepted as context; this note does not claim a complete independent disproof.

Outcome of this attempt: UNRESOLVED; two proof ingredients rigorously reconstructed. The batch script checks the join on every allowed pair of color states and adjacent layer types.

5) Source and attribution

6) COMPLETION ESTIMATE

FORMAL RESTATEMENT. Let $f:\mathbb N\to\mathbb N$ be any function with $f(n)\to\infty$ as $n\to\infty$ (no monotonicity is assumed). Does there exist a (simple, undirected) graph $G$ with infinite chromatic number $\chi(G)=\infty$ such that for every integer $n\ge 1$ and every (finite) subgraph $H\subseteq G$ with $\lvert V(H)\rvert=n$, one can delete at most $f(n)$ edges of $H$ to make it bipartite?

Equivalently, defining for a finite graph $H$ the edge bipartization number \[ \beta(H):=\min\{\lvert F\rvert: F\subseteq E(H),\ H-F\text{ is bipartite}\}, \] the question asks whether for every $f(n)\to\infty$ there exists $G$ with $\chi(G)=\infty$ and \[ \beta(H)\le f(\lvert V(H)\rvert)\quad\text{for every finite }H\subseteq G. \]

QUICK LITERATURE/CONTEXT CHECK. The problem statement records: (i) this was conjectured by Erdős, Hajnal, and Szemerédi; (ii) Rödl proved an analogue for hypergraphs, and for graphs proved existence when $f(n)=\varepsilon n$ for any fixed $\varepsilon>0$ (yielding $\chi(G)=\aleph_0$); (iii) the problem is open even for $f(n)=\sqrt n$; (iv) the analogous statement fails (even for $f(n)\gg n$) if one demands $\chi(G)=\aleph_1$. No further literature results are used here.

ATTACK PLAN. Proof track ideas. $1$ Rephrase the condition via maximum cuts: $H$ can be made bipartite by deleting $t$ edges iff $H$ has a cut containing at least $\lvert E(H)\rvert-t$ edges. Then try to build $G$ with very large maximum cuts in every small subgraph, yet unbounded chromatic number. $2$ Attempt a probabilistic construction ensuring simultaneously: large chromatic number and strong local "almost bipartite" behavior.

Disproof track ideas. $1$ Find a universal obstruction: show that any graph with $\chi(G)=\infty$ must contain, for infinitely many $n$, an $n$-vertex subgraph whose maximum cut misses many edges (forcing $\beta(H)$ large).

I did not find a construction or obstruction that resolves the conjecture. Below are problem-specific equivalences and small-case checks.

WORK.

Lemma 74.1 (edge-bipartization equals "edges minus max-cut"). Let $H$ be a finite graph with $m:=\lvert E(H)\rvert$. For a partition $V(H)=L\sqcup R$, let $\mathrm{Cut}_H(L,R)$ be the number of edges with one endpoint in $L$ and the other in $R$. Define \[\mathrm{MaxCut}(H):=\max_{V(H)=L\sqcup R}\mathrm{Cut}_H(L,R).\] Then \[\beta(H)=m-\mathrm{MaxCut}(H).\]

Proof. Fix a partition $V(H)=L\sqcup R$. Consider the subgraph $H_{L,R}$ obtained from $H$ by deleting all edges with both endpoints in $L$ and all edges with both endpoints in $R$, i.e. keeping exactly the crossing edges. By construction, $H_{L,R}$ is bipartite with bipartition $(L,R)$, and the number of deleted edges is \[m-\mathrm{Cut}_H(L,R).\] Therefore \[\beta(H)\le \min_{L\sqcup R}(m-\mathrm{Cut}_H(L,R))=m-\max_{L\sqcup R}\mathrm{Cut}_H(L,R)=m-\mathrm{MaxCut}(H).\]

Conversely, suppose $F\subseteq E(H)$ is such that $H-F$ is bipartite. Let $(L,R)$ be a bipartition of $H-F$. Then every edge of $H-F$ crosses between $L$ and $R$, so $\lvert E(H-F)\rvert\le \mathrm{Cut}_H(L,R)\le \mathrm{MaxCut}(H)$. Since $\lvert E(H-F)\rvert=m-\lvert F\rvert$, this gives \[m-\lvert F\rvert\le \mathrm{MaxCut}(H)\quad\Rightarrow\quad \lvert F\rvert\ge m-\mathrm{MaxCut}(H).\] Taking the minimum over all such $F$ yields $\beta(H)\ge m-\mathrm{MaxCut}(H)$. Combining with the earlier inequality proves $\beta(H)=m-\mathrm{MaxCut}(H)$.$\square$

Lemma 74.2 (complete graphs require quadratic deletions). For the complete graph $K_t$ on $t\ge 2$ vertices, \[\beta(K_t)=\binom{t}{2}-\Big\lfloor\frac{t^2}{4}\Big\rfloor.\]

Proof. Let $t=a+b$ with $a,b\ge 0$, and partition $V(K_t)=L\sqcup R$ with $\lvert L\rvert=a$, $\lvert R\rvert=b$. In $K_t$, every pair of vertices is an edge, so the cut size is exactly \[\mathrm{Cut}_{K_t}(L,R)=ab.\] The product $ab$ is maximized (over integers $a+b=t$) when the partition is as balanced as possible, giving \[\mathrm{MaxCut}(K_t)=\max_{a+b=t}ab=\Big\lfloor\frac{t^2}{4}\Big\rfloor.\] Also $\lvert E(K_t)\rvert=\binom{t}{2}$. Apply Lemma 74.1 to conclude \[\beta(K_t)=\binom{t}{2}-\mathrm{MaxCut}(K_t)=\binom{t}{2}-\Big\lfloor\frac{t^2}{4}\Big\rfloor.\] $\square$

FAST REALITY CHECK (small graphs / explicit numbers). By Lemma 74.2, for $t=2,3,\dots,10$ one obtains: \[ \begin{array}{c|ccccccccc} t & 2&3&4&5&6&7&8&9&10\\\hline \beta(K_t) & 0&1&2&4&6&9&12&16&20 \end{array} \] (Computed directly from $\binom{t}{2}-\lfloor t^2/4\rfloor$; also verified by a short script.) As another sanity check: an odd cycle $C_{2k+1}$ becomes a path (hence bipartite) after deleting one edge, so $\beta(C_{2k+1})=1$.

VERIFICATION.

• Lemma 74.1: checked both directions. One direction constructs an explicit bipartite subgraph for each partition; the other uses a bipartition of $H-F$ to upper-bound $\lvert E(H-F)\rvert$ by a cut size.
• Lemma 74.2: verified the maximum-cut computation $\max_{a+b=t}ab=\lfloor t^2/4\rfloor$ and then applied Lemma 74.1.
• Small values: the table matches the explicit formula and grows like $\sim t^2/4$.

FINAL: UNRESOLVED.

• (i) Strongest proved partial result. The condition "delete $\le f(n)$ edges to make $H$ bipartite" is exactly the max-cut requirement $\mathrm{MaxCut}(H)\ge \lvert E(H)\rvert-f(n)$ (Lemma 74.1). In particular, any candidate $G$ for a slowly growing $f$ must avoid large complete subgraphs because $\beta(K_t)\asymp t^2$ (Lemma 74.2).
• (ii) First gap (crisp). Construct (or rule out) a graph $G$ with $\chi(G)=\infty$ such that every $n$-vertex subgraph $H$ satisfies $\beta(H)\le \sqrt n$ for all large $n$.
• (iii) Top 3 next moves. $1$ Search for explicit high-chromatic graph families (e.g. triangle-free or large-girth graphs) and compute/estimate $\mathrm{MaxCut}(H)$ for their $n$-vertex subgraphs to see whether $\beta(H)$ can be forced $o(n)$. $2$ In the probabilistic direction, attempt to build $G$ as an increasing union of finite graphs with simultaneously large chromatic number and the property that every induced subgraph has a cut missing at most $f(n)$ edges. $3$ On the obstruction side, try to prove a lower bound of the form: any graph with chromatic number $>k$ contains a subgraph $H$ with $\beta(H)\ge g_k(\lvert V(H)\rvert)$ for some explicit $g_k$; then let $k\to\infty$.
• (iv) Minimal counterexample structure. If the conjecture is false for some slowly growing $f$, then for that $f$ every infinite-chromatic graph $G$ contains, for some $n$, an $n$-vertex subgraph $H$ whose edge set is far from any cut: $\mathrm{MaxCut}(H)\le \lvert E(H)\rvert-f(n)-1$. A "minimal" obstruction would likely have bounded clique number but still have every bipartition cutting significantly less than all edges.

OUTPUT 1) FORMAL RESTATEMENT Definitions/Conventions. - Graphs are simple, undirected, and may be infinite. - A graph is bipartite iff it contains no odd cycle. - For a finite graph $H$, define its edge-bipartization number \[\mathrm{ebip}(H):=\min\{|F|: F\subseteq E(H)\ \text{and}\ H-F\ \text{is bipartite}\}.\]

Question. Given any function $f:\mathbb N\to\mathbb N$ with $f(n)\to\infty$, does there exist a graph $G$ with infinite chromatic number (i.e. $\chi(G)$ is not finite) such that for every $n\in\mathbb N$ and every finite subgraph $H\subseteq G$ with $|V(H)|=n$, one has \[\mathrm{ebip}(H)\le f(n)?\]

2) QUICK LITERATURE/CONTEXT CHECK Web browsing is not available in this session. From the problem text only: - The conjecture is attributed to Erdős--Hajnal--Szemerédi. - Rödl proved existence for $f(n)=\varepsilon n$ (and for hypergraphs). - The problem is open even for $f(n)=\sqrt n$. - The analogous statement fails for graphs of chromatic number $\aleph_1$. I do not re-derive these results here.

3) ATTACK PLAN Proof track ideas: 1. Reinterpret $\mathrm{ebip}(H)$ as a minimum edge set hitting all odd cycles (proved below), then try to build an infinite-chromatic graph where every small subgraph has a tiny odd-cycle edge transversal. 2. Attempt to modify probabilistic high-chromatic constructions (Erdős high-girth graphs) so that small subgraphs have very few odd cycles, allowing deletion of $f(n)$ edges.

Disproof track ideas: 1. Try to prove a universal lower bound: in any infinite-chromatic graph, some $n$-vertex subgraph must have $\mathrm{ebip}(H)\ge g(n)$ for a function $g(n)\to\infty$ faster than some candidate $f(n)$.

Chosen path in this attempt: prove two problem-specific lemmas clarifying what "delete $f(n)$ edges to make bipartite" means combinatorially, and what it forbids in $n$-vertex subgraphs.

4) WORK Lemma 1 (Edge-bipartization equals odd-cycle edge transversal). For a finite graph $H$, $\mathrm{ebip}(H)$ equals the minimum size of a set of edges $F\subseteq E(H)$ that intersects every odd cycle in $H$.

Proof. First, if $F\subseteq E(H)$ is such that $H-F$ is bipartite, then $H-F$ contains no odd cycle. Therefore every odd cycle $C$ of $H$ must use at least one deleted edge, i.e. $E(C)\cap F\ne\emptyset$. So any feasible edge-deletion set is an odd-cycle edge transversal.

Conversely, suppose $F\subseteq E(H)$ intersects every odd cycle of $H$. Then $H-F$ has no odd cycle. It is standard that a graph is bipartite iff it has no odd cycle (e.g. by BFS 2-coloring and checking parity along cycles). Thus $H-F$ is bipartite, so $F$ is feasible for $\mathrm{ebip}(H)$.

Taking minima over $|F|$ in the two equivalent formulations shows equality. $\square$

Lemma 2 (Packing obstruction: many edge-disjoint odd cycles force large $\mathrm{ebip}$). Let $H$ be a finite graph, and suppose $H$ contains $t$ pairwise edge-disjoint odd cycles. Then $\mathrm{ebip}(H)\ge t$.

Proof. Let $C_1,\dots,C_t$ be edge-disjoint odd cycles. By Lemma 1, any set of edges $F$ whose deletion makes $H$ bipartite must intersect every odd cycle, hence must intersect each $C_i$ in at least one edge. Since the $C_i$ are edge-disjoint, $F$ must contain at least one distinct edge from each cycle, so $|F|\ge t$. Therefore $\mathrm{ebip}(H)\ge t$. $\square$

FAST REALITY CHECK - For a triangle $K_3$, $\mathrm{ebip}(K_3)=1$ (delete any one edge). - For a disjoint union of $t$ triangles, $\mathrm{ebip}=t$ by Lemma 2 (the $t$ triangles are edge-disjoint odd cycles). So controlling $\mathrm{ebip}(H)$ on all $n$-vertex subgraphs is a strong restriction: it forbids packing many edge-disjoint odd cycles into small vertex sets.

5) VERIFICATION - Lemma 1 uses only the characterization "bipartite iff no odd cycle" and is logically tight in both directions. - Lemma 2 is a direct consequence of Lemma 1: any transversal must hit each edge-disjoint cycle.

6) FINAL UNRESOLVED

(i) Strongest fully proved partial result: The local requirement "delete at most $f(n)$ edges to make bipartite" is exactly the statement that every $n$-vertex subgraph has an odd-cycle edge transversal of size $\le f(n)$ (Lemma 1), and in particular no $n$-vertex subgraph can contain more than $f(n)$ edge-disjoint odd cycles (Lemma 2).

(ii) First gap: Construct (or rule out) an infinite-chromatic graph $G$ such that every $n$-vertex subgraph has $\mathrm{ebip}\le f(n)$ for a slowly growing $f$ (e.g. $f(n)=\sqrt n$). The lemmas above give obstructions, but I did not find a construction meeting them.

(iii) Top 3 next moves (concrete): 1. Search for a construction strategy that guarantees "few edge-disjoint odd cycles in every small subgraph" while allowing global chromatic number to diverge (e.g. by gluing gadgets along sparse cutsets). 2. Attempt a probabilistic existence proof tailored to the local transversal condition: choose a random sparse graph and bound, for each $n$, the probability that some $n$-vertex subgraph contains $>f(n)$ edge-disjoint odd cycles. 3. Try to prove a lower bound on $\mathrm{ebip}(H)$ in terms of $\chi(H)$ that holds uniformly for all finite subgraphs $H$; any such bound would convert the problem into an explicit inequality relating $f(n)$ and possible chromatic growth.

(iv) What a minimal counterexample would likely look like (structure/parameters): If the answer is negative for some slowly growing $f$, then for every infinite-chromatic graph $G$ there should exist arbitrarily large $n$ and an $n$-vertex subgraph $H\subseteq G$ containing many edge-disjoint odd cycles (or another certificate forcing large odd-cycle transversals), with $\mathrm{ebip}(H)>f(n)$.