# Expander decomposition of graphs

This is from [CZP](https://arxiv.org/pdf/1807.06624.pdf).

**Definition ($n^\delta$-decomposition).** A $n^\delta$ decomposition of a graph $G$ on $n$ vertices in a tripartition of the edge set $E$ in to $E = E_h \cup E_r \cup E_s$ such that:
* Each connected component $X$ induced by $E_h$ has:
* $\Phi(X) \geq \frac 1 {poly \log n}$, ==$\Leftarrow$ good mixing time==
* For every $v \in V(G)$., either $deg_{E_h}(v) = 0$ or $deg_{E_h}(v) \geq n^\delta$. ==$\Leftarrow$ High degree expander==
* $E_s$ has arboricity at most $n^\delta$, and each vertex knows the edges oriented from it.
* $|E_r| \leq |E(G)|/6$.

This is from [Daga et al](https://arxiv.org/abs/1904.04341). Some clean-up is necessary in the paper.

**Defition (X-decomposition).** For $0 < \rho, \gamma <1$, $(\rho, \gamma)$-decomposition of $G$ on $n$ vertices is a tuple ${\cal E} = (E_h, E_r, E_s)$ such that
* $E_h, E_r, E_s$ is a partition of $E(G)$.
* Each component $X$ induced by $E_h$ is an expander with conductance $\Phi(X) \geq \Omega(n^{- \rho})$.
* Edges in $E_r$ has its endpoint in different components induced by $E_h$, and $|E_r| = O(m^{1 - \rho/2})$.
* Rest of the edges are in $E_s$. The arboricity of the subgraph induced by $E_s$ is $O(n^\gamma)$.

**Lemma.** A $(\rho, \gamma)$-decomposition, ==if constructable==, can be found by a randomized distributed algorithm in time $O(n^{1 - \gamma + 10 \rho})$.

#### Trimming and shaving
* Given a set $X$ (a component induced by $E_h$), we prune (or *trim*) vertices such that at the end we have a set $X^{trim} \subseteq X$ such that each $v \in X^{trim}$ has at least $2 deg(v)/5$ many neighbors in $X^{trim}$. ==$X^{trim}$ may not be connected any more.==
* Each of the pruned vertices form a new component.
* A vertex $v \in X^{trim}$ is *shaved* if the number of neighbors of $v$ outside $X^{trim}$ is at least $deg(v)/2$. Thus, $X^{trim}$ is bipartitioned into $X^{core} \cup X^{reg}$ where $X^{reg}$ has all shaved vertices, and for every $v \in X^{core}$, the number of neighbors in $X^{trim}$ is at least $deg(v)/2$.

**Lemma.** TODO: Algorithm

**Lemma.** Let $X_1, \cdots, X_t$ be the components of $G$ induced by $E_h$ after $(\epsilon, \epsilon/11)$-decomposition. Then the total number of nodes trimmed is at most $O(n^{1 - \epsilon/22})$.

**Lemma.** Under similar operation, $\sum_i |X^{reg}_i| = O(n^{1 - \epsilon/22})$.

**Lemma.** Under similar operation, $t = O(n^{1 - 2\epsilon})$.

### Core decomposition

This paper ([CK19](https://arxiv.org/pdf/1905.11512.pdf)) shows a technique much like expander decomposition.

**Definition (Perfect core).** Given a graph $G$ on at most $n$ vertices, a *core structure* ${\cal K} = (K, U(K), G^K, W^K)$ is a tuple where:
* $\emptyset \neq K \subseteq V(G)$ is the *core*
* $U(K)$ with at most $|K|$ vertices is a disjoint set from $K$ is the *extension*,
* $G^K \subseteq G[K \cup U(K)]$ is a connected subgraph over vertex set $V(G^K) = K \cup U(K)$,
* $W^K$, a *witness graph* for $K$ (which shares the vertex set of $G$ and **not the edge set**) with
* Vertex set: $K \subseteq V(W^K) \subseteq K \cup U(K)$,
* Degree: Maximum vertex degree of $W^K$ is at most $\log^3 n$,
* Embedding: For every edge $e = (x,y) \in E(W^K)$, there is a path $P(e)$ in $G^K$ that connects $x$ and $y$ such that:
* length of $P(e)$ is at most $O(\log^8 n)$, and
* Every vertex of $G^K$ participates in at most $O(\log^{19}n)$ such paths.
* Expansion: $W^K$ is an $\alpha$-expander.

**Comment.**
(i) The expansion property of $W^K$ makes the core $\cal K$ perfect.
(ii) $K$ does not play much role in this definition---we could have defined core structure just with $K' = K \cup U(K)$ which is the vertex set of $G^K$. The next definition requires $K$.
(iii) There may be path $P \in G^K$ which connects $u, v$ such that $(u,v) \notin E(W^K)$. This may be because either such paths are long or such path will make some vertex participate in too many paths. This means $E(W^k)$ has a subset of connectivity information of $G^K$.

**Definition ($h$-core).** A core structure ${\cal K} = (K, U(K), G^K, W^K)$ is *$h$-core structure* if
* For every $v \in K$, there is a set $N(v) \in V(W^K)$, $|N(v)| \leq h/(64 \log n)$ such that:
* For every $u \in N(v)$, the edge $(u,v) \in E(G^K)$. ==$\Rightarrow$ A lower bound for $|K \cup U(K)|$==

**Comment.**
1. For a core to be $h$-core, we do not need such $N(v)$ for $v \in U(K)$.
2. Even though $(u,v)$ is connected in $G^K$, there may not be a corresponding edge in $W^K$.

**Observation.** $|K| \geq h/(128 \log n)$.

*Proof.* We have (i) $|K \cup U(K)| \geq h/(64 \log n)$, and (ii) $|K| \geq |U(K)|$ and are disjoint.

**Definition (Core decomposition).** An $h$-core decomposition of $G$ with at most $n$ vertices is a collection ${\cal F} = \{(K_i, U(K_i), G^{K_i}, W^{K_i})\}_{i=1}^r$ such that
* $K_i$'s are mutually disjoint (but $U(K_i)$'s may not be),
* Every $e \in E(G)$ participates in at most $\log n$ many $G^{K_i}$'s.
* Let $\tilde K = \bigcup K_i$ and $J = V(G) - \tilde K$. $J$ is $h$-universal w.r.t to $\tilde K$, i.e.,
* For every $u \in J$ (outside the cores) and for every subset $R \subseteq G - u$ of at most $h/\Delta$ vertices: ==Take $R = \emptyset$ for simplicity==
* There is a path in $G[(\tilde K \cup J) - R]$ connecting $u$ to a vertex in $\tilde K$ of length at most $\log n$. ==i.e., every vertex outside the core is connected to a core with a path of length at most $\log n$==
* If each $\cal K_i$ is a perfect $h$-core, then $\cal F$ is a perfect $h$-core decomposition.

The main decomposition theorem from CK19 is the following:


Here also a procedure named `Proc-Degree-Pruning` is used which is similar to shaving.
* Given a graph $H$ and a degree bound $d$,
* $J^{core}$ is the set of vertices which has more than $d$ neighbors in $J^{core}$ (*core set*), rest of the vertices are in $J^{reg}$ (*regular set*).
* This is achieved by pruning vertices from $J^{core}$ (which is initially $V(H)$) which has fewer than $d$ vertices in $J^{core}$ and putting them in $J^{reg}$.

**Beware:bangbang: :arrow_right:** Here we measure the neighborhood in the set $J^{core}$ where as, in shaving, we measure w.r.t the ambient set $X^{trim}$. It will be more useful to think of this as *trimming* with $J^{reg} = X - X^{trim}$ and $J^{core} = X^{trim}$.

**Claim (Shaving implies universality).** Let $S \subseteq V(G)$ and $(J^{core}, J^{reg})$ be the partition of $V(G) - S$ computed by `Proc-Degree-Pruning` with $d= h/(32 \log n)$. Then:
* $J^{reg}$ is $h$-universal w.r.t. $S$,
* The minimum degree in $G(J^{core})$ is at least $h/(32 \log n)$.

*Proof direction.* We have to show that for any $u \in J^{reg}$ (and any vertex set $R$ of size at most $h/\Delta$) there is a path that connects it to $S$ (avoiding $R$) of length $\log n$. We show the following:
* For any vertex $u \in J^{reg}$, there is at least $h/\Delta$ many vertex disjoint paths connecting $u$ to $S$. The fact that $|R| < h /\Delta$ means that there is at least one such path which cannot have any intersection with $R$, and we are done.

We show that a weaker version of decomposition (sans universality) is enough to give us the required theorem when we are allowed to shave.


==Theorem 4.9 + Shaving implies universality $\Rightarrow$ Theorem 5.2. The idea is to use Theorem 5.2 with shaving recursively.==
* Start with ${\cal F}_1 = \emptyset, J^{1,reg} = \emptyset, J^{1,core} = V(G)$. Set $\tilde G_1 = G[J^{1,core}]$.
* Apply Theorem 5.2 on (every connected component of) $\tilde G_1$. Let ${\cal F}'_1$ be the core-decomposition. Set ${\cal F}_2 = {\cal F}_1 \cup {\cal F}'_1$.
* Let $S^2 = \bigcup K$ is the union of all cored from ${\cal F}_2$ and $J^2 = V(G) - S^2$. Shave $J^2$ into $J^{2, reg}, J^{2,core}$.
* Check if $J^{2,core} = \emptyset$. If yes, **terminate**. If note, set $\tilde G_2 = G[J^{2,core}]$ and apply Theorem 5.2 on it. Continue so on.

### New core decomposition

* Core: $\phi$-expanders with degree $\Omega(n / \lambda)$. # expander $\leq n/\lambda\phi$
* Non-core nodes: Each has $\lambda$ many vertex disjoint path to a core.

Use theorem 1.2 from [SW](https://arxiv.org/pdf/1812.08958.pdf)