3
$\begingroup$

My question concerns the following result of Erdős and Simonovits.

A graph $G$ is $d$-almost-regular if $d\delta(G)\geq \Delta(G)$. Theorem 1 of the above paper states that a large $n$-vertex graph $G$ with $n^{1+\alpha}$ edges contains a large $d$-almost-regular subgraph $H$ for a constant $d$ depending only on $\alpha$. I cannot follow the proof of the theorem:

In case a) of the proof, if $C_1$ represents less than $\frac{1}{2}n^{1+\alpha}$ many edges, then we consider $G-C_1$. The resulting graph has only then at least $\frac{1}{2}n^{1+\alpha}$ edges, if $n$ refers to the order of the graph we are considering right now in the inductive step and not the order of the original graph (unless we are in the first step of the induction).

When we later show that the induction terminates after a bounded number os steps, however, we estimate the number of edges by $\frac{1}{(4A)^k}n^{1+\alpha}$. This holds only true if $n$ refers to the order of the original graph throughout the induction.

I tried to modify the proof such that case a) works, that is, $n$ refers to the order of the current graph in the inductive step. It is not hard to show that also then the induction terminates. However, with those modifications I cannot obtain that the subgraph $H$ is still large.

Am I misunderstanding something? Is there a newer presentation of this theorem?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

Yep. The writing is not great (but this is a nice result [but there should be an easier proof by now]). Anyway, you should read the $n^{1+\alpha}$ in the proof as a fixed quantity $\tau$, which is the number of edges in the original graph. The rest then follows.

Improve this answer
$\endgroup$
3
  • $\begingroup$ My problem with the fixed quantity $\tau$ is this: Assume we are in the second step of the induction and in the first step we were in case b). Then there are (at least) $1/(4A)\tau$ many edges left. Now we are in case a) and $C_1$ represents less than $1/2\tau$ many edges, which still may be all edges of the graph. Then $G-C_1$ is edgeless and we have shown nothing. $\endgroup$
    – Sebastian Siebertz
    Apr 24, 2015 at 6:20
  • $\begingroup$ Well, compute explicitly the number of vertices and edges in the graph in the $i$th iteration of this recursive argument... It has $n_i = n ({\frac{2}{5 A}})^{i-1}$ vertices, and least $ m_i \geq m ({\frac{1}{2 (A-1)}})^{i-1}$ edges (according to my calculations). You are applying the argument of part (a) to this graph... Here $m$ is the number of edges in the original graph, and $n$ is the number of vertices in the original graph. $\endgroup$
    – Sariel Har-Peled
    Apr 24, 2015 at 22:32
  • $\begingroup$ I finally understood it: In the $k$-th iteration of the induction we ask whether there are at least $\frac{1}{2(4A)^k}n^{1+\epsilon}$ edges with at least one end in $C_1$. Then one follows through with the numbers as you say. Thanks a lot. $\endgroup$
    – Sebastian Siebertz
    Apr 26, 2015 at 13:24
1
$\begingroup$

In fact $n$ refers to the order of the original graph (they wrote $G^n$) not the graph in the inductive steps, actually this is for the first part of the proof. The idea in the first part of the proof is to find a small set* of vertices of high degree and a small set of vertices of low degree and eliminate them from the original graph so that the resulting graph is almost $d$-regular. So when we eliminate that small set or $C_1$, we have to count the remaining edges w.r.t the original graph minus $C_1$ (not in $G^m$ but in $G^n$).

But if the first part does not happen, then we are in the second case, they don't do recursive operation to obtain something which fits for the first part. In the second part of the proof they say we have a big subgraph so that each vertex has a big degree, they obtain that big subgraph with a recursive procedure (it has nothing to do with a first part). I think the paper is not very well written in fact in the part that they wrote: "Either we obtain 10A-regular graph by a) or a $G^{m_2}$ by b) from it." They don't want to transfer to the a) part during recursion if the b) part happened. They simply shrink the graph obtained recursively from the b) part to satisfy the required properties.

*: Small in a sense that the remaining graph has some function of $n$ many vertices.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.