gpt pro 5.2 attempt on Math-663

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.