pith. sign in

arxiv: math/0509022 · v1 · submitted 2005-09-01 · 🧮 math.PR · math.CO

The isoperimetric constant of the random graph process

classification 🧮 math.PR math.CO
keywords widetildegraphdegreeconstantisoperimetricminimumprocessvertices
0
0 comments X
read the original abstract

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 $\Theta(\log n)$, the ratio between the isoperimetric constant and the minimum degree falls from 1 to 1/2, its final value.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.