The below argument is from Zhao's book "Graph Theory and Additive Combinatorics".
Definition 2.1.2 ($\varepsilon$-regular pair)
Let $G$ be a graph and $U,W\subseteq V(G)$. We call $(U,W)$ an
$\varepsilon$–regular pair in $G$ if for all $A\subseteq U$ and
$B\subseteq W$ with $|A|\geq \varepsilon |U|$ and $|B|\geq \varepsilon
|W|$, one has $$|d(A,B)-d(U,W)|\leq \varepsilon.$$ If $(U,W)$ is not
$\varepsilon$-regular, then we say that their irregularity is
witnessed by some $A\subseteq U$ and $B\subseteq W$ satisfying
$|A|\geq \varepsilon |U|$, $|B|\geq \varepsilon |W|$, and
$|d(A,B)-d(U,W)|> \varepsilon.$
Definition 2.1.7 ($\varepsilon$-regular partition)
Given a graph $G$, a partition $\mathcal{P}=\{V_1,\dots,V_k\}$ of its
vertex set is an $\varepsilon$–regular partition if
$$\sum_{\substack{(i,j)\in [k]^2\\\text{$(V_i,V_j)$ not
$\varepsilon$-regular}}}|V_i||V_j|\leq \varepsilon |V(G)|^2.$$
Now we can formulate Regularity Lemma:
Theorem 2.1.9 (Szemeredi's graph regularity lemma) For every $\varepsilon>0$, there exists a constant $M$ such that every graph
has an $\varepsilon$-regular partition into at most $M$ parts.
In order to prove this fundamental result we need to introduce the following definition:
Definition 2.1.10 (Energy)
Let $G$ be an $n$-vertex graph. Let $U,W\subseteq V(G)$. Define
$$q(U,W):=\frac{|U||W|}{n^2}d(U,W)^2,$$ where $d(U,W)$ is an edge density between $U$ and $W$.For partitions
$\mathcal{P}_{U}=\{U_1,\dots,U_k\}$ of $U$ and
$\mathcal{P_W}=\{W_1,\dots,W_l\}$ of $W$, define
$$q(\mathcal{P}_U,\mathcal{P}_W):=\sum
\limits_{i=1}^{k}\sum_{j=1}^{l}q(U_i,W_j).$$ Finally, for a partition
$\mathcal{P}=\{V_1,\dots,V_k\}$ of $V(G)$, define its energy to be
$$q(\mathcal{P}):=q(\mathcal{P},\mathcal{P})=\sum
\limits_{i,j=1}^{k}q(V_i,V_j)=\sum
\limits_{i,j=1}^{k}\frac{|V_i||V_j|}{n^2}d(V_i,V_j)^2.$$
Since the edge density is always between $0$ and $1$, we have $0\leq q(\mathcal{P})\leq 1$ for all partitions $\mathcal{P}$.
The following lemma plays an important role in the proof of Graph Regularity Lemma.
Lemma 2.1.14 (Energy boost for an irregular partition) If a partition $\mathcal{P}=\{V_1,\dots,V_k\}$ of $V(G)$ is not
$\varepsilon$-regular, then there exists a refinement $\mathcal{Q}$ of
$\mathcal{P}$ where every $V_i$ is partitioned into at most $2^{k+1}$
parts, and such that $$q(\mathcal{Q})>q(\mathcal{P})+\varepsilon^5.$$
Proof of the graph regularity lemma (Theorem 2.1.9). Start with a trivial partition of the
vertex set of the graph. Repeatedly apply Lemma 2.1.14 whenever the current partition is
not $\varepsilon$-regular. By Lemma 2.1.14, the energy of the partition increases by more than $\varepsilon^5$ at each iteration. Since the energy of the partition is $\leq 1$, we must stop after $<\varepsilon^{-5}$ iterations, terminating in an $\varepsilon$-regular partition.
If a partition has $k$ parts, then Lemma 2.1.14 produces a refinement with $\leq k2^{k+1}$ parts. We start with a trivial partition with one part, and then refine $<\varepsilon^{-5}$ times. Observe the crude bound $k2^{k+1}\leq2^{2^k}$. So the total number of parts at the end is $\leq \text{tower}(\lceil 2\varepsilon^{-5}\rceil)$ (In the book author writes ceiling function, but I believe one can take floor function as well, i.e. I mean that the total number of parts at the end is $\leq \text{tower}(\lfloor 2\varepsilon^{-5}\rfloor)$), where
$$\text{tower}(k):=2^{2^{.^{.^{.^{2}}}}} \Bigg\} \text{height $k$}$$
Question:
The regularity lemma is quite flexible. For example, we can start with
an arbitrary partition of $V(G)$ instead of the trivial partition in
the proof, in order to obtain a partition that is a refinement of a
given partition. The exact same proof with this modification yields
the following.
Theorem 2.1.19 (Regularity starting with an arbitrary intiial partition)
For every $\varepsilon>0$, there exists a constant $M$ such that for
every graph $G$ and a partition $\mathcal{P}_0$ of $V(G)$, there
exists an $\varepsilon$-regular partition $\mathcal{P}$ of $V(G)$ that
is a refinement of $\mathcal{P}_0$, and such that each part of
$\mathcal{P}_0$ is refined into at most $M$ parts.
I don't think that it follows easily and directly as we did in original formulation of regularity lemma. This is what I've done so far. Let $\varepsilon>0$ be given and take any graph $G$ and fix some partition $\mathcal{P}_0=\{V_1,\dots,V_k\}$ of $V(G)$. If $\mathcal{P}_0$ is $\varepsilon$-regular, then we are done. Otherwise, we apply Lemma 2.1.14 and obtain a partition $\mathcal{P}_1$ of $V(G)$ which refines $\mathcal{P}_0$ such that $|\mathcal{P}_1|\leq k2^{k+1}$ and $q(\mathcal{P}_1)>q(\mathcal{P}_0)+\varepsilon^5$. By the same reasoning at the $N$th step we have an $\varepsilon$-partition $\mathcal{P}_N$, where $N<\varepsilon^{-5}$ and $$|\mathcal{P}_N|\leq 2^{2^{\dots^{2^k}}} \Bigg \} \text{height $(2N+1)$}.$$
But we see that the size of $\mathcal{P}_N$ depends depends also on $k=|\mathcal{P}_0|$. We know that $2N+1\leq \lfloor 2\varepsilon^{-5}\rfloor+1$. But I am wondering is it possible to give an upper bound for $k$ in terms of $\varepsilon$?
Can anyone help me please?
P.S. Unfortunately, my edit was wrong so I've decided to give bounty on this question. I worked hard on this question for 3-4 days but I don't know the answer.
EDIT: I think that I understood the claim. It was much simpler than I thought before. Suppose we fix some partition $\mathcal{P}_0$ of $V(G)$. We already know that if we start from trivial partition, then we end up in $\varepsilon$-regular partition (say $\mathcal{P}'$) in fewer than $\text{tower}(\lfloor 2\varepsilon^{-5} \rfloor)$ steps. However, if we intersect $\mathcal{P}_0$ with partitions (by intersection I mean a common refinement of two partitions) at each step and since energy does not decrease under refinement, then we still obtain an $\varepsilon$-regular partition which refines $\mathcal{P_0}$ and the number of parts in this partition is $\leq |\mathcal{P}_0|\text{tower}(\lfloor 2\varepsilon^{-5} \rfloor)$. Does it make sense?
Best Answer
You are correct in pointing out a mistake in the statement. The resulting number of parts depends on the number of parts in the initial partition. I will make a correction.