The isoperimetric constant of the random graph process
| dc.creator | Benjamini, Itai | |
| dc.creator | Haber, Simi | |
| dc.creator | Krivelevich, Michael | |
| dc.creator | Lubetzky, Eyal | |
| dc.date | 2005-09-01 | |
| dc.date.accessioned | 2026-07-07T05:22:53Z | |
| dc.date.available | 2026-07-07T05:22:53Z | |
| dc.description | The isoperimetric constant of a graph $G$ on $n$ vertices, $i(G)$, is the minimum of $\frac{|\partial S|}{|S|}$, taken over all nonempty subsets $S\subset V(G)$ of size at most $n/2$, where $\partial S$ denotes the set of edges with precisely one end in $S$. A random graph process on $n$ vertices, $\widetilde{G}(t)$, is a sequence of $\binom{n}{2}$ graphs, where $\widetilde{G}(0)$ is the edgeless graph on $n$ vertices, and $\widetilde{G}(t)$ is the result of adding an edge to $\widetilde{G}(t-1)$, uniformly distributed over all the missing edges. We show that in almost every graph process $i(\widetilde{G}(t))$ equals the minimal degree of $\widetilde{G}(t)$ as long as the minimal degree is $o(\log n)$. Furthermore, we show that this result is essentially best possible, by demonstrating that along the period in which the minimum degree is typically $Θ(\log n)$, the ratio between the isoperimetric constant and the minimum degree falls from 1 to 1/2, its final value. | |
| dc.identifier | https://arxiv.org/abs/math/0509022 | |
| dc.identifier | http://arxiv.org/abs/math/0509022 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/76234 | |
| dc.subject | Probability | |
| dc.subject | Combinatorics | |
| dc.title | The isoperimetric constant of the random graph process | |
| dc.type | text |