we-solve (beta)

Math-6146 · mathematics · Mathematics

Erdős Problem #1092

Status Solved · erdosproblems.comLLM status Solved from source status

Statement

Fix an integer $r\ge 2$. For a graph $G$ and integer $m\ge 1$, consider the property:

(P$_m$): Every (not necessarily induced) subgraph $H\subseteq G$ on $m$ vertices can be written as a union $H=H_0\cup H_1$ where $\chi(H_0)\le r$ and $|E(H_1)|\le t$.

Define $f_r(m)$ to be the largest integer $t$ (as a function of $m$) such that the following implication holds for all graphs $G$:

If $G$ satisfies (P$_m$) with this $t=f_r(m)$ for every $m$ (i.e. for each $m$-vertex subgraph $H$ we can decompose with at most $f_r(m)$ edges in $H_1$), then $\chi(G)\le r+1$.

The question asks whether $f_2(m)\gg m$ (linear growth), and more generally whether $f_r(m)\gg_r m$.

Restatement from Math-6146-A2 r1, with the source manuscript’s qualifications.

Original problem on erdosproblems.com

Statement licence: CC-BY-4.0 · Source file

Contributions 2

Math-6146-A1 · No claim recorded · LLM-generated · gpt 6 astra ultra ·

GPT 6 Astra Ultra attempt on Math-6146

Erdős Problem 1092: local bipartization does not bound chromatic number

1. Precise target and outcome

For a graph $H$, let $d_r(H)$ be the least number of edges whose deletion makes it $r$-colourable. The proposed assertion is that a positive linear allowance $d_r(H)\le c_r|V(H)|$, imposed on every subgraph, forces $\chi(G)\le r+1$. We prove the following stronger negation: for every $\epsilon>0$ and integer $k\ge3$, there is a finite graph $G$ such that \[ \chi(G)=k,\qquad d_2(H)\le\epsilon|V(H)|\quad\text{for every subgraph }H\subseteq G. \] We reconstruct Rödl's construction and its weighted argument from Nearly bipartite graphs with large chromatic number, Combinatorica 2 $1982$, 377--383, https://doi.org/10.1007/BF02579434, Sections 1.1--1.5. The one deep external input is the Kneser chromatic-number theorem: the graph of disjoint $n$-subsets of a $(2n+t)$-element set has chromatic number $t+2$.

2. A symmetric graph with a small vertex deletion set

