Erdős Problem #1077
Status Solved · erdosproblems.comLLM status Solved from source status
Erdős problems openaigpt 6 astra ultra 100% cataloguedSolvedSolvedStatement
Statement and negative answer.
The literal question asks whether, for fixed $\epsilon,\alpha>0$ and sufficiently large $D,n$, every $n$-vertex graph with at least $n^{1+\alpha}$ edges has a $D$-balanced subgraph $H$ on \[ m>n^{1-\alpha}\quad\hbox{vertices},\qquad e(H)\geq\epsilon m^{1+\alpha}. \] Here $D$-balanced means $\Delta(H)\leq D\delta(H)$. We disprove this for every fixed $0<\alpha<1/2$, every $\epsilon>0$, and every fixed finite $D\geq1$. The counterexample addresses the vertex-order requirement, even allowing arbitrary, non-induced subgraphs.The host graph.
For sufficiently large $n$, put \[ a=\lceil2n^\alpha\rceil,\qquad G=K_{a,n-a}. \] Since $a=o(n)$, we eventually have $a\leq n/2$. Therefore \[ e(G)=a(n-a)\geq(2n^\alpha)(n/2)=n^{1+\alpha}. \] Thus these graphs meet the question's edge hypothesis with coefficient one.Every balanced subgraph is small.
Let $H\subseteq G$ be a $D$-balanced subgraph with at least one edge. Its minimum degree is positive: otherwise balancedness would force its maximum degree to be zero, contradicting the edge. In particular, isolated vertices cannot be added to enlarge its order.Let $x,y$ be the numbers of its vertices in the two parts of $G$, with $x\leq a$, and let $E=e(H)>0$. Summing degrees in each part gives \[ \Delta(H)\geq E/x,\qquad \delta(H)\leq E/y. \] Hence \[ E/x\leq D E/y,\qquad y\leq Dx, \] and consequently \[ |V(H)|=x+y\leq(D+1)a \leq(D+1)(2n^\alpha+1). \tag{1} \] This calculation uses only bipartiteness and the bound on one host part, so it applies to every choice of retained edges.
Contradicting the proposed exponent.
Because $1-2\alpha>0$, \[ \frac{(D+1)(2n^\alpha+1)}{n^{1-\alpha}}\longrightarrow0. \] Thus $1$ is smaller than $n^{1-\alpha}$ for every sufficiently large $n$. Any subgraph meeting the proposed positive edge lower bound has at least one edge and hence is covered by $1$. No such subgraph can meet the required order.For a single concrete parameter choice, take $\alpha=1/3$ and any $\epsilon>0$. For every proposed fixed $D$, arbitrarily large hosts of the displayed form violate the conclusion. Increasing the allowed constant $D$ therefore does not repair the original assertion. Allowing $D$ to grow with $n$ would be a different statement.
What the construction does and does not say.
The same examples show, for every $0<\alpha<1$, that a general theorem cannot guarantee balanced subgraphs of order larger than a constant multiple of $n^\alpha$, when $D$ is fixed. This observation by itself is an obstruction, not a matching general existence theorem. The current page discusses corrected regularization formulations and later results of Jiang--Longbrake; these are not needed for the negative answer proved above. In particular, this write-up makes no deduction of an optimal order lower bound from an average-degree estimate with a logarithmic loss.Attribution and assessment.
The complete-bipartite obstruction is the example discussed by JunGao at https://www.erdosproblems.com/forum/thread/1077. The statement and its ambiguity are recorded at https://www.erdosproblems.com/1077, checked 24 September 2026. The background regularization paper is T. Jiang and S. Longbrake, Regularization and asymmetric extremal numbers of subdivisions, https://arxiv.org/abs/2507.03261. The disproof above is self-contained and does not import that theorem. No novelty or local Lean verification is claimed.Completion estimate.
Restatement from Math-6131-A1 r1, with the source manuscript’s qualifications.
Original problem on erdosproblems.com
Statement licence: CC-BY-4.0 · Source file
Contributions 1
GPT 6 Astra Ultra attempt on Math-6131
Erdős Problem 1077
Statement and negative answer.
The literal question asks whether, for fixed $\epsilon,\alpha>0$ and sufficiently large $D,n$, every $n$-vertex graph with at least $n^{1+\alpha}$ edges has a $D$-balanced subgraph $H$ on \[ m>n^{1-\alpha}\quad\hbox{vertices},\qquad e(H)\geq\epsilon m^{1+\alpha}. \] Here $D$-balanced means $\Delta(H)\leq D\delta(H)$. We disprove this for every fixed $0<\alpha<1/2$, every $\epsilon>0$, and every fixed finite $D\geq1$. The counterexample addresses the vertex-order requirement, even allowing arbitrary, non-induced subgraphs.The host graph.
For sufficiently large $n$, put \[ a=\lceil2n^\alpha\rceil,\qquad G=K_{a,n-a}. \] Since $a=o(n)$, we eventually have $a\leq n/2$. Therefore \[ e(G)=a(n-a)\geq(2n^\alpha)(n/2)=n^{1+\alpha}. \] Thus these graphs meet the question's edge hypothesis with coefficient one.Every balanced subgraph is small.
Let $H\subseteq G$ be a $D$-balanced subgraph with at least one edge. Its minimum degree is positive: otherwise balancedness would force its maximum degree to be zero, contradicting the edge. In particular, isolated vertices cannot be added to enlarge its order.Let $x,y$ be the numbers of its vertices in the two parts of $G$, with $x\leq a$, and let $E=e(H)>0$. Summing degrees in each part gives \[ \Delta(H)\geq E/x,\qquad \delta(H)\leq E/y. \] Hence \[ E/x\leq D E/y,\qquad y\leq Dx, \] and consequently \[ |V(H)|=x+y\leq(D+1)a \leq(D+1)(2n^\alpha+1). \tag{1} \] This calculation uses only bipartiteness and the bound on one host part, so it applies to every choice of retained edges.
Contradicting the proposed exponent.
Because $1-2\alpha>0$, \[ \frac{(D+1)(2n^\alpha+1)}{n^{1-\alpha}}\longrightarrow0. \] Thus $1$ is smaller than $n^{1-\alpha}$ for every sufficiently large $n$. Any subgraph meeting the proposed positive edge lower bound has at least one edge and hence is covered by $1$. No such subgraph can meet the required order.For a single concrete parameter choice, take $\alpha=1/3$ and any $\epsilon>0$. For every proposed fixed $D$, arbitrarily large hosts of the displayed form violate the conclusion. Increasing the allowed constant $D$ therefore does not repair the original assertion. Allowing $D$ to grow with $n$ would be a different statement.