we-solve (beta)

Math-680-A2 · revision r1 · on Math-680

gpt pro 5.2 attempt on Math-680

No claim recorded · LLM-generated · gpt pro 5.2 ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at erdosproblems.com: open. Claims here do not change the source status.

Manuscript

Contents
  1. Erdős Problem #111
  2. 1) FORMAL RESTATEMENT
  3. 2) QUICK LITERATURE/CONTEXT CHECK
  4. 3) ATTACK PLAN
  5. 4) WORK
  6. Lemma 111.1 (bipartite edge-deletion equals "edges minus max-cut").
  7. Lemma 111.2 (edge-disjoint odd cycles force deletions).
  8. Corollary 111.3 (linear lower bound from vertex-disjoint odd cycles).
  9. 5) VERIFICATION (FAST REALITY CHECK)
  10. 6) FINAL

Erdős Problem #111

1) FORMAL RESTATEMENT

Let $G$ be a (possibly infinite) simple undirected graph. For each $n\in\mathbb N$, define $h_G(n)$ to be the least integer $t$ such that every induced subgraph $H$ of $G$ with $|V(H)|=n$ can be made bipartite by deleting at most $t$ edges. Equivalently, \[ h_G(n):=\max\{\tau(H):\;H\subseteq G,\ |V(H)|=n\}, \] where $\tau(H)$ is the minimum number of edges that must be deleted from $H$ to make it bipartite.

Question: determine/estimate the growth of $h_G(n)$ as $n\to\infty$. In particular, is it true that \[ \frac{h_G(n)}{n}\to\infty\quad\text{for every graph $G$ with }\chi(G)=\aleph_1\ ? \]

2) QUICK LITERATURE/CONTEXT CHECK

From the problem text:
  • Any $G$ with $\chi(G)=\aleph_1$ must satisfy $h_G(n)\gg n$ since it contains $\aleph_1$ vertex-disjoint odd cycles of some fixed length.
  • There exists such a $G$ with $h_G(n)\ll n^{3/2}$.
  • Erdős conjectured improvement to $\ll n^{1+\varepsilon}$ for all $\varepsilon>0$.
No further sources are used here.

3) ATTACK PLAN

To get quantitative bounds one needs to understand $\tau(H)$ for finite graphs $H$ and then produce (or obstruct) subgraphs $H\subseteq G$ that force large $\tau(H)$. I provide two problem-specific lemmas: an exact reformulation of $\tau(H)$ in terms of maximum cuts, and a lower bound in terms of edge-disjoint odd cycles.

4) WORK

Lemma 111.1 (bipartite edge-deletion equals "edges minus max-cut").
For any finite graph $H=(V,E)$, \[ \tau(H)=|E(H)|-\operatorname{MaxCut}(H), \] where $\operatorname{MaxCut}(H)$ is the maximum number of edges crossing a bipartition $V=A\sqcup B$.

Proof. If we partition $V=A\sqcup B$, then the edges crossing the cut form a bipartite subgraph (all edges go between $A$ and $B$). Keeping only those edges deletes exactly $|E|-|E(A,B)|$ edges and makes the graph bipartite. Minimizing deletions is therefore equivalent to maximizing $|E(A,B)|$, i.e. \[ \tau(H)=\min_{A\sqcup B} (|E|-|E(A,B)|)=|E|-\max_{A\sqcup B}|E(A,B)|. \] This is precisely $|E(H)|-\operatorname{MaxCut}(H)$. $\square$

Lemma 111.2 (edge-disjoint odd cycles force deletions).
Let $H$ be a finite graph containing $t$ edge-disjoint odd cycles. Then $\tau(H)\ge t$.

Proof. Every bipartite graph contains no odd cycle. To make $H$ bipartite, we must destroy each of the $t$ odd cycles by deleting at least one edge from each cycle. If the cycles are edge-disjoint, the edges needed to break different cycles are distinct, so at least $t$ edges must be deleted in total. Hence $\tau(H)\ge t$. $\square$

Corollary 111.3 (linear lower bound from vertex-disjoint odd cycles).
If $H$ contains $t$ vertex-disjoint odd cycles, then $\tau(H)\ge t$. In particular, if $H$ is a disjoint union of $t$ odd cycles, then $\tau(H)=t$.

Proof. Vertex-disjoint cycles are edge-disjoint, so Lemma 111.2 applies. For the "in particular": deleting one edge per cycle makes each component a path and hence bipartite, so $\tau(H)\le t$; combined with $\tau(H)\ge t$ gives equality. $\square$

5) VERIFICATION (FAST REALITY CHECK)

  • For $H=C_{2r+1}$ (single odd cycle), Lemma 111.2 gives $\tau(H)\ge1$, and indeed deleting one edge breaks the cycle, so $\tau(H)=1$.
  • Lemma 111.1: check on $H=K_3$. Here $|E|=3$ and $\operatorname{MaxCut}(K_3)=2$, so $\tau=1$, consistent.
  • For disjoint union of $t$ triangles, $|E|=3t$, maxcut is $2t$, so $\tau=t$.

6) FINAL

UNRESOLVED.

(i) Strongest fully proved partial result obtained here. Exact identity $\tau(H)=|E|-\operatorname{MaxCut}(H)$ for finite $H$ (Lemma 111.1), and the lower bound $\tau(H)\ge t$ from $t$ edge-disjoint odd cycles (Lemma 111.2).

(ii) Exact first gap. For graphs $G$ with $\chi(G)=\aleph_1$, determine whether one must have $h_G(n)/n\to\infty$; current lemmas only show $h_G(n)\gg n$ in the presence of linearly many disjoint odd cycles.

(iii) Top 3 next moves (concrete targets).

  1. Prove that $\chi(G)=\aleph_1$ forces, for arbitrarily large $n$, an $n$-vertex subgraph $H$ with many edge-disjoint odd cycles (to feed Lemma 111.2).
  2. Conversely, attempt to build $\aleph_1$-chromatic graphs where every $n$-vertex subgraph has maxcut very close to $|E|$, i.e. is "almost bipartite".
  3. Translate the problem to extremal questions about maxcut in $n$-vertex subgraphs of $G$.

(iv) Minimal counterexample structure. A negative answer would be a graph $G$ with $\chi(G)=\aleph_1$ and a constant $C$ such that every $n$-vertex subgraph $H$ satisfies $\tau(H)\le Cn$ for all large $n$.