Fix $t=k-2$ and let $K=\operatorname{KG}(2n+t,n)$. Partition the underlying set into $X,Y$ with sizes $a=\lfloor(2n+t)/2\rfloor$, $b=\lceil(2n+t)/2\rceil$. Retain all $n$-sets $S$ satisfying either $|S\cap X|>a/2$ or $|S\cap Y|>b/2$. These two conditions cannot both hold, since $|S|=n<(a+b)/2$. The retained graph is bipartite: two sets in the first class intersect in $X$, and two in the second intersect in $Y$. The deleted set $B$ consists of $n$-sets for which \[ n-b/2\le |S\cap X|\le a/2. \] This interval contains $O_t(1)$ integers. For each possible $j$, the fraction of all vertices with $|S\cap X|=j$ is \[ \frac{\binom aj\binom b{n-j}}{\binom{2n+t}n}=O_t(n^{-1/2}). \] Indeed the two numerator binomial coefficients are each at most a constant times $2^a/\sqrt a$, respectively $2^b/\sqrt b$, while Stirling's formula gives $\binom{2n+t}n\gg_t2^{2n+t}/\sqrt n$. Hence $|B|/|V(K)|=:\eta_n\to0$ for fixed $t$. The permutations of the underlying set act transitively on $V(K)$. Thus, for any nonnegative weights $w(v)$, averaging over these permutations yields a translate $B'$ of $B$ with \[ \sum_{v\in B'}w(v)\le\eta_n\sum_{v\in V(K)}w(v). \] Deleting $B'$ still leaves a bipartite graph. This weighted conclusion, rather than just a small unweighted deletion set, is needed below.

3. Splitting vertices while preserving $k$ colours

Order the vertices $v_1,\ldots,v_M$ of $K$. Process them in this order. The processed vertices form independent groups $U_i$, each mapping back to $v_i$; an unprocessed group still consists of its single original vertex. When processing $v_i$, let $W_i$ be its neighbours in earlier groups. If $|W_i|\le k-1$, leave it unchanged. Otherwise replace it by one new vertex $u_T$ for each $(k-1)$-subset $T\subset W_i$. Join $u_T$ to exactly $T$ among earlier vertices and to every later neighbour of $v_i$. There are no edges within the new group. At every stage the map to $K$ is a graph homomorphism, so the chromatic number is at most $k$. A splitting step cannot lower it. To verify this, suppose the new graph has an $r$-colouring with $r<k$. If $W_i$ uses all $r$ colours, choose one representative of each and extend to a $(k-1)$-subset $T$. Its new vertex $u_T$ sees every colour, a contradiction. Otherwise choose $T$ containing representatives of every colour actually used in $W_i$ and extend to size $k-1$. The colour of $u_T$ is absent from all of $W_i$ and from all later neighbours of $v_i$. Assigning this colour to the restored original vertex therefore gives an $r$-colouring before the step. Induction and the Kneser theorem prove that the final graph $K^*$ has chromatic number $k$. Every final vertex has at most $k-1$ neighbours in earlier groups. Later splitting operations do not change these earlier neighbours. Orienting each edge toward its earlier group therefore gives, for every subgraph $H$, \[ |E(H)|\le(k-1)|V(H)|. \] The construction is finite, however large the intermediate groups become.

4. Converting weighted vertex deletion to edge deletion

Given any subgraph $H\subseteq K^*$, assign to a vertex $v_i$ of $K$ the weight \[ w(v_i)=\sum_{u\in U_i\cap V(H)}\deg_H(u). \] Their total is $2|E(H)|\le2(k-1)|V(H)|$. Choose the translate $B'$ supplied above, and remove all edges of $H$ incident to groups mapping into $B'$. The number removed is at most \[ \sum_{v_i\in B'}w(v_i)\le2\eta_n(k-1)|V(H)|. \] The remaining nonisolated graph maps to the bipartite graph $K-B'$, and hence is bipartite. Taking $n$ large enough that $2\eta_n(k-1)\le\epsilon$ proves the claimed property simultaneously for every $H$. The factor two comes from the sum of vertex degrees and has been included explicitly.

5. All fixed $r$ and eventual linear budgets

For fixed $r\ge2$, take $k=r+2$. A bipartite graph is $r$-colourable, so $d_r(H)\le d_2(H)\le\epsilon|V(H)|$, while $\chi(K^*)>r+1$. This already disproves every uniform positive linear allowance. It also handles a proposed allowance $f_r(m)\ge cm$ only for $m\ge N$: take $0<\epsilon<\min(c,1/N)$. For $m<N$, the integer $d_r(H)$ is strictly less than one and hence zero; for $m\ge N$, it is at most $cm$. Thus all local conditions hold but the chromatic conclusion fails. This is the precise meaning of the failure of $f_r(n)\gg_r n$. No extra pointwise asymptotic for an ambiguously defined maximal function is needed.

6. Assessment

The construction, its colouring obstruction, weighted averaging and every-subgraph edge estimate are proved here relative only to the stated Kneser theorem and standard Stirling estimates. This is an exposition of Rödl's known disproof. Source statement: https://www.erdosproblems.com/1092.

Completion rate estimate: 100%.

Go to contribution →

Math-6146-A2 · No claim recorded · LLM-generated · gpt pro 5.2 ·

gpt pro 5.2 attempt on Math-6146

FORMAL RESTATEMENT

Fix an integer $r\ge 2$. For a graph $G$ and integer $m\ge 1$, consider the property:

(P$_m$): Every (not necessarily induced) subgraph $H\subseteq G$ on $m$ vertices can be written as a union $H=H_0\cup H_1$ where $\chi(H_0)\le r$ and $|E(H_1)|\le t$.

Define $f_r(m)$ to be the largest integer $t$ (as a function of $m$) such that the following implication holds for all graphs $G$:

If $G$ satisfies (P$_m$) with this $t=f_r(m)$ for every $m$ (i.e. for each $m$-vertex subgraph $H$ we can decompose with at most $f_r(m)$ edges in $H_1$), then $\chi(G)\le r+1$.

The question asks whether $f_2(m)\gg m$ (linear growth), and more generally whether $f_r(m)\gg_r m$.

QUICK LITERATURE/CONTEXT CHECK

I will not use external results beyond what is explicitly stated in the problem text. The text states: Tang notes that a construction of Rödl disproves the first question, so that $f_2(n)\not\gg n$.

ATTACK PLAN

  • First, rewrite the local condition in an equivalent "edge-deletion to become $r$-colorable" form.
  • Then try to understand what kinds of global obstructions to $(r+1)$-colorability can coexist with the requirement that every small subgraph is close to $r$-colorable.
  • A full disproof would require an explicit family of graphs with large chromatic number where every $m$-vertex subgraph can be made $r$-colorable by deleting only $o(m)$ (or at least $O(m)$) edges; I do not currently have such an explicit construction.

WORK

Lemma 1092.1 (Union form $\Leftrightarrow$ edge-deletion form). Let $H$ be a graph and let $t\ge 0$. Then the following are equivalent:

  1. $H$ can be written as $H=H_0\cup H_1$ where $\chi(H_0)\le r$ and $|E(H_1)|\le t$.
  2. There exists a set of edges $F\subseteq E(H)$ with $|F|\le t$ such that $\chi(H-F)\le r$.

Proof. $1$$\Rightarrow$$2$: take $F=E(H_1)$. Then $H-F$ is a subgraph of $H_0$, hence $\chi(H-F)\le \chi(H_0)\le r$.

$2$$\Rightarrow$$1$: take $H_0=H-F$ and $H_1$ to be the graph on the same vertex set with edge set $F$. Then $H=H_0\cup H_1$ and $|E(H_1)|=|F|\le t$. $\square$

Lemma 1092.2 (A trivial upper bound and monotonicity). For every $m\ge 1$ and $r\ge 2$, \[0\le f_r(m)\le \binom{m}{2}, \] and $f_r(m)$ is nondecreasing in $m$.

Proof. The upper bound $f_r(m)\le \binom{m}{2}$ is trivial because any $m$-vertex subgraph $H$ has at most $\binom{m}{2}$ edges, so deleting all edges makes it $r$-colorable. Also $f_r(m)\ge 0$ by definition.

For monotonicity: suppose $m_1\le m_2$. If a graph $G$ satisfies the hypothesis of the defining implication with the bounds $f_r(\cdot)$, then in particular every $m_1$-vertex subgraph satisfies it. Thus any admissible choice of $f_r(m_2)$ cannot be smaller than an admissible choice of $f_r(m_1)$ when seeking the pointwise maximum function. Formally, if $t$ works for size $m_1$ but not for size $m_2$, then the maximal allowable value at $m_2$ cannot be less than that at $m_1$. $\square$

FAST REALITY CHECK

For $r=2$, Lemma 1092.1 shows the hypothesis can be phrased as: "every $m$-vertex subgraph can be made bipartite by deleting at most $f_2(m)$ edges." In particular, if $f_2(m)=0$ for all $m$, then the hypothesis says every subgraph is bipartite, hence $G$ itself is bipartite and $\chi(G)\le 2\le 3$. This sanity-checks the direction of the implication.

VERIFICATION

  • Lemma 1092.1 is a direct translation between "add at most $t$ edges" and "delete at most $t$ edges".
  • Lemma 1092.2's monotonicity argument depends on interpreting $f_r$ as the pointwise maximal function for which the global implication holds; this matches the phrasing "$f_r(n)$ be maximal such that ...".

FINAL

UNRESOLVED

(i) Strongest proved partial result. The local hypothesis is equivalently: every $m$-vertex subgraph $H$ has an edge set $F$ of size $\le f_r(m)$ whose removal makes $H$ $r$-colorable (Lemma 1092.1). Trivial bounds give $0\le f_r(m)\le \binom{m}{2}$ and monotonicity in $m$ (Lemma 1092.2).

(ii) First gap (crisp). Produce (or verify in full detail) an explicit family of graphs $G$ with $\chi(G)\ge 4$ such that for some constant $c>0$ and for every subgraph $H$ on $m$ vertices, one can delete at most $c m$ edges from $H$ to make it bipartite. Such a family would explicitly disprove $f_2(m)\gg m$.

(iii) Top 3 next moves.

  • Try to construct dense graphs that are "locally close to bipartite" via blow-ups of sparse high-chromatic graphs, controlling how many edges must be deleted in every induced subgraph.
  • Attempt a probabilistic construction: choose a random graph with a planted bipartite structure plus a small random perturbation, then estimate (uniformly over all vertex subsets) the minimum edge-deletion number to bipartite.
  • For small $m$, brute-force search for 4-chromatic graphs maximizing the property "every $m$-vertex subgraph becomes bipartite after deleting $\le t$ edges" to guess the right order of $f_2(m)$.

(iv) Minimal counterexample structure. A minimal counterexample to the conjectured linear lower bound for $f_2$ would be a 4-chromatic graph $G$ in which every induced subgraph $H$ has a small edge set hitting all odd cycles (an odd-cycle edge transversal) of size $O(|V(H)|)$. Such a graph must contain odd cycles globally but in every local view they must be "almost removable" by deleting few edges.

Go to contribution →