\(\newcommand{\fA}{\mathfrak{A}} \newcommand{\fB}{\mathfrak{B}} \newcommand{\fC}{\mathfrak{C}} \DeclareMathOperator{\Res}{Res} \newcommand{\fD}{\mathfrak{D}} \newcommand{\fE}{\mathfrak{E}} \newcommand{\fF}{\mathfrak{F}} \newcommand{\fG}{\mathfrak{G}} \newcommand{\fH}{\mathfrak{H}} \newcommand{\fI}{\mathfrak{I}} \newcommand{\fJ}{\mathfrak{J}} \newcommand{\fK}{\mathfrak{K}} \newcommand{\fL}{\mathfrak{L}} \newcommand{\fM}{\mathfrak{M}} \newcommand{\fN}{\mathfrak{N}} \newcommand{\fO}{\mathfrak{O}} \newcommand{\fP}{\mathfrak{P}} \newcommand{\fQ}{\mathfrak{Q}} \newcommand{\fR}{\mathfrak{R}} \newcommand{\fS}{\mathfrak{S}} \newcommand{\fT}{\mathfrak{T}} \newcommand{\fU}{\mathfrak{U}} \newcommand{\fV}{\mathfrak{V}} \newcommand{\fW}{\mathfrak{W}} \newcommand{\fX}{\mathfrak{X}} \newcommand{\fY}{\mathfrak{Y}} \newcommand{\fZ}{\mathfrak{Z}} \newcommand{\cA}{\mathcal{A}} \newcommand{\cB}{\mathcal{B}} \newcommand{\cC}{\mathcal{C}} \newcommand{\cD}{\mathcal{D}} \newcommand{\cE}{\mathcal{E}} \newcommand{\cF}{\mathcal{F}} \newcommand{\cG}{\mathcal{G}} \newcommand{\cH}{\mathcal{H}} \newcommand{\cI}{\mathcal{I}} \newcommand{\cJ}{\mathcal{J}} \newcommand{\cK}{\mathcal{K}} \newcommand{\cL}{\mathcal{L}} \newcommand{\cM}{\mathcal{M}} \newcommand{\cN}{\mathcal{N}} \newcommand{\cO}{\mathcal{O}} \newcommand{\cP}{\mathcal{P}} \newcommand{\cQ}{\mathcal{Q}} \newcommand{\cR}{\mathcal{R}} \newcommand{\cS}{\mathcal{S}} \newcommand{\cT}{\mathcal{T}} \newcommand{\cU}{\mathcal{U}} \newcommand{\cV}{\mathcal{V}} \newcommand{\cW}{\mathcal{W}} \newcommand{\cX}{\mathcal{X}}\newcommand{\cx}{\chi} \newcommand{\cY}{\mathcal{Y}} \newcommand{\cZ}{\mathcal{Z}} \DeclareMathOperator{\Aut}{Aut} \newcommand{\bA}{\mathbb{A}} \newcommand{\bB}{\mathbb{B}} \newcommand{\bC}{\mathbb{C}} \newcommand{\bD}{\mathbb{D}} \newcommand{\bE}{\mathbb{E}} \newcommand{\bF}{\mathbb{F}} \newcommand{\bG}{\mathbb{G}} \newcommand{\bH}{\mathbb{H}} \newcommand{\bI}{\mathbb{I}} \newcommand{\bJ}{\mathbb{J}} \newcommand{\bK}{\mathbb{K}} \newcommand{\bL}{\mathbb{L}} \newcommand{\bM}{\mathbb{M}} \newcommand{\bN}{\mathbb{N}} \newcommand{\bO}{\mathbb{O}} \newcommand{\bP}{\mathbb{P}} \newcommand{\bQ}{\mathbb{Q}} \newcommand{\bR}{\mathbb{R}} \newcommand{\bS}{\mathbb{S}} \newcommand{\bT}{\mathbb{T}} \newcommand{\bU}{\mathbb{U}} \newcommand{\bV}{\mathbb{V}} \newcommand{\bW}{\mathbb{W}} \newcommand{\bX}{\mathbb{X}} \newcommand{\bY}{\mathbb{Y}} \newcommand{\bZ}{\mathbb{Z}} \newcommand{\ce}{\mathcal{e}} \newcommand{\fe}{\mathfrak{e}} \newcommand{\p}{\overline{p}} \DeclareMathOperator{\im}{im} \DeclareMathOperator{\rank}{rank} \DeclareMathOperator{\coker}{coker} \DeclareMathOperator{\rad}{rad} \DeclareMathOperator{\spec}{Spec} \DeclareMathOperator{\diam}{diam} \DeclareMathOperator{\maxspec}{maxSpec} \DeclareMathOperator{\Ann}{Ann} \DeclareMathOperator{\Ass}{Ass} \require{AMScd}\)

Sunday, January 20, 2019

Diameter of random graph.

Proposition. For a fixed $p\in (0,1)$ almost every graph in $G(n,p)$ has diameter $2$.

Proof.  Note first that a graph $G$ in $G(n,p)$ has diameter $1$ iff it's a complete graph in $n$ vertices, so that $P(\diam G=1)=p^{\binom{n}{2}}\to 0$ when $n\to\infty$. So, if we prove that almost every graph in $G(n,p)$ has diameter $\leq 2$ we're done.

Suppose a graph $G$ has diameter $>2$. Then there are two vertices $u,v$ such that $d(u,v)>2$, so that $N(u)\cap N(v)=\varnothing$. Conversely, if this last property holds for some graph, the graph must indeed have diameter $>2$. So, to prove that almost every graph in $G(n,p)$ has diameter $2$ we need to prove that almost every graph in $G(n,p)$ does not have vertices with disjoint neighborhoods. Consider the following random variable on $G(n,p)$:
$$X(G)=|S(G)|$$
where $S(G)=\{(u,v)\in V(G)\times V(G)\mid N(u)\cap N(v)=\varnothing\}$, so that a graph in $G(n,p)$ will have diameter $\leq 2$ iff $X(G)=0$.

By Markov's inequality,
$$P(X\geq 1)\leq E(X),$$
so we're left to prove that $\lim_{n\to\infty} E(X)=0$.
Now, $E(X)=\sum_{G\in G(n,p)}P(G)X(G)$.

For a given vertex $x\in V(G)$, the probability of it being adjacent to both vertices $u,v$ is $p^2$, so the probability of $x\notin N(u)\cap N(v)$ is $1-p^2$, so $P(N(u)\cap N(v)=\varnothing)=(1-p^2)^{n-2}$. Also $P(uv\notin E(G))=1-p$.

So,
$$E(X)=\binom{n}{2} (1-p)(1-p^2)^{n-2}.$$
Letting $n\to\infty$, since $|1-p^2|<1$, $(1-p^2)^{n-2}\to 0$ and $\lim_{n\to \infty} E(X)=0$.

Thus $\lim_{p\to \infty} P(X\geq 1)=0$, so that almost every graph in $G(n,p)$ has no such vertices $u,v$, and therefore almost every graph in $G(n,p)$ has diameter $\leq 2$, and still almost every such graph has diameter $2$.
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)