Let $n$ be some sufficiently large positive integer and let $V$ be a set of $n$ vertices. Are there always disjoint sets of edges $E_1,\ldots, E_{\log n}$ such that $G_i = (V,E_i), \forall i = 1,\ldots, \log n$, is an edge expander graph with a bounded degree? The number of edges in $E_i$ has to be $\Omega(n)$. Note that $E_1,\ldots, E_{\log n}$ can be any edges out of the $n \choose 2$ potential edges.
5
-
$\begingroup$ It seems possible that this is a consequence of the regularity lemma, have you tried applying it? $\endgroup$– Daniel WeberCommented Jul 29 at 7:14
-
3$\begingroup$ You need to add some lower bound on the number of edges, of the graph is empty this is obviously false $\endgroup$– Daniel WeberCommented Jul 29 at 7:19
-
$\begingroup$ My goal is only to show that there are such graphs. Of course, this does not hold if there are no edges, but I assume that the number of edges is $\Theta(n)$. $\endgroup$– JohnCommented Jul 29 at 8:27
-
$\begingroup$ I am unsure how this follows directly from the regularity lemma, although I am not an expert in this subject. $\endgroup$– JohnCommented Jul 29 at 8:35
-
$\begingroup$ Is your last sentence supposed to mean that you take the disjoint expanders as subgraphs of a complete graph, i.e. the edge sets $E_i$ are just disjoint subsets of $n \choose 2$? $\endgroup$– Felix SchröderCommented Jul 31 at 14:39
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Yes, and you can find many more than $\log n$ of them.
Take an expander $G$ (for example a random cubic graph). Take $k$ copies, where $k=o(n^{1/2})$. Now randomly relabel each copy. The probability of them becoming edge-disjoint is small, but not zero.
Apply Theorem 2.5 in this paper repeatedly.
It wouldn't even surprise me if the complete graph can be partitioned into expanders of bounded degree, but I don't know how to prove that.
answered Jul 29 at 14:59
$\begingroup$
$\endgroup$
One can even partition the edges of $K_n$ into bounded-degree expanders. Let $\epsilon > 0$ be small and $n$ be sufficiently large. Let $H$ be an $n$-vertex edge-expander with $\Delta(H) \leq 3$. Then it is $3$-degenerate, and by a result of Allen, Böttcher, Hladký and Piguet one can find edge-disjoint copies $H_1, \dotsc, H_t$ of $H$ in $K_n$ which leave at most $\epsilon n^2$ unused edges, and moreover the graph $L$ consisting of the leftover edges has maximum degree at most $\epsilon n$. Note that $t \approx n/3$. Using Vizing's theorem, decompose the edges of $L$ into $\ell \leq \epsilon n$ matchings $M_1, \dotsc, M_\ell$. We have $\ell \leq t$, so we can assign each of the matchings to a different graph $H_i$, i.e. let $H'_i = H_i \cup M_i$ for $i \leq \ell$ and $H'_i = H_i$ for $\ell < i \leq t$. Then each $H'_i$ is still a expander and has maximum degree at most $\Delta(H) + 1 = 4$, as required.
