Exploring connectivity of random
subgraphs of a graph.

Connectivity of random subgraphs of Cartesian products of $K_{2}$, $K_{3}$,
and $P_{3}$. A survey of uniformly most reliable networks.

BEHRANG MAHJANI
Supervisor: Jeffrey Steif

Department of Mathematical Sciences
CHALMERS UNIVERSITY OF TECHNOLOGY
Division of Engineering Mathematics
Göteborg, Sweden, 2010

Exploring connectivity of random subgraphs of a graph.
Connectivity of random subgraphs of Cartesian products of $K_{2}$, $K_{3}$,
and $P_{3}$. A survey of uniformly most reliable networks.
BEHRANG MAHJANI
©BEHRANG MAHJANI, 2010.
Department of Mathematical Sciences
Chalmers University of Technology
SE-412 96 Göteborg
Sweden
Telephone + 46 (0)31-772 1000

Exploring connectivity of random subgraphs of a graph
Connectivity of random subgraphs of Cartesian products of $K_{2}$, $K_{3}$,
and $P_{3}$. A survey of uniformly most reliable networks.
BEHRANG MAHJANI
Department of Mathematical Sciences
Chalmers University of Technology

Abstract

This work is divided into two main parts. The first part is devoted to
exploring the connectivity of random subgraphs of cartesian products of
$K_{1}$, $K_{2}$, and $P_{3}$. In the second part, the author presents a short
review of the results about network reliability.

The cartesian product of $K_{2}$, the complete graph with 2 vertices, is the
cube graph $Q^{n}$. A random subgraph of $Q^{n}$, $Q^{n}_{p_{n}}$, contains
all vertices of $Q^{n}$, and each edge of $Q^{n}$ independently with
probability $p_{n}$. One can call $p_{n}$ the percolation parameter. The
author explains in detail that for $p_{n}\geq 1-(1/2)(\log n)^{1/n}$,
$Q^{n}_{p_{n}}$ has no components with size larger than $1$ and smaller than
$2^{n}$, as $n\rightarrow\infty$. It is also explained that for
$p_{n}=1-(1/2)\lambda^{1/n}(1+o(1/n))$, the probability that $Q_{p_{n}}^{n}$
has no isolated point, as $n\rightarrow\infty$, tends to $e^{-\lambda}$;
hence, the probability that $Q_{p_{n}}^{n}$ is connected tends to
$e^{-\lambda}$. For constant percolation values larger than $1/2$, when $n$
tends to infinity, almost every random subgraph of $Q^{n}$ is connected; for
percolation values smaller than $1/2$, when $n$ tends to infinity, almost no
random subgraph of $Q^{n}$ is connected; and for percolation values equal
$1/2$, when $n$ tends to infinity, the probability that $Q^{n}_{1/2}$ is
connected tends to $e^{-1}$. At the end of this section, a comparison between
connectivity of a typical random graph with $M$ edges and $N$ vertices, $G\in
G(N=2^{n},M=n2^{n-1})$, and $Q^{n}$, after percolation with the parameter
$p_{n}$ is presented.

This work continues with exploring the threshold function for the cartesian
product of $K_{3}$, the complete graph with 3 vertices, denoted by
${}^{3}Q^{n}$. It is shown that for $p_{n}\geq 1-(1/\sqrt{3})(\log n)^{1/n}$,
${}^{3}Q_{p_{n}}^{n}$ has no components with size larger than $1$ and smaller
than $3^{n}$, as $n\rightarrow\infty$. Then, it is proved that for
$p_{n}=1-(1/\sqrt{3})\lambda^{1/2n}(1+o(1/n))$, the probability that
${}^{3}Q_{p_{n}}^{n}$ has no isolated point, as $n\rightarrow\infty$, tends to
$e^{-\lambda}$; hence, the probability that $Q_{p_{n}}^{n}$ is connected tends
to $e^{-\lambda}$. At last, the author suggests that the threshold value for
connectivity of the cartesian product of $P_{3}$, where $P_{3}$ is a path with
length $2$, denoted by $P_{3}^{n}$, is $2-\sqrt{2}$. One can show that for
percolation values smaller than $2-\sqrt{2}$, almost no random subgraph of
$P_{3}^{n}$ is connected, and for percolation values larger than $2-\sqrt{2}$,
almost every random subgraph of $P_{3}^{n}$ has no isolated point. The author
also shows that for percolation values larger than $0.68$ almost all random
subgraphs of $P_{3}^{n}$ are connected.

The last part of this work, sheds light on reliability of networks. The main
question in this part is: one is given 2 parameters, $n$ and $m$ where $n$ and
$m$ are positive integers. Among all graphs with $n$ vertices and $m$ edges,
which graph $G$, if any, maximizes the probability that when one does
percolation on $G$ with the parameter $p_{n}$, for all $p_{n}$ in $(0,1)$
there is one component? $G$ would be called the uniformly optimally reliable
graph (UOR graph) for the parameter $n$ and $m$. It is shown in this part, for
some $m$ and $n$ there is no UOR graph, since the graph which maximizes the
probability of connectivity depends on $p_{n}$ in that family of graphs. A
review of results about when the UOR graph exists is presented in this part.

Keywords: Random subgraphs, percolation, n-cube, path graph, reliable
networks.

ACKNOWLEDGMENTS

I would like to express my deepest gratitude to Professor Jeffrey Steif for
his supervision and guidance in this thesis. His invaluable comments and
suggestions were of enormous help during this research work. My special thanks
are due to my parents who supported me and made it possible for me to continue
my studies.

###### Contents

  1. 1 Introduction
  2. 2 Graph theory background
    1. 2.1 Graph models and their matrix representation
    2. 2.2 Connectivity
  3. 3 Random graph theory background
    1. 3.1 Evolution of Erdõs Rényi graphs
    2. 3.2 Properties of almost every graphs
    3. 3.3 Probabilistic methods
  4. 4 Connected random subgraphs of the cube
    1. 4.1 Isolated vertices
    2. 4.2 Isoperimetric problem for the cube
    3. 4.3 Isolated components of size larger than 2 and smaller than $2^{n}$
    4. 4.4 Comparison between a typical random graph and $Q^{n}$
  5. 5 Connected random subgraphs of the 3-cube
    1. 5.1 Isolated vertices
    2. 5.2 Isoperimetric problem for the 3-cube
    3. 5.3 Isolated components of size larger than 2 and smaller than $3^{n}$
  6. 6 Connected random subgraph of the $P_{3}$-product
    1. 6.1 Isolated vertices
    2. 6.2 Isolated components of size larger than 2 and smaller than $3^{n}$
  7. 7 Reliable networks
    1. 7.1 All terminal reliability
    2. 7.2 Random accessibility
  8. References

##  Chapter 1 Introduction

Exploring the connectivity of random subgraphs of different families of graphs
is one of the most interesting topics in random graphs and percolation theory.
A random subgraph of a graph $G(V_{n},E_{m})$ is a graph which contains all
vertices of $G$, and each edge of $G$ independently with probability $p_{n}$.
$p_{n}$ is known as the percolation parameter. Connectivity of a random
subgraph of a graph can be investigated both for small and considerably large
(when $n$ tends to infinity) graphs. For considerably large graphs, the first
step in exploring the connectivity is to calculate $p_{c}$ which for all
constant $p=p_{n},p\in(0,1)$ and $p<p_{c}$, as $n$ tends to infinity, almost
all random subgraphs of $G(V_{n},E_{m})$ is connected; but for all $p\in(0,1)$
and $p>p_{c}$, as $n$ tends to infinity, almost no random subgraphs of
$G(V_{n},E_{m})$ is connected. The second step is to investigate what happens
when $p=p_{c}$. A more complete approach is to calculate $p_{c}$ when $p_{c}$
depends on $n$.

For small graphs, it is of interest to find the uniformly optimally reliable
graph (UOR graph). Consider $G(n,m)$ as the family of graphs with $n$ vertices
and $m$ edges. The UOR graph is the graph $G\in G(n,m)$ that maximizes the
probability that $G$ is connected after percolation with the parameter $p_{n}$
for fixed $n,m$ and all $p_{n}\in(0,1)$.

One of the interesting graphs for analyzing the connectivity of its random
subgraphs is the cube graph. The cube graph $Q^{n}$, is a graph with the
vertices labeling $1,2,3,4,...,2^{n}-1$. Two vertices in this graph are
adjacent if their binary representation differs only in one digit. Another way
to define $Q^{n}$ is using the cartesian products of $n$ copies of $K_{2}$,
where $K_{n}$ is the complete graph with $n$ vertices. It is shown by Paul
Erdös and Joel Spencer [4] that $p_{c}=1/2$ for $Q^{n}$. An extension of
$Q^{n}$ is the graph with the vertices labeling $1,2,3,4,...,3^{n}-1$, where
two vertices in this graph are adjacent if their ternary representation
differs only in one digit. We call this graph 3-cube denoted by ${}^{3}Q^{n}$.
One can show that ${}^{3}Q^{n}$ is the cartesian product of $K_{3}$.
Connectivity of random subgraphs of the cartesian product of $K_{i}$ is
investigated by Lane Clark [15]. Another extension of $Q^{n}$ is the cartesian
product of $n$ copies of a path with length 2 which we call it $P_{3}^{n}$.

This thesis is divided into two main parts. The first part (chapter 4,5,6) is
devoted to the connectivity of random subgraphs of some considerably large
graphs, and the second part is the connectivity of random subgraphs of small
graphs (chapter 7). Chapter 2 presents a very short review of definition and
results in graph theory. Chapter 3 is a short review of the definitions in
random graph theory; it is explained briefly in this chapter that how small
components construct a giant component and gradually a graph becomes connected
by adding more edges to it. In chapter $4$, the results by Bela Bollobás [1]
on finding $p_{c}$ for connectivity of random subgraphs of $Q^{n}$ is
explained in detail. In chapter $5$ the author calculates $p_{c}$ for
connectivity of random subgraphs of ${}^{3}Q^{n}$. After calculating the
threshold value for the connectivity of random subgraphs of ${}^{3}Q^{n}$, the
author found that this problem is solved for a general case of the random
subgraphs of cartesian product of $K_{i}$ [15]. Chapter $6$ is an approach to
find $p_{c}$ for connectivity of random subgraphs of $P_{3}^{n}$. This work
finishes with chapter $7$ which is a review of the results on finding the UOR
graph. In this chapter it is shown by the author that for some $m$ and $n$
there are no UOR graph.

##  Chapter 2 Graph theory background

This chapter presents s short review of basic definitions in graph theory.
Most of the definitions in this chapter are extracted from [10].

###  2.1 Graph models and their matrix representation

#### Graphs

######  Definition 1.

Graph: A _graph_ $G(V,E)$ is an ordered pair consisting of the set of
_vertices_ $V$, and the set of _edges_ $E$. Each edge is associated with a set
of vertices which are called _endpoints_. Two vertices are _adjacent_ if they
are joined by an edge. Two edges are _adjacent_ if they have a common
endpoint. A vertex is _incident_ to an edge and viceversa, if that vertex is
an endpoint of the edge. A _self-loop_ is an edge which joins a vertex to
itself. A _multi-edge_ is a set of two or more edges having the same
endpoints. A _simple graph_ is a graph without self-loops and multi-edges.

#### Degrees

After defining a graph, it is of interest to get familiar with the
characteristics of different graphs in order to compare them. One of the basic
characteristics is the degree of each vertices.

######  Definition 2.

Degree: The _degree_ of a vertex, denoted by $deg(v)$, is the number of edges
incident on that vertex plus two times the number of its self-loops. The
_smallest degree_ in a graph is denoted by $\delta_{min}$ or $\delta$, and the
_largest degree_ in a graph is denoted by $\delta_{max}$ or $\Delta$. The
_degree sequence_ of a graph is the non-increasing sequence of vertice
degrees.

The first question that comes into mind, after defining the degree sequence of
a graph, is if there exists a degree sequence of a graph for each sequence of
positive integers.

######  Definition 3.

Graphic: A sequence of positive integers is _graphic_ if there is a
permutation of it that is the degree sequence of a simple graph. An explicit
sufficient and necessary condition for a sequence of positive integers to be
graphical is:

######  Theorem 1.

A sequence of non-negative integers $(d_{1},d_{2},...,d_{n})$ is graphical if
and only if

$\displaystyle\sum_{i=1}^{k}deg(i)\leq k(k-1)+\sum_{j=k+1}^{n}min(k,deg(i))$
(2.1)

for each $1\leq k\leq n$ [9].

#### Graph models

There are many types of graphs. Some of the most important types of simple
graphs are:

######  Definition 4.

Common families of graphs: A _complete graph_ $K_{n}$ is a simple graph with
$n$ vertices which every pair of vertices is connected by an edge. A
_bipartite graph_ $G$ is a graph with the set of vertices that can be
partitioned into two subsets $U$ and $W$, such that each edge in $G$ has one
endpoint in $U$ and one endpoint in $W$. A _regular graph_ is a graph where
all vertices have the same degree. A path graph is a simple graph with
$|V|=|E|+1$ that can be drawn, such that all vertices and edges are in a
single straight line. A _path graph_ with $|V|=n$ and $|E|=n-1$ is denoted by
$P_{n}$. A _hypercube graph (cube graph)_ is a simple n-regular graph with the
set of vertices labels from $0$ to $2^{n}-1$, in which two vertices are
adjacent if their binary representation differs only in one digit.

######  Definition 5.

Subgraphs: $H$ _subgraph_ of $G$ is a graph whose vertices and edges are in
$G$. If $V_{G}=V_{H}$ then the subgraph $H$ is said to _span_ the graph $G$.
The _induced subgraph_ on $U\subseteq V_{G}$ of $G$ is the graph whose set of
vertices is $U$, and set of edges is all edges of $G$ with two endpoints in
$U$. The _induced subgraph_ on $D\subseteq E_{G}$ of $G$ is the graph whose
its set of edges is $D$, and its set of vertices is all vertices which are
incident with an edge in $D$. A maximal connected subgraph of a graph $G$ is a
_component_ of $G$.

######  Definition 6.

Cartesian product of a graph: $G\times H$, the _Cartesian product_ of $G$ and
$H$ is the graph with the set of vertices $V_{G}\times V_{H}$ and the set of
edges $(V_{G}\times E_{H})\cup(E_{G}\times V_{H})$.

Defining a walk on a graph can help us to define some important characteristic
of a graph such as connectivity of a graph and spanning trees.

######  Definition 7.

Walk: In a graph $G$, a _walk_ from vertex $v_{0}$ to vertex $v_{n}$ is an
ordered sequence

$\displaystyle W=<v_{0},e_{1},v_{1},e_{2},...,v_{n-1},e_{n},v_{n}>$ (2.2)

of vertices and edges, such that the endpoints of $e_{i}$ is
$\\{v_{i-1},v_{i}\\}$ for $i=1,...,n$. For a simple graph one can abbreviate
the representation as a vertex sequence

$\displaystyle W=<v_{0},v_{1},...,v_{n}>$ (2.3)

######  Definition 8.

Tree, spanning tree: A _path_ is a walk with no repeated vertices (except the
initial and final vertices). A _cycle_ is a nontrivial closed path. A _tree_
is a connected graph without cycle. A spanning tree of a graph is a subgraph
of a graph which is a tree.

#### Matrix representations

The last important concept in this section is that each graph can be presented
as a matrix, as follows:

######  Definition 9.

Matrix representation of a graph: The _adjacency matrix_ of a simple graph $G$
is: $A_{G}[u,v]=\left\\{\begin{array}[]{ll}1,&\hbox{if $u$ and $v$ are
adjacent;}\\\ 0,&\hbox{otherwise.}\\\ \end{array}\right.$ for all pairs of
vertices $u$ and $v$ in $V_{G}$.

###  2.2 Connectivity

Connectivity of a graph is one of the most important property of a graph. A
graph is _connected_ if for every pair of vertices $u$ and $v$, there is walk
from $u$ to $v$. There are different types of connectivity for a graph:

######  Definition 10.

Vertex-connectivity: $\kappa_{v}(G)$, _vertex connectivity_ of a connected
graph $G$, is the minimum number of vertices which its removal will disconnect
$G$ or reduce it to a single vertex graph. A graph $G$ is _k-connected_ if
$\kappa_{v}(G)\geq k$.

######  Definition 11.

Edge-connectivity:$\kappa_{e}(G)$, _edge connectivity_ of a connected graph
$G$, is the minimum number of edges which its removal will disconnect $G$. A
graph $G$ is _k-edge-connected_ if $\kappa_{e}(G)\geq k$

######  Definition 12.

Algebraic connectivity: The _Laplacian matrix_ of a graph is $L:=D-A$, where
$A$ is the adjacency matrix and the $D$ is the diagonal matrix of vertex
outdegrees. The algebraic connectivity of an undirected graph with the
Laplacian matrix $L$ is the second smallest eigenvalue of $L$. If one arranges
the eigenvalues of $L$ as :
$\lambda_{1}(L)\leq\lambda_{2}(L)\leq...\lambda_{n}(L)$, then $\lambda_{2}(L)$
is the algebraic connectivity of a graph. The following theorem presents some
applications of algebraic connectivity:

######  Theorem 2.

For an undirected graph with minimum vertex degree $\delta$ and maximum vertex
degree $\Delta$, we have:

  * •

$\lambda_{2}\geq 0$ with the inequality strict if and only if the graph is
connected.

  * •

$\lambda_{2}\leq\frac{n}{n-1}\delta\leq\frac{n}{n-1}\triangle\leq\lambda_{n}$.

##  Chapter 3 Random graph theory background

A _random graph_ is a graph with a specific number of vertices which adjacency
between two vertices are determined in a random way [10]. In this chapter, we
define Erdõs Rényi random graph, and then we explain briefly some properties
of it.

###  3.1 Evolution of Erdõs Rényi graphs

$G(n,M),0\leq M\leq\binom{n}{2}$, is the equiprobable space of all simple
graphs with the vertex set $V=\\{1,2,...,n\\}$ and $M$ edges. $G(n,p),0<p<1$,
is the collection of all graphs with the vertex set $V=\\{1,2,...,n\\}$ in
which two vertices are connected independently with the probability $p$ [10],
[1].

It is of interest to study the global structure of a random graph of order $n$
(with $n$ vertices) and size M(n) (with $M(n)$ edges). Let us define
$L_{j}(G)$ as the order of the jth largest component of a graph $G$, where if
$G$ has fewer than j components then $L_{j}(G)=0$. Consider the random graph
process $\widetilde{G}=(G_{t})_{t=0}^{N}$ where $G_{t}$ is getting larger by
adding more and more edges. When $t\sim\frac{1}{2}cn$ and $c<1$ then in a.e
$G_{t}$ the maximum of the order of its components is of order $\log n$. When
$c=1$, in a.e $G_{t}$ $L_{1}(G_{\lfloor n/2\rfloor})$ has order $n^{2/3}$.
When $t$ passes $n/2$, $L_{1}(G)$ begins to grow suddenly and the giant
component, which is a component whose order is much larger than other
components, appears. Eventually, small components join the giant component and
the graph becomes connected. Erdõs Rényi proved that $(n/2)\log n$ is the
sharp threshold for connectedness [1]. The following theorem illustrates this
fundamental result:

######  Theorem 3.

Let $c\in\mathbb{R}$ be fixed and let $M=(n/2)\\{\log
n+c+o(1)\\}\in\mathbb{N}$ and $p=\\{\log n+c+o(1)\\}/n$. Then [1]:

$\displaystyle\textbf{P}(G_{M}\text{ is connected})\rightarrow
e^{-e^{-c}}\text{ as }n\rightarrow\infty$ (3.1)

and

$\displaystyle\textbf{P}(G_{p}\text{ is connected})\rightarrow
e^{-e^{-c}}\text{ as }n\rightarrow\infty.$ (3.2)

For more information regarding random graphs one can check [1], [2], [13],
[14].

###  3.2 Properties of almost every graphs

A graph property $T$ is true for almost every (all) graph if for fixed
$p=p(n)$ [3]:

$\displaystyle\lim_{n\rightarrow\infty}\textbf{P}(G\in G(n,p)\text{ and
}G\text{ has property T})=1\text{ for }p>0$ (3.3)

Some of the important ”almost every graph properties” are:

######  Theorem 4.

For any integer $r\geq 1$ and all $p\in(0,1)$, almost every graph contains
$K_{r}$ [10].

######  Theorem 5.

Almost every graph is connected for all $p\in(0,1)$ [10].

######  Theorem 6.

For $k\in\mathbb{N}$ and all $p\in(0,1)$, almost every graph is k-connected
[10].

###  3.3 Probabilistic methods

Usually, the goal in the probabilistic method is to prove the existence of a
combinatorial structure with a certain property. The usual approach in these
methods is to first construct a suitable probability space, then show that
there exists a random object in that space with the desired properties [11].
Sometimes it is not easy to find the desired object, instead one proves that
there is an object which _almost_ satisfies the desired conditions [12].
Usually, it is possible to modify the almost close object in a deterministic
way so that one gets the desired object. Markov’s inequality, and Chebyshev
inequality are two important inequalities used for this purpose. An important
concept in probabilistic methods is the definition of threshold function,
which is:

######  Definition 13.

$r(n)$ is called a threshold function for a graph property $T$ for $G(n,M(n))$
if:
1\. When $\lim_{n\rightarrow\infty}\frac{M(n)}{r(n)}=0$ almost every graphs do
not satisfy $T$.
2\. When $\lim_{n\rightarrow\infty}\frac{M(n)}{r(n)}=1$ almost every graphs
satisfy $T$.

##  Chapter 4 Connected random subgraphs of the cube

111The proof presented in this chapter is based on the proof presented by
B.Bollobás in [1] p.384-393.

The cube graph, $Q^{n}$, is a graph with $2^{n}$ vertices. If one labels each
vertex of $Q^{n}$ from $0$ to $2^{n}-1$, then two vertices are adjacent if
their binary representation differs only in one digit. Hence, one can conclude
that each vertex in $Q^{n}$ is connected to $n$ other vertices. In other
words, $Q^{n}$ has $n2^{n-1}$ edges. A random subgraph of $Q^{n}$ is denoted
by $Q_{p_{n}}^{n}$. $Q_{p_{n}}^{n}$ contains all vertices of $Q^{n}$, and each
edge of $Q^{n}$ independently with probability $p_{n}$.

It is of interest in this chapter to explore a critical value $p_{c}$, which
for fixed values of $p$ if $p<p_{c}$ then the probability that $Q_{p_{n}}^{n}$
is connected, as $n\rightarrow\infty$, tends to $0$; but if $p>p_{c}$ then the
probability that $Q_{p_{n}}^{n}$ is connected, as $n\rightarrow\infty$, tends
to $1$. Burtin proved that this critical value is $1/2$ [6]. Later, P.Erdös
and J.Spencer proved that for $p=1/2$ the probability that $Q_{p_{n}}^{n}$ is
connected, as $n\rightarrow\infty$, tends to $e^{-1}$ [4].

In the first section of this chapter, first the probability that
$Q_{p_{n}}^{n}$ has no isolated point as $n\rightarrow\infty$, for fixed $p$,
is investigated. It is proved that for $p<1/2$ the probability that
$Q_{p_{n}}^{n}$ has no isolated point, as $n\rightarrow\infty$, tends to $0$.
Therefore, for $p<1/2$ the probability that $Q_{p_{n}}^{n}$ is connected, as
$n\rightarrow\infty$, tends to $0$. Then it is proved that, for $p>1/2$ the
probability that $Q_{p_{n}}^{n}$ has no isolated point, as
$n\rightarrow\infty$, tends to $1$. In the next step, the probability that
$Q_{p_{n}}^{n}$ has no isolated point, as $n\rightarrow\infty$, when $p$
depends on $n$ and it is close $1/2$, is explored. It is proved that for
$\lambda(n)=\lambda>0$ and $p_{n}=1-(1/2)\lambda^{1/n}(1+o(1/n))$, the
probability that $Q_{p_{n}}^{n}$ has no isolated point, as
$n\rightarrow\infty$, tends to $e^{-\lambda}$ [1]. Finally, it is proved that,
for fixed $p=1/2$ the probability that $Q_{p_{n}}^{n}$ has no isolated point,
as $n\rightarrow\infty$, tends to $e^{-1}$. These results are based on P.Erdös
and J.Spencer’s work [4].

In the second section, one sheds light on the Isoperimetric problem, which is
the problem of finding an inequality which relates the size of a subgraph to
the size of its boundary. The solution to this problem for $Q_{p_{n}}^{n}$ is
presented by S.Hart [5]. One needs such an inequality to explore the
probability that $Q_{p_{n}}^{n}$ has a component which is not the whole graph.

In the last section, the Isoperimetric inequality is applied to prove that
when $p$ depends on $n$ and $p_{n}\geq 1-(1/2)(\log n)^{1/n}$, then the
probability that there are no components with size larger than $1$ and smaller
than $2^{n}$ in $Q_{p_{n}}^{n}$ , as $n\rightarrow\infty$, tends to $1$.
Therefore, for $p_{n}=1-(1/2)\lambda^{1/n}(1+o(1/n))$, the probability that
$Q_{p_{n}}^{n}$ is connected, as $n\rightarrow\infty$, tends to
$e^{-\lambda}$. Finally, as a special case, it is shown that, for fixed $p$ if
$p=1/2$, the probability that $Q_{p_{n}}^{n}$ is connected , as
$n\rightarrow\infty$, tend to $e^{-1}$; and if $p>1/2$, the probability that
$Q_{p_{n}}^{n}$ is connected, as $n\rightarrow\infty$, tends to $1$.

###  4.1 Isolated vertices

For $p<0.5$:
Assume $p$ is fixed and $p<0.5$. First, consider the following definitions:

######  Definition 14.

$f_{n}(p_{n})$:=P($Q_{p_{n}}^{n}$ is connected)

######  Definition 15.

$g_{n}(p_{n}):=\textbf{P}(Q_{p_{n}}^{n}\text{contains an isolated point})$

######  Definition 16.

$X_{i}(n):=\left\\{\begin{array}[]{ll}1&\mbox{Vertex $i$ is isolated, $i\in
V(Q_{p_{n}}^{n}$)};\\\ 0&\mbox{Vertex $i$ is NOT isolated, $i\in
V(Q_{p_{n}}^{n}$)}.\end{array}\right.$ , and $X(n):=\displaystyle\sum_{i\in
V(Q_{p_{n}}^{n})}X_{i}(n)$.

Now, calculate $E[X(n)]$ and $Var[X(n)]$ as follows:

$\displaystyle\mu:=E[X(n)]=\sum_{i\in V(Q_{p_{n}}^{n})}E[X_{i}(n)]=\sum_{i\in
V(Q_{p_{n}}^{n})}(1-p)^{n}=2^{n}(1-p)^{n}$ (4.1) $\displaystyle
Var[X(n)]=\displaystyle\sum_{i\in
V(Q_{p_{n}}^{n})}Var[X_{i}(n)]+\displaystyle\sum_{i\neq j;i,j\in
V(Q_{p_{n}}^{n})}Cov[X_{i}(n),X_{j}(n)]$ (4.2)

where, $Var[X_{i}(n)]$ and $Cov[X_{i}(n),X_{j}(n)]$ are equal to:

$\displaystyle\displaystyle\sum_{i\in V(Q_{p_{n}}^{n})}Var[X_{i}(n)]$
$\displaystyle=2^{n}(1-p)^{n}-2^{n}(1-p)^{n}(1-p)^{n}=\mu-\mu(1-p)^{n}$ (4.3)
$\displaystyle Cov[X_{i}(n),X_{j}(n)]$
$\displaystyle=E[X_{i}(n)X_{j}(n)]-E[X_{i}(n)]E[X_{j}(n)]$ (4.4)
$\displaystyle=\left\\{\begin{array}[]{ll}0&\mbox{i,j not adjacent};\\\
(1-p)^{n}(1-p)^{n-1}-(1-p)^{n}(1-p)^{n}=\frac{\mu^{2}}{2^{2n}}(\frac{p}{1-p})&\mbox{i,j
adjacent}.\end{array}\right.$ (4.7)

and finally:

$\displaystyle
Var[X(n)]=\mu-\mu(1-p)^{n}+\frac{\mu^{2}}{2^{n}}(\frac{np}{1-p})=\mu+\mu(1-p)^{n}(\frac{np}{1-p}-1)$
(4.8)

Now, since we have $Var[X(n)]$, we can use Chebyshev’s inequality to estimate
$g_{n}(p)$. Chebyshev’s inequality states that:

$\displaystyle
1-g_{n}(p)=\textbf{P}[X(n)=0]\leq\textbf{P}[|X(n)-\mu|\geq\mu]\leq\frac{Var[X(n)]}{\mu^{2}}$
(4.9)

By applying Chebyshev’s inequality when $p<0.5$, one gets
$Var[X(n)]/\mu^{2}\rightarrow 0$, as $n\rightarrow\infty$. Therefore
$\lim_{n\rightarrow\infty}g_{n}(p)=1$. And finally, since $f_{n}(p)\leq
1-g_{n}(p)$, then for $p<0.5$ the probability that $Q_{p_{n}}^{n}$ is
connected for $p<0.5$, as $n\rightarrow\infty$, tends to $0$. $\blacksquare$

For $p>0.5$:
Assume $p$ is fixed and $p>0.5$. In order to calculate $g_{n}(p)$ when
$p>0.5$, as $n\rightarrow\infty$, one can use the following inequality:

$\displaystyle g_{n}(p)=\textbf{P}[X(n)>0]\leq E[X(n)]=\mu$ (4.10)

Since $E[X(n)]\rightarrow 0$ as $n\rightarrow\infty$, then
$\lim_{n\rightarrow\infty}g_{n}(p)=0$. This means that the probability that
there are no isolated points in $Q_{p_{n}}^{n}$ for $p>0.5$, as
$n\rightarrow\infty$, tends to $1$. $\blacksquare$

For $p_{n}=1-(1/2)\lambda^{1/n}(1+o(1/n))$:
One needs the following theorem from [1] to find the distribution of $X(n)$
(distribution of the number of isolated points).

######  Theorem 7.

Let $\lambda=\lambda(n)$ be a non-negative bounded function on N. Suppose the
non-negative integer valued random variables $X(1),X(2),...$ are such that:

$\displaystyle\lim_{n\rightarrow\infty}\\{E_{r}[X(n)]-\lambda^{r}\\}=0,\text{
}r=0,1,...$ (4.11)

where $E_{r}[X]$ is the $r$th factorial moment of $X$, i.e.
$E_{r}[X]=E[(X)_{r}]$. Then

$\displaystyle X(n)\stackrel{{\scriptstyle
d}}{{\longrightarrow}}\textbf{P}_{\lambda}$ (4.12)

Use the definition of $X(n)$ presented in definition 16. The goal is to
calculate $E[X(n)]$.

$\displaystyle E_{r}[X(n)]=E[X(n)(X(n)-1)(X(n)-2)...(X(n)-r+1)]$ (4.13)

Since $X(n):=\sum_{i\in V(Q_{p_{n}}^{n})}X_{i}(n)$ and $X_{i}$’s are indicator
functions, therefore:

$\displaystyle
X(n)(X(n)-1)(X(n)-2)...(X(n)-r+1)=\sum_{(i_{1},i_{2},...,i_{r})}X_{i_{1}}X_{i_{2}}...X_{i_{r}}$
(4.14)

where the sum is over all ordered sets of distinct vertices. Then:

$\displaystyle E_{r}[X(n)]$
$\displaystyle=E[X(n)(X(n)-1)(X(n)-2)...(X(n)-r+1)]$ (4.15)
$\displaystyle=E[\sum_{(i_{1},i_{2},...,i_{r})}X_{i_{1}}X_{i_{2}}...X_{i_{r}}]$
(4.16)
$\displaystyle=\sum_{(i_{1},i_{2},...,i_{r})}\textbf{P}[X_{i_{1}}=1,X_{i_{2}}=1,...,X_{i_{r}}=1]$
(4.17)

One knows that a set of $r$ vertices is incident with at most $rn$ edges.
There are $(r)_{r}\binom{2^{n}}{r}$ ways to choose such $r$ vertices. Hence:

$\displaystyle
E_{r}[X(n)]\geq(r)_{r}\binom{2^{n}}{r}(1-p_{n})^{rn}=(2^{n})_{r}(1-p_{n})^{rn}$
(4.18)

One the other hand, a set of $r$ vertices is incident with at least $r(n-r)$
edges. There are at most $(r-1)_{r-1}\binom{2^{n}}{r-1}(r-1)n$ ways to choose
a set of $r$ vertices in $Q_{p_{n}}^{n}$ where at least two vertices are
adjacent; since if we choose $r-1$ vertices independently, then the last
vertex must be connected to one of the chosen vertices. In other words, there
are at most $(r-1)_{r-1}\binom{2^{n}}{r-1}(r-1)n$ ways to choose $r$ vertices
which some of them are adjacent to each other. Hence:

$\displaystyle E_{r}[X(n)]$
$\displaystyle\leq(2^{n})_{r}(1-p_{n})^{rn}+(r-1)_{r-1}\binom{2^{n}}{r-1}(r-1)n(1-p_{n})^{r(n-r)}$
(4.19)
$\displaystyle\leq(2^{n})_{r}(1-p_{n})^{rn}+(2^{n})_{r}rn(1-p_{n})^{r(n-r)}$
(4.20)
$\displaystyle\leq(2^{n})_{r}(1-p_{n})^{rn}+2^{n(r-1)}rn(1-p_{n})^{r(n-r)}$
(4.21)

Finally from 4.18 and 4.21 one gets:

$\displaystyle(2^{n})_{r}(1-p_{n})^{rn}\leq
E_{r}[X(n)]\leq(2^{n})_{r}(1-p_{n})^{rn}+2^{n(r-1)}rn(1-p_{n})^{r(n-r)}$
(4.22)

which gives:

$\displaystyle(2(1-p_{n}))^{rn}(1-\frac{r}{2^{n}})^{r}\leq
E_{r}[X(n)]\leq(2(1-p_{n}))^{rn}\\{1+2^{-n}rn(1-p_{n})^{-r^{2}}\\}$ (4.24)

Since $r$ is fixed and $\lim_{n\rightarrow\infty}(2(1-p_{n}))^{n}=\lambda$,
then:

$\displaystyle\lim_{n\rightarrow\infty}(E_{r}[X(n)])=\lambda^{r}\text{ for
r=0,1,2,...}$ (4.25)

This shows that $X(n)\stackrel{{\scriptstyle
d}}{{\longrightarrow}}\textbf{P}_{\lambda}$. $\blacksquare$

For $p=0.5$:
In the calculation of $p_{n}=1-1/2\lambda^{1/n}(1+o(1/n))$, if we fix $p=1/2$
and let $\lambda=1$, then we get that the distribution of $X(n)$ , as
$n\rightarrow\infty$, tends to a Poisson distribution with mean $1$.
Therefore, one can conclude:

$\displaystyle\lim_{n\rightarrow\infty}(1-g_{n}(p))=\lim_{n\rightarrow\infty}(\textbf{P}(X(n)=0))=e^{-1}$
(4.26)

This shows that for $p=1/2$ the probability that $Q_{p_{n}}^{n}$ has no
isolated point, as $n\rightarrow\infty$, tends to $e^{-1}$. $\blacksquare$

###  4.2 Isoperimetric problem for the cube

One needs an inequality which relates the size of a subgraph of $Q^{n}$ to the
size of its boundary. This inequality will be applied to prove that for fixed
values of $p$ if $p\geq 0.5$, then the probability that subgraphs of $Q^{n}$
do not have a component of size larger than $2$ and smaller than $2^{n}$, as
$n\rightarrow\infty$, tends to $1$. The proof presented here is based on the
proof presented in [1].

######  Definition 17.

The edge boundary $b_{G}(H)$, where $H$ is an induced subgraph of G, is the
number of edges which joins vertices in $H$ to the vertices in $G\backslash
H$.

######  Definition 18.

$b_{G}(m):=\min\\{b_{G}(H),H\text{ is an induced subgraph of }G,|V(H)|=m\\}$.

The main task in this section is to calculate $b_{Q^{n}}(m)$. The answer,
loosely, is if $m=2^{k}$ for some $k<n$ then one should take a k-dimensional
sub-cube of $Q^{n}$ as $b_{Q^{n}}(H)$. If $2^{k}\leq m<2^{k+1}$, for some
$k<n$, then one should choose one side of a $(k+1)-$cube and $m-2^{k}$ more
vertices properly chosen in the other half. Since $Q^{n}$ is n-regular and $H$
is an induced subgraph of $G$ with $|V(H)|=m$, then:

$\displaystyle b_{Q^{n}}(H)$ $\displaystyle=mn-2e(H),\text{where e(H) is the
total number of edges in H.}$ (4.27) $\displaystyle b_{Q^{n}}(m)$
$\displaystyle=mn-2e_{n}(m),\text{where }e_{n}(m)=\max\\{e(H):H\text{ induced
subgraph of }Q^{n},|V(H)|=m\\}.$ (4.28)

######  Definition 19.

$h(i)$ := sum of digits in the binary expansion of $i$ and
$f(l,m):=\displaystyle\sum_{l\leq i<m}h(i)$

######  Lemma 1.

If $1\leq k\leq l$, then $f(l,l+k)\geq f(0,k)+k$

Proof:
Let look at the binary expansion of a few numbers:

$\begin{array}[]{ccccc}Column&3&2&1&0\\\ Bin\backslash
Dec&2^{3}&2^{2}&2^{1}&2^{0}\\\ 0&&&&0\\\ 1&&&&1\\\ 2&&&1&0\\\ 3&&&1&1\\\
4&&1&0&0\\\ 5&&1&0&1\\\ 6&&1&1&0\\\ 7&&1&1&1\\\ 8&1&0&0&0\\\ 9&1&0&0&1\\\
10&1&0&1&0\\\ 11&1&0&1&1\end{array}$

From this representation, one can observe that column $i$ starts with a block
of $2^{i}$ zeros. Therefore, sum of jth digits of $k$ consecutive numbers is
minimal if the first block of $0$’s is as long as possible. Hence, one can
conclude:

$\displaystyle f(l,l+k)\geq f(0,k)$ (4.29)

For every $i$ define $r$ such that $0\leq i\leq 2^{r}-1$. The binary
expansions of $i$ and $2^{r}-1-i$ are symmetric. This means that, if there is
a $1/0$ in an specific location of the binary expansion of $i$ then there is a
$0/1$ in the same location of the binary expansion of $2^{r}-1-i$. Therefore,

$\displaystyle h(i)+h(2^{r}-1-i)=r\text{ for }0\leq i\leq 2^{r}-1$ (4.30)

Consequently, since:

$\displaystyle\displaystyle\sum_{l\leq
i<l+k}h(i)+\displaystyle\sum_{2^{r}-l-k\leq i<2^{r}-l}h(i)=rk$ (4.31)

then:

$\displaystyle f(l,l+k)+f(2^{r}-l-k,2^{r}-l)=rk,\text{if }l+k\leq 2^{r}$
(4.32)

Let us prove lemma 1 with the assumption $k\leq 2^{r}\leq l$ by using
inequalities 4.29 and 4.32. This assumption means that the length of the
sequence in the binary expansion of $2^{r}+k$ and $2^{r}$ are equal.

With the same logic that one gets 4.29, one gets:

$\displaystyle f(l,l+k)\geq f(2^{r},2^{r}+k)\text{ when }2^{r}\leq l$ (4.33)

and then for $k\leq 2^{r}$ one can get:

$\displaystyle f(2^{r},2^{r}+k)=\displaystyle\sum_{2^{r}\leq i<2^{r}+k}h(i)$
(4.34)

$\sum_{2^{r}\leq i<2^{r}+k}h(i)$ is the sum over numbers with the same length
in their binary expansion’s sequence. When one removes the last digit in their
binary expansion, the remain is $f(0,k)$. Therefore, $\sum_{2^{r}\leq
i<2^{r}+k}h(i)$ is equal to $k$ $1$’s plus $f(0,k)$. Hence:

$\displaystyle f(2^{r},2^{r}+k)=k+f(0,k)\text{ when }k\leq 2^{r}\leq l$ (4.35)

and finally:

$\displaystyle f(l,l+k)\geq f(0,k)+k\text{ where }k\leq 2^{r}\leq l$ (4.36)

Now, one can prove lemma 1 by induction on $K$, without the assumption $k\leq
2^{r}\leq l$. We want to prove that for $1\leq K\leq l$, $f(l+K,l)\geq
K+f(0,K)$. Fix $k$ such that $1\leq k\leq l$ and $K<k$. For $K=1$ the
inequality in lemma 1 is trivial. Assume that the inequality is true for $K<k$
and $K>2$, which means:

$\displaystyle f(l,l+K)\geq K+f(0,K)\text{ when }1\leq k\leq l\text{ , and
}K<k$ (4.37)

Now, one should verify the inequality for $K=k$. Define $r\geq 1$ by
$2^{r-1}\leq k<2^{r}$. If $l\geq 2^{r}$, then $k\leq 2^{r}\leq l$ and the
lemma is implied by inequality 4.36. Hence, one may assume that
$2^{r-1}<l<2^{r}$. Now, one should apply inequality 4.32 and 4.37 in order to
get the final result:

$\displaystyle f(l+k)$ $\displaystyle=f(l,2^{r})+f(2^{r},l+k)\text{\emph{
(from definition of f and }}l\geq 2^{r})$ (4.38)
$\displaystyle=(2^{r}-l)r-f(0,2^{r}-l)+f(2^{r},l+k)\text{ \emph{ (from
\ref{1.5})}}$ (4.39)
$\displaystyle\geq(2^{r}-l)r-f(0,2^{r}-l)+f(0,l+k-2^{r})+l+k-2^{r}\text{\emph{
(from \ref{1.7})}}$ (4.40)
$\displaystyle\geq(2^{r}-l)r-f(2^{r}-k,2^{r}-k+2^{r}-l)+2^{r}-l+f(0,l+k-2^{r})+l+k-2^{r}\text{
\emph{(from \ref{1.7})}}$ (4.41)
$\displaystyle\geq(2^{r}-l)r-f(2^{r}-k,2^{r}-k+2^{r}-l)+f(0,l+k-2^{r})+k$
(4.42) $\displaystyle\geq f(l+k-2^{r},k)+f(0,l+k-2^{r})+k\text{ \emph{(from
\ref{1.5})}}$ (4.43) $\displaystyle\geq f(0,k)+k\text{ \emph{(from
characteristics of f)}}$ (4.44)

$\blacksquare$

######  Theorem 8.

For $2\leq m\leq 2^{n}$ we have $b_{Q^{n}}(m)=mn-2f(0,m)$. In other words,
$f(0,m)=e_{n}(m)\text{ where }e_{n}(m)=\max\\{e(H):H\text{ induced subgraph of
}Q^{n},|V(H)|=m\\}.$

Proof:
First, let us fix an $m$. As the first step one should prove that
$e_{n}(m)\geq f(0,m)$. Vertex $i$ is connected to $h(i)$ vertices $j$ with
$j<i$, since for each 1 in the binary expansion of $i$ there is exactly one j
$(j<i)$, which its binary expansion differs in the position of that $1$.
Therefore, one can conclude that $W=\\{0,1,2,...,m-1\\}$ contains $\sum_{0\leq
i<m}h(i)=f(0,m)$ edges. So, $e_{n}(m)\geq f(0,m)$.

As the second step, one should prove that $e_{n}(m)\leq f(0,m)$ by induction
on $n$. Fix $m$ and $n$ for $2\leq m\leq 2^{n}$. For $n=1$ the inequality is
trivially true. Assume that it is true for $N<n$, which means:

$\displaystyle e_{N}(m)\leq f(0,m),\text{ where }N<n\text{ and the fixed m is:
}2\leq m\leq 2^{n}$ (4.45)

Now, one should check the inequality 4.45 for $N=n$. This means that we should
find an $H$ induced subgraph of $Q^{n}$, $|V(H)|=m$, which maximize
$e_{n}(m)$. Let us split $Q^{n}$ into two (n-1)-dimensional cubes, the top
face with $2^{n-1}$ vertices and the bottom face with $2^{n-1}$ vertices. This
means, there are $(n-1)2^{n-2}$ edges in each face, and $2^{n-1}$ edges
between two faces. Now, one can construct $H$. Choose $m_{1}$ vertices for $H$
from the top face, and $m_{2}$ vertices from the bottom face, where
$m_{1}+m_{2}=m$ and $m_{1}\leq m_{2}$. In other words, $H$ is constructed from
two induced subgraphs, one from the top face, denoted by $H_{1}$, and the
other from the bottom face, denoted by $H_{2}$.

Each face is a (n-1)-dimensional cube, so inequality 4.45 holds for both
$H_{1}$ and $H_{2}$. Also, each vertex of the top face is connected to exactly
one vertex of the bottom face. Hence, the number of edges of $H$ is at most:

$\displaystyle e_{n}(m)\leq f(0,m_{1})+f(0,m_{2})+m_{1}\text{(from
\ref{1.21})}$ (4.46)

where $m_{1}$, in the right hand side of the inequality, is for the maximum
number of edges between $H_{1}$ and $H_{2}$, which one can choose here.
Finally, by applying lemma 1, one gets:

$\displaystyle e_{n}(m)$ $\displaystyle\leq f(0,m_{1})+f(0,m_{2})+m_{1}$
(4.47) $\displaystyle\leq f(m_{2},m_{2}+m_{1})+f(0,m_{2})\text{ (from lemma
\ref{1.1})}$ (4.48) $\displaystyle\leq f(0,m)\text{ (from definition of f)}$
(4.49)

$\blacksquare$
Theorem 8 shows that, if we want to choose an induced subgraph of $Q^{n}$,
with $m$ vertices, which has the smallest edge boundary, then we should choose
the induced subgraph of $Q^{n}$ with the set of vertices
$W=\\{0,1,2,...,m-1\\}$.

######  Corollary 1.

For all $k$ and $n$, $e_{n}(k)\leq\frac{k}{2}\lceil log_{2}k\rceil$, which is
equivalent to $b_{Q^{n}}(k)\geq k(n-\lceil log_{2}k\rceil)$.

Proof:
Let $r=\lceil log_{2}k\rceil$. Then

$\displaystyle 2f(0,k)$ $\displaystyle\leq f(0,k)+f(0,k)\leq
f(0,k)+f(2^{r}-k,2^{r})\text{ (from \ref{1.2}) }$ (4.50)
$\displaystyle=rk\text{ (from \ref{1.5})}$ (4.51)

Therefore:

$\displaystyle e_{n}(k)=f(0,k)\leq r\frac{k}{2}=\frac{k}{2}\lceil
log_{2}k\rceil$ (4.52)

$\blacksquare$

###  4.3 Isolated components of size larger than 2 and smaller than $2^{n}$

######  Definition 20.

$C_{s}$ is the family of s-subsets (subsets with size s) of $V=V(Q^{n})$ whose
induced graph is connected.

Remarks: $h(n):=o(g(n))$ means $\frac{h(n)}{g(n)}\rightarrow 0$ as
$n\rightarrow\infty$.
Remarks: The following inequality will be applied a lot in the rest of this
section:

$\displaystyle(\frac{n}{k})^{k}\leq\binom{n}{k}\leq\frac{n^{k}}{k!}\leq(\frac{ne}{k})^{k}$
(4.53)

######  Theorem 9.

If $p_{n}\geq 1-\frac{1}{2}(\log n)^{\frac{1}{n}}$, the probability that for
some $S\in C_{s}$, $2\leq s\leq 2^{n-1}$, no edges of $Q_{p_{n}}^{n}$ join $S$
to $V(Q^{n})\setminus S$, as $n\rightarrow\infty$, tends to 0.

Note: For $2^{n-1}<s<2^{n}$, if there exist a component of size smaller than
$2^{n}$ then there is at least one component of size smaller than $2^{n-1}$
which contradicts with the theorem.

Proof:
Consider $S\subset V=V(Q^{n})$ and set $b(S)=b_{Q^{n}}(H)$ for which $H$ is
the induced subgraph of $Q^{n}$ with the set of vertices S. One can observe
that:

$\displaystyle\textbf{P}(\text{No edges of }Q_{p_{n}}^{n}\text{ join S to
}V\setminus S)=(1-p_{n})^{b(S)}$ (4.54)

In order to prove the theorem, it is sufficient to show that:

$\displaystyle\sum_{s=2}^{2^{n-1}}\sum_{S\in C_{s}}(1-p_{n})^{b(S)}=o(1)$
(4.55)

From corollary 1, one knows that for $|S|=s$:

$\displaystyle b(S)\geq b(s)\geq s(n-\lceil\log_{2}s\rceil)$ (4.56)

and therefore:

$\displaystyle\sum_{S\in C_{s}}(1-p_{n})^{b(S)}\leq|C_{s}|(1-p_{n})^{b(s)}$
(4.57)

Now, one should partition s, $2\leq s\leq 2^{n-1}$, to different intervals in
order to find a bound for $|C_{s}|$ and $(1-p_{n})^{b(s)}$ for each interval.

First interval $2\leq s\leq
s_{1},s_{1}=\lfloor\frac{2^{\frac{n}{2}}}{n^{2}}\rfloor$:

First, one should find a bound for $|C_{s}|$. One has maximum $2^{n}$ choices
to choose the first element for $C_{s}$. The selected element is connected to
maximum $n$ vertices, therefore there are $n$ choices to choose the second
element. With the same logic there are at most $(s-1)n$ choices to choose the
last element for $C_{s}$. Therefore, one can show:

$\displaystyle|C_{s}|\leq 2^{n}(n)(2n)...((s-1)n))\leq(s-1)!(n)^{s-1}2^{n}$
(4.58)

Hence:

$\displaystyle|C_{s}|(1-p_{n})^{b(s)}\leq(s-1)!(n)^{s-1}2^{n}(1-p_{n})^{s(n-\lceil\log_{2}s\rceil)}$
(4.59)

Since $p_{n}=1-\frac{1}{2}(\log n)^{\frac{1}{n}}$, so for large enough $n$:

$\displaystyle(1-p_{n})^{s(n-\lceil log_{2}s\rceil)}$
$\displaystyle\leq(2)^{-ns}(\log
n)^{s}(1-p_{n})^{-s(\log_{2}s)}\text{(neglecting some small terms)}$ (4.60)
$\displaystyle=(2)^{-ns}(\log n)^{s}2^{s\log_{2}s}(\log
n)^{\frac{-s\log_{2}s}{n}}$ (4.61) $\displaystyle(\text{ since for large
enough n: }(\log n)^{\frac{-s\log_{2}s}{n}}\leq 1)$ (4.62)
$\displaystyle\leq(2)^{-ns}(\log n)^{s}s^{s}$ (4.63)

From equations 4.59 and 4.63, one can show that:

$\displaystyle|C_{s}|(1-p_{n})^{b(s)}\leq(s-1)!(n)^{s-1}2^{n}(2)^{-ns}(\log
n)^{s}s^{s}$ (4.64)

Assume that the right hand side of inequality 4.64 is equal to A. After
multiplying both sides of inequality 4.64 with $\frac{ns^{s+1}}{s!}$ and then
taking $\log_{2}$ from both sides, one gets:

$\displaystyle\log_{2}(|C_{s}|(1-p_{n})^{b(s)}\frac{ns^{s+1}}{s!})\leq\log_{2}(A\frac{ns^{s+1}}{s!})$
(4.65)

If $\log_{2}(A\frac{ns^{s+1}}{s!})\rightarrow-\infty$ as $n\rightarrow\infty$
then $A\frac{ns^{s+1}}{s!}$ should tend to 0. This means that
$|C_{s}|(1-p_{n})^{b(s)}\frac{ns^{s+1}}{s!}$ tends to 0, as
$n\rightarrow\infty$. Therefore:

$\displaystyle|C_{s}|(1-p_{n})^{b(s)}\leq\frac{s!}{ns^{s+1}}\text{ for large
enough n}$ (4.66)

which shows that:

$\displaystyle\sum_{s=2}^{s_{1}}\sum_{S\in C_{s}}(1-p_{n})^{b(S)}=o(1)$ (4.67)

Finally, it remains to prove
$\log_{2}(A\frac{ns^{s+1}}{s!})\rightarrow-\infty$ as $n\rightarrow\infty$.
One can verify this for $s\leq n$ and $s>n$.

Second interval $s_{1}+1\leq s\leq 2^{n-1}$ and $S\in
C_{s}^{-},s_{1}=\lfloor\frac{2^{\frac{n}{2}}}{n^{2}}\rfloor$:
Let us define $C_{s}^{-}$ and $C_{s}^{+}$ as follows:

######  Definition 21.

$\displaystyle C_{s}^{-}:=\\{S\in C_{s}|b(s)\geq
s(n-\log_{2}s+\log_{2}n)\\}\text{, and }C_{s}^{+}:=C_{s}\backslash C_{s}^{-}$
(4.68)

One can bound $|C_{s}^{-}|$ for $s_{1}+1\leq s\leq 2^{n-1}$ as follows:

$\displaystyle|C_{s}^{-}|\leq|C_{s}|\leq\binom{2^{n}}{s}\leq\frac{2^{ns}}{s!}\leq(\frac{e2^{n}}{s})^{s}$
(4.69)

Hence:

$\displaystyle\displaystyle\sum_{s=s_{1}+1}^{2^{n-1}}\sum_{S\in
C_{s}^{-}}(1-p_{n})^{b(S)}$
$\displaystyle\leq\sum_{s=s_{1}+1}^{2^{n-1}}(\frac{e2^{n}}{s})^{s}(\frac{1}{2}(\log
n)^{\frac{1}{n}})^{s(n-\log_{2}s+\log_{2}n)}$ (4.70)
$\displaystyle\leq\sum_{s=s_{1}+1}^{2^{n-1}}(\frac{e2^{n}2^{-(n-\log_{2}s+\log_{2}n)}(\log
n)^{\frac{(n-\log_{2}s+\log_{2}n)}{n}}}{s})^{s}$ (4.71)
$\displaystyle\leq\sum_{s=s_{1}+1}^{2^{n-1}}(\frac{e2^{n}2^{-n}2^{\log_{2}s}2^{-\log_{2}n}\log
n}{s})^{s}(\log n)^{\frac{n(-\log_{2}s+\log_{2}n)}{s}}$ (4.72)
$\displaystyle(\text{ since for large enough n: }(\log
n)^{\frac{n(-\log_{2}s+\log_{2}n)}{s}}\leq 1)$ (4.73)
$\displaystyle\leq\sum_{s=s_{1}+1}^{2^{n-1}}(\frac{e\log n}{n})^{s}=o(1)$
(4.74)

$\blacksquare$

Third interval $s_{1}\leq s\leq s_{2}$,
$s_{1}=\lfloor\frac{2^{\frac{n}{2}}}{n^{2}}\rfloor,s_{2}=\lfloor\frac{2^{n}}{(\log
n)^{4}}\rfloor$ and $S\in C_{s}^{+}$:
For the 3rd and the 4th intervals one needs to know how to find a bound for
$|C_{s}^{+}|$. The following lemma, presented by B.Bollobas [1], helps us in
this matter:

######  Lemma 2.

Let G be a graph of order $v$ and suppose that $\Delta(G)\leq\Delta$,
$2e(G)=vd$ and $\Delta+1\leq u\leq v-\Delta-1$. Then, there is a u-set of U of
vertices with:

$\displaystyle|N(U)|=|U\cup\Gamma(U)|\geq
v\frac{d}{\Delta}\\{1-exp(\frac{-u(\Delta+1)}{v})\\}$ (4.75)

where, $\Delta(G):=$ Maximum degree in G, $d:=$ average degree in G and
$\Gamma(U)=\\{x\in V(G):xy\in E(G)\text{ for some y}\in U\\}$

Let $H=Q_{n}[S]$ (the induced subgraph of $Q_{n}$ with the set of vertices
$S$). From the definition of $C_{s}^{+}$ one knows that the average degree in
$H$ is at least:

$\displaystyle\log_{2}s-\log_{2}n$ (4.76)

The goal is to find $U\subset S$, where $|U|:=u:=\lfloor\frac{2s}{n}\rfloor$,
$\Delta=n$, $v=s$, $d\geq\log_{2}s-\log_{2}n$ and then use lemma 2 to
calculate $|N(U)|$. First, one should check the condition $\Delta+1\leq u\leq
v-\Delta-1$ for defined variables in order to use lemma 2. First, check if
$n+1\leq\lfloor\frac{2s}{n}\rfloor$, as $n\rightarrow\infty$:

$\displaystyle\frac{2s}{n}=\frac{2^{\frac{n}{2}+1}}{n^{3}}\text{for minimum s,
and trivially }n+1\leq\frac{2^{\frac{n}{2}+1}}{n^{3}}\text{ for large enough
n}$ (4.77)

and then check if $\lfloor\frac{2s}{n}\rfloor\leq s-(n+1)$. One should check
if $ns-n(n+1)\geq 2s$, which means one should check that whether:

$\displaystyle\frac{2^{\frac{n}{2}}(n-2)}{n^{3}(n+1)}\geq 1$ (4.79)

which is clearly true for large enough $n$. Now, one can apply lemma 2 on the
graphs generated by $S$ and get :

$\displaystyle\exists U\subset S:|N(U)|\geq
s\frac{\log_{2}s-\log_{2}n}{n}\\{1-exp(-\frac{u(n+1)}{s})\\}$ (4.80)

where:

$\displaystyle\frac{\log_{2}s-\log_{2}n}{n}\geq\frac{(\log_{2}(\frac{2^{\frac{n}{2}}}{n^{2}})-\log_{2}n)}{n}=\frac{n-6\log_{2}n}{2n}$
(4.81) $\displaystyle\text{and
}\lim_{n\rightarrow\infty}\frac{n-6\log_{2}n}{2n}=\frac{1}{2}$ (4.82)

on the other hand:

$\displaystyle\lim_{n\rightarrow\infty}(1-exp(-\frac{n+1}{s}(\frac{2s}{n}+1)))=1-e^{-2}$
(4.83)

Therefore, from 4.82 and 4.83 one gets:

$\displaystyle|N(U)|\geq\frac{1}{2}(1-e^{-2})s\geq\frac{s}{3}\text{ as
}n\rightarrow\infty$ (4.84)

Now that we have $|N(U)|$, we can estimate a bound for $|C_{s}^{+}|$ here. We
know from 4.84 that for each $S\in C_{s}^{+}$ there exist a $U\subseteq S$,
$|U|:=u:=\lfloor\frac{2s}{n}\rfloor$, such that $|N(U)|\geq s/3$. Therefore,
one can choose $S\in C_{s}^{+}$ as follows:
1\. Select $u$ vertices of $Q^{n}$; there are $\binom{2^{n}}{u}$ choices for
this $u$.
2\. Select $\lfloor\frac{s}{3}\rfloor-u$ neighbors of the selected vertices in
part $1$; there are maximum $(2^{n})^{u}$ choices, since there are at most
$\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+...\binom{n}{n}=2^{n}$ ways to find
neighbors of a vertex in $U$.
3\. Select $\lfloor\frac{2s}{3}\rfloor$ other vertices; there are at most
$\binom{2^{n}}{\lfloor\frac{2s}{3}\rfloor}$ choices.
Hence:

$\displaystyle|C_{s}^{+}|\leq\binom{2^{n}}{u}(2^{n})^{u}\binom{2^{n}}{\lfloor\frac{2s}{3}\rfloor}$
(4.85)

and:

$\displaystyle\sum_{S\in
C_{s}^{+}}(1-p_{n})^{b(S)}\leq\binom{2^{n}}{u}(2^{n})^{u}\binom{2^{n}}{\lfloor\frac{2s}{3}\rfloor}(1-p_{n})^{b(s)}$
(4.86)

where:

$\displaystyle(1-p_{n})^{b(s)}\leq 2^{-sn}s^{s}(\log n)^{s}$ (4.87)

consequently from 4.86, 4.87 and 4.53:

$\displaystyle\sum_{S\in
C_{s}^{+}}(1-p_{n})^{b(S)}\leq(\frac{e2^{n}}{u})^{u}2^{un}(\frac{e2^{n}}{\lfloor\frac{2s}{3}\rfloor})^{\lfloor\frac{2s}{3}\rfloor}2^{-sn}s^{s}(\log
n)^{s}$ (4.88)

Write $s=2^{\beta n}$, ($\beta=\frac{log_{2}s}{n}$), so that:

$\displaystyle 2^{\beta n}\leq\frac{2^{n}}{(\log n)^{4}}\Rightarrow\beta\leq
1-\frac{4\log_{2}\log n}{n}$ (4.89)

Now, find a bound for the inequality 4.88. First calculate the first part of
the inequality:

$\displaystyle(\frac{e2^{n}}{u})^{u}2^{un}(\frac{e2^{n}}{\lfloor\frac{2s}{3}\rfloor})^{\lfloor\frac{2s}{3}\rfloor}$
$\displaystyle\leq(\frac{e2^{n}}{\frac{2s}{n}})^{\frac{2s}{n}}2^{2s}(\frac{e2^{n}}{\frac{2s}{3}})^{\frac{2s}{3}}=(2^{2}2^{2}(\frac{3}{2}e)^{\frac{2}{3}})^{s}\frac{2^{\frac{2s}{3n}}}{s^{\frac{2s}{3}}}(\frac{2^{n}}{s})^{\frac{2s}{3}}$
(4.90) $\displaystyle(\text{ since for large enough n and $s_{1}\leq s\leq
s_{2}$: }(\frac{e2^{n}}{\frac{2s}{3}})^{\frac{2s}{3}}\leq 1)$ (4.91)
$\displaystyle=(2^{2}2^{2}(\frac{3}{2}e)^{\frac{2}{3}})^{s}\frac{2^{\frac{2s}{3n}}}{s^{\frac{2s}{3}}}=c^{s}2^{\frac{2}{3}sn(1-\frac{\log_{2}s}{n})}=c^{s}2^{\frac{2}{3}sn(1-\beta)}$
(4.92)

where c is a positive constant. Now, by substituting 4.92 in 4.88 one gets:

$\displaystyle\sum_{S\in C_{s}^{+}}(1-p_{n})^{b(S)}$ $\displaystyle\leq
2^{-sn}s^{s}(\log n)^{s}c^{s}2^{\frac{2}{3}sn(1-\beta)}$ (4.93)
$\displaystyle=c^{s}(\log n)^{s}2^{-\frac{sn(1-\beta)}{3}}$ (4.94)
$\displaystyle\leq c^{s}(\log n)^{s}2^{-\frac{4s\log_{2}\log n}{3n}}\text{ ,
(from \ref{1.13})}$ (4.95) $\displaystyle=c^{s}(\log n)^{s}2^{\log_{2}(\log
n)^{\frac{-4s}{3}}}$ (4.96) $\displaystyle\leq c^{s}(\log n)^{s}(\log
n)^{\frac{-4s}{3}}$ (4.97) $\displaystyle=c^{s}(\log n)^{\frac{-s}{3}}$ (4.98)

and finally from 4.98:

$\displaystyle\sum_{s=s_{1}}^{s_{2}}\sum_{S\in
C_{s}^{+}}(1-p_{n})^{b(S)}\leq\sum_{s=s_{1}}^{s_{2}}c^{s}(\log
n)^{\frac{-s}{3}}=o(1)$ (4.99)

$\blacksquare$

Fourth interval $s_{2}+1\leq s\leq 2^{n-1}$ and
$,s_{2}=\lfloor\frac{2^{n}}{(\log n)^{4}}\rfloor,S\in C_{s}^{+}$:

In $H=Q^{n}[S]$ (the induced subgraph of $Q^{n}$ with the set of vertices S),
the average degree is at least:

$\displaystyle\log_{2}s-\log_{2}n>n-2\log_{2}n$ (4.100)

since:

$\displaystyle s\geq\lceil\frac{2^{n}}{(\log
n)^{4}}\rceil\Rightarrow\log_{2}(\frac{2^{n}}{(\log n)^{4}})<\log_{2}s$
(4.101)
$\displaystyle\Rightarrow\log_{2}s-\log_{2}n\geq\log_{2}(\frac{2^{n}}{(\log
n)^{4}})-\log_{2}n\geq n-\log_{2}(\log n)^{4}-\log_{2}n$ (4.102)
$\displaystyle(\text{for large enough n one can get, }n>(\log n)^{4})$ (4.103)
$\displaystyle\geq n-2\log_{2}n$ (4.104)

First, look for a subgraph of H with large average degree. Let T be the set of
vertices of H with degree at least $n-(\log_{2}n)^{2}$, and set $t=|T|$. From
4.100 one can conclude that the sum of degrees in $H$ is at least
$s(n-2\log_{2}n)$.We also know that:

$\displaystyle\text{Sum of degrees in }S$ $\displaystyle\leq s(n-2\log_{2}n)$
(4.105) $\displaystyle\leq t\times(\text{Maximum degree of vertices in set $T$
of graph $H$ })$ (4.106) $\displaystyle+(s-t)\times(\text{Maximum degree of
vertices in set $S\setminus T$ of graph $H$ })$ (4.107) $\displaystyle\leq
tn+(s-t)(n-(\log_{2}n)^{2})$ (4.108) $\displaystyle\Rightarrow t\geq
s(1-\frac{2}{\log_{2}n})$ (4.109)

Define $H_{1}=Q^{n}[T]=H[T]$ as the induced subgraph spanned by $T$. We want
to calculate $|N_{H_{1}}(U)|$ for some $U$ in $H_{1}$, hence we should
estimate the size of $H_{1}$ and after that calculate the average degree in T.
Let us first calculate $e(H_{1})$, the total number of edges in $H_{1}$.

$\displaystyle e(H_{1})\geq
e(H)-(s-t)n\geq\frac{s}{2}(n-2\log_{2}n)-\frac{2s}{\log_{2}n}n\text{ (from
\ref{1.33} and \ref{1.34})}$ (4.110)

One knows that the average degree in $H_{1}$ is at least
$\frac{2e(H_{1})}{s}$, and:

$\displaystyle\frac{2e(H_{1})}{s}\geq n-2\log_{2}n-\frac{4n}{\log_{2}n}\geq
n-\frac{5}{log_{2}n}$ (4.111) $\displaystyle(\text{since:
}\log_{2}n^{2}<\frac{n}{\log_{2}n}\text{ for large enough n})$ (4.112)

Set $u=\lfloor\frac{2^{n}}{n^{\frac{1}{2}}}\rfloor$. One should check the
conditions of lemma 1 here. Let $v=t,\Delta=n,d\geq n-\frac{5}{\log_{2}n}$.
So, one should check if $n+1\leq\frac{2^{n}}{n^{\frac{1}{2}}}\leq t-(n+1)$ for
large enough $n$. Clearly, $n+1\leq\frac{2^{n}}{n^{\frac{1}{2}}}$, as
$n\rightarrow\infty$. It remains to prove $\frac{2^{n}}{n^{\frac{1}{2}}}\leq
t-(n+1)$, for large enough $n$. For minimum $s$ from 4.109 we can get:

$\displaystyle t\geq$ $\displaystyle\frac{2^{n}}{(\log
n)^{4}}(1-\frac{2}{\log_{2}n})\text{ (from \ref{1.34})}$ (4.113)
$\displaystyle\geq\frac{2^{n}}{n^{\frac{1}{2}}}+n+1\text{ (for large enough n)
}$ (4.114)

Now, one can use lemma 1 and estimate $|N_{H_{1}}(U)|$.

$\displaystyle|N_{H_{1}}(U)|$
$\displaystyle\geq\frac{t}{n}(n-\frac{5n}{\log_{2}n})\\{1-\exp(-\frac{n+1}{t}\frac{2^{n}}{n^{\frac{1}{2}}})\\}$
(4.115)
$\displaystyle\geq\frac{t}{2}(1-\frac{5}{\log_{2}n})\\{1-\exp(-\frac{n+1}{t}\frac{2^{n}}{n^{\frac{1}{2}}})\\}$
(4.116)

After that, let us estimate a bound for
$\exp(-\frac{n+1}{t}\frac{2^{n}}{n^{\frac{1}{2}}})$. One knows that $t\geq
s(1-\frac{2}{\log_{2}n})$. Since $\max(t)=s$ and $\max(s)=2^{n-1}$, then:

$\displaystyle\frac{2^{n}(n+1)}{n^{\frac{1}{2}}t}\geq\frac{2^{n}(n+1)}{n^{\frac{1}{2}}2^{n-1}}=\frac{2(n+1)}{n^{\frac{1}{2}}}\geq
n^{\frac{1}{4}}\text{( for large enough n)}$ (4.117)
$\displaystyle\Rightarrow\\{1-\exp(-\frac{n+1}{t}\frac{2^{n}}{n^{\frac{1}{2}}})\\}\geq\exp(-n^{\frac{1}{4}})\text{(
for large enough n)}$ (4.118)

By using the bound from 4.118 in 4.116, one gets:

$\displaystyle|N_{H}(U)|\geq|N_{H_{1}}(U)|$ $\displaystyle\geq
t(1-\frac{5}{\log_{2}n})\\{1-\exp(-n^{\frac{1}{4}})\\}$ (4.119)
$\displaystyle=t\\{1+\exp(-n^{\frac{1}{4}})\frac{5}{\log_{2}n}-\exp(-n^{\frac{1}{4}})-\frac{5}{\log_{2}n}\\}$
(4.120)
$\displaystyle(\lim_{n\rightarrow\infty}\exp(-n^{\frac{1}{4}})\frac{5}{\log_{2}n}=0\text{
and }\exp(-n^{\frac{1}{4}})<\frac{1}{\log_{2}n}\text{( for large enough n)})$
(4.121) $\displaystyle\geq
t\\{1-\frac{1}{\log_{2}n}-\frac{6}{\log_{2}n}\\}=t(1-\frac{6}{\log_{2}n})$
(4.122) $\displaystyle\geq
s(1-\frac{2}{\log_{2}n})(1-\frac{5}{\log_{2}n})=s(1+\frac{2}{\log_{2}n}\frac{6}{\log_{2}n}-\frac{8}{\log_{2}n})\text{(from
\ref{1.34})}$ (4.123) $\displaystyle\geq s(1-\frac{8}{\log_{2}n})$ (4.124)

Now that we have $|N_{H}(U)|$, we can estimate a bound for $|C_{s}^{+}|$ here.
We know from 4.124 that for each $S\in C_{s}^{+}$ there exist a $U\subseteq
S$, $|U|:=u:=\lfloor\frac{2^{n}}{n^{\frac{1}{2}}}\rfloor$, such that
$|N_{H}(U)|\geq s(1-\frac{8}{\log_{2}n})$. Therefore, one can choose $S\in
C_{s}^{+}$ as follows:
1\. Select $u$ vertices of $Q^{n}$; there are $\binom{2^{n}}{u}$ choices for
this $u$.
2\. Select $\lfloor s(1-\frac{8}{\log_{2}n})\rfloor-u$ neighbors of the
selected vertices in part 1. At most $(\log_{2}n)^{2}$ of the $n$ neighbors of
a vertex in $U$ do not belong to $N_{H}(U)$. Hence there are at most
$\sum_{(k_{j})}(\prod_{i=1}^{u}\binom{n}{j})$ ways to find neighbors of $u$
vertices in $U$, where the sum is over all
$(k_{1},k_{2},...,k_{u}),k_{i}\leq(\log_{2}n)^{2}$. We know that:

$\displaystyle\sum_{(k_{i})}\prod_{i=1}^{u}\binom{n}{k_{i}}$
$\displaystyle\leq\sum_{(k_{i})}\prod_{i=1}^{u}(\frac{n^{i}}{i!})$ (4.125)
$\displaystyle\leq\sum_{(k_{i})}\prod_{i=1}^{u}(\frac{n^{(\log_{2}n)^{2}}}{(\log_{2}n)^{2}!})$
(4.126)
$\displaystyle=\sum_{(k_{i})}\frac{n^{u(\log_{2}n)^{2}}}{((\log_{2}n)^{2}!)^{u}}$
(4.127)
$\displaystyle={((\log_{2}n)^{2})}^{u}\frac{n^{u(\log_{2}n)^{2}}}{((\log_{2}n)^{2}!)^{u}}$
(4.128) $\displaystyle\leq n^{u(\log_{2}n)^{2}}$ (4.129)

3\. Select $\lfloor\frac{8s}{\log_{2}n}\rfloor$ other vertices; there are at
most $\binom{2^{n}}{\lfloor\frac{8s}{\log_{2}n}\rfloor}$ choices.
Hence:

$\displaystyle\sum_{S\in
C_{s}^{+}}(1-p_{n})^{b(S)}\leq\binom{2^{n}}{u}n^{u(\log_{2}n)^{2}}\binom{2^{n}}{\lfloor\frac{8s}{\log_{2}n}\rfloor}2^{-s(n-\log_{2}s)}(\log
n)^{s(1-\frac{\log_{2}s}{n})}$ (4.131)

where:

$\displaystyle\binom{2^{n}}{u}n^{u(\log_{2}n)^{2}}\binom{2^{n}}{\lfloor\frac{8s}{\log_{2}n}\rfloor}\leq
2^{o(s)}$ (4.133)

Therefore:

$\displaystyle\sum_{S\in C_{s}^{+}}(1-p_{n})^{b(S)}\leq 2^{\varepsilon(s)}$
(4.134)

where:

$\displaystyle\varepsilon(s)=o(s)-s\\{n-\log_{2}s-\log_{2}\log
n+\frac{\log_{2}s}{n}\log_{2}\log n\\}$ (4.135)

Since $s\leq 2^{n-1}$, hence one can get:

$\displaystyle\varepsilon(s)$ $\displaystyle\leq o(s)-s\\{n-(n-1)-\log_{2}\log
n+\frac{n-1}{n}\log_{2}\log n\\}$ (4.136)
$\displaystyle=o(s)-s\\{1-\frac{1}{n}\log_{2}\log n\\}\leq\frac{-s}{2}$
(4.137)

Therefore, for large enough n, one can get:

$\displaystyle\sum_{s=s_{2}+1}^{2^{n-1}}\sum_{S\in
C_{s}^{+}}(1-p_{n})^{b(S)}\leq\sum_{s=s_{2}+1}^{2^{n-1}}2^{-\frac{s}{2}}=o(1)$
(4.138)

$\blacksquare$

###  4.4 Comparison between a typical random graph and $Q^{n}$

Consider $Per(G(V,E),p_{n})$ as the subgraph of $G(V,E)$ after percolation
with the parameter $p_{n}$. The goal in this section is to compare
$\textbf{P}(Q^{n}_{p_{n}}\text{ is connected})$ with P($Per(G\in
G(N=2^{n},M=n2^{n-1}),p_{n}$) is connected) as $n\rightarrow\infty$.

One knows, the probability that $G_{p}\in G(n,p)$ is connected, for $p=c\log
n/n$ as $n\rightarrow\infty$, tends to [1] :

$\displaystyle\lim_{n\rightarrow\infty}\textbf{P}(G_{p}\in G(n,p)\text{ is
connected})=\left\\{\begin{array}[]{ll}1&\mbox{if $c>1$};\\\ 1-e^{-1}&\mbox{if
$c=1$};\\\ 0&\mbox{if $c<1$}.\end{array}\right.$ (4.142)

######  Theorem 10.

If $Q$ is a convex property and $pq\binom{n}{2}\rightarrow\infty$, then almost
every graph in $G(n,p)$ has $Q$ iff for every fixed $x$ a.e. graph in $G(n,M)$
has $Q$, when $M=\lfloor p\binom{n}{2}+x(pq\binom{n}{2}^{0.5})\rfloor$ [1].

######  Definition 22.

$Q$ is a convex property if $F\subset G\subset H$ and $F\in Q$ and $H\in Q$
then $G\in Q$.

We want to calculate $\textbf{P}(Per(G_{m}\in G(n,M=m),p_{n})\text{ is
connected})$ as $n\rightarrow\infty$. From theorem 10, one can conclude that
$G(n,p)$ and $G(n,M=p\binom{n}{2})$ have almost the same behavior for
connectivity, as $n\rightarrow\infty$. Hence:

$\displaystyle\textbf{P}(Per(G_{M}\in G(n,M=p\binom{n}{2}),p_{n})\text{ is
connected})$ (4.143) $\displaystyle\approx\textbf{P}(G_{p}\in
G(n,pp_{n}))\text{ is connected}),\text{ as }n\rightarrow\infty$ (4.144)

We can calculate $\textbf{P}(G_{p}\in G(n,pp_{n}))\text{ is connected})$ from
theorem 10 for $pp_{n}=c\log n/n$, as $n\rightarrow\infty$. Therefore, we
should consider $p_{n}=c(n-1)\log n/(2m)$. Finally, one can calculate the
probability that $G_{M}\in G(n,M=m)$ is connected after percolation with the
parameter $p_{n}=c(n-1)\log n/(2m)$ as:

$\displaystyle\lim_{n\rightarrow\infty}\textbf{P}(Per(G_{M}\in
G(n,M),p_{n})\text{ is connected})=\left\\{\begin{array}[]{ll}1&\mbox{for
$p_{n}$'s such that $c>1$};\\\ 1-e^{-1}&\mbox{for $p_{n}$'s such that
$c=1$};\\\ 0&\mbox{for $p_{n}$'s such that $c<1$}.\end{array}\right.$ (4.148)

Now, let us calculate $\textbf{P}(Per(G_{M}\in G(2^{n},n2^{n-1}),p_{n})\text{
is connected)}$. From (4.148), for $p_{n}=c(1-\frac{1}{2^{n}})$, one gets:

$\displaystyle\lim_{n\rightarrow\infty}\textbf{P}(Per(G_{M}\in
G(2^{n},n2^{n-1}),p_{n})\text{ is
connected})=\left\\{\begin{array}[]{ll}1&\mbox{for $p_{n}$'s such that $c>\log
2$};\\\ 1-e^{-1}&\mbox{for $p_{n}$'s such that $c=\log 2$};\\\ 0&\mbox{for
$p_{n}$'s such that $c<\log 2$}.\end{array}\right.$ (4.152)

Finally, it can be concluded that,
$\lim_{n\rightarrow\infty}\textbf{P}(Per(G_{M}\in
G(2^{n},n2^{n-1}),p^{\prime})\text{ is connected})=1$ for $0.3\approx\log
2<p^{\prime}<0.5$, while
$\lim_{n\rightarrow\infty}\textbf{P}(Q^{n}_{p^{\prime}}\text{ is
connected})=0$ for $\log 2<p^{\prime}<0.5$. Hence, a typical graph with
$2^{n}$ vertices and $n2^{n-1}$ edges is ”more connected” than $Q^{n}$.

##  Chapter 5 Connected random subgraphs of the 3-cube

111The proof presented for the 3-cube, in this chapter, is independent of the
proof presented in the previous chapter; therefore, some parts of the proofs
overlap each other.

The 3-cube graph, ${}^{3}Q^{n}$, is a simple graph with $3^{n}$ vertices. If
one labels each vertex of ${}^{3}Q^{n}$ from $0$ to $3^{n}-1$, then two
vertices are adjacent if their ternary representation differs only in one
digit. The number of edges in ${}^{3}Q_{n}$ is $n3^{n}$, since each vertex is
connected to $2n$ vertices. A random subgraph of ${}^{3}Q^{n}$ contains all
vertices of ${}^{3}Q^{n}$, and each edge independently with probability
$p_{n}$. ${}^{3}Q_{p_{n}}^{n}$ stands for a random subgraph of ${}^{3}Q^{n}$.

The main goal in this chapter is to explore a critical value $p_{c}$, which
for fixed values of $p$ if $p<p_{c}$ then the probability that
${}^{3}Q_{p_{n}}^{n}$ is connected, as $n\rightarrow\infty$, tends to $0$; but
if $p>p_{c}$ then the probability that ${}^{3}Q_{p_{n}}^{n}$ is connected, as
$n\rightarrow\infty$, tends to $1$. We prove that this critical value is
$(\sqrt{3}-1)/(\sqrt{3})$.

In the first section of this chapter, first the probability that
${}^{3}Q_{p_{n}}^{n}$ has no isolated point as $n\rightarrow\infty$, for fixed
$p$, is investigated. It is proved that for $p<(\sqrt{3}-1)/(\sqrt{3})$ the
probability that ${}^{3}Q_{p_{n}}^{n}$ has no isolated point, as
$n\rightarrow\infty$, tends to $0$. Therefore, for $p<(\sqrt{3}-1)/(\sqrt{3})$
the probability that ${}^{3}Q_{p_{n}}^{n}$ is connected, as
$n\rightarrow\infty$, tends to $0$. Then it is proved that, for
$p>(\sqrt{3}-1)/(\sqrt{3})$ the probability that ${}^{3}Q_{p_{n}}^{n}$ has no
isolated point, as $n\rightarrow\infty$, tends to $1$. In the next step, the
probability that ${}^{3}Q_{p_{n}}^{n}$ has no isolated point, as
$n\rightarrow\infty$, when $p$ depends on $n$ and it is close
$(\sqrt{3}-1)/(\sqrt{3})$, is explored. It is proved that for
$\lambda(n)=\lambda>0$ and $p_{n}=1-(1/\sqrt{3})\lambda^{1/2n}(1+o(1/n)$, the
probability that ${}^{3}Q_{p_{n}}^{n}$ has no isolated point, as
$n\rightarrow\infty$, tends to $e^{-\lambda}$. Finally, it is proved that, for
fixed $p=(\sqrt{3}-1)/(\sqrt{3})$ the probability that ${}^{3}Q_{p_{n}}^{n}$
has no isolated point, as $n\rightarrow\infty$, tends to $e^{-1}$.

In the second section, one sheds light on the Isoperimetric problem, which is
the problem of finding an inequality which relates the size of a subgraph to
the size of its boundary. One needs such an inequality to explore the
probability that ${}^{3}Q_{p_{n}}^{n}$ has a component which is not the whole
graph.

In the last section, the Isoperimetric inequality is applied to prove that
when $p$ depends on $n$ and $p_{n}\geq 1-(1/\sqrt{3})(\log n)^{1/n}$, then the
probability that there are no components with size larger than $1$ and smaller
than $3^{n}$ in ${}^{3}Q_{p_{n}}^{n}$ , as $n\rightarrow\infty$, tends to $1$.
Therefore, for $p_{n}=1-(1/\sqrt{3})\lambda^{1/2n}(1+o(1/n))$, the probability
that ${}^{3}Q_{p_{n}}^{n}$ is connected, as $n\rightarrow\infty$, tends to
$e^{-\lambda}$. Finally, as a special case, it is shown that, for fixed $p$ if
$p=(\sqrt{3}-1)/(\sqrt{3})$, the probability that ${}^{3}Q_{p_{n}}^{n}$ is
connected , as $n\rightarrow\infty$, tend to $e^{-1}$; and if
$p>(\sqrt{3}-1)/(\sqrt{3})$, the probability that ${}^{3}Q_{p_{n}}^{n}$ is
connected, as $n\rightarrow\infty$, tends to $1$.

###  5.1 Isolated vertices

For $p_{n}<\frac{\sqrt{3}-1}{\sqrt{3}}$:

First, one should consider the following definitions:

######  Definition 23.

$f_{n}(p_{n})$:=P(${}^{3}Q_{p_{n}}^{n}$ is connected)

######  Definition 24.

$g_{n}(p_{n}):=\textbf{P}(^{3}Q_{p_{n}}^{n}\text{contains an isolated point})$

######  Definition 25.

$X_{i}(n):=\left\\{\begin{array}[]{ll}1&\mbox{Vertex $i$ is isolated, $i\in
V(^{3}Q_{p_{n}}^{n}$)};\\\ 0&\mbox{Vertex $i$ is NOT isolated, $i\in
V(^{3}Q_{p_{n}}^{n}$)}.\end{array}\right.$ , and
$X(n):=\displaystyle\sum_{i\in V(^{3}Q_{p_{n}}^{n})}X_{i}(n)$.

Now, calculate $E[X(n)]$ and $Var[X(n)]$ as follows:

$\displaystyle\mu:=E[X(n)]=\sum_{i\in
V(^{3}Q_{p_{n}}^{n})}E[X_{i}(n)]=\sum_{i\in
V(^{3}Q_{p_{n}}^{n})}(1-p)^{2n}=3^{n}(1-p)^{2n}$ (5.1) $\displaystyle
Var[X(n)]=\displaystyle\sum_{i\in
V(^{3}Q_{p_{n}}^{n})}Var[X_{i}(n)]+\displaystyle\sum_{i\neq j;i,j\in
V(^{3}Q_{p_{n}}^{n})}Cov[X_{i}(n),X_{j}(n)]$ (5.2)

where, $Var[X_{i}(n)]$ and $Cov[X_{i}(n),X_{j}(n)]$ are equal to:

$\displaystyle\displaystyle\sum_{i\in V(^{3}Q_{p_{n}}^{n})}Var[X_{i}(n)]$
$\displaystyle=3^{n}(1-p)^{2n}-3^{n}(1-p)^{2n}(1-p)^{2n}=\mu-\mu(1-p)^{2n}$
(5.3) $\displaystyle Cov[X_{i}(n),X_{j}(n)]$
$\displaystyle=E[X_{i}(n)X_{j}(n)]-E[X_{i}(n)]E[X_{j}(n)]$ (5.4)
$\displaystyle=\left\\{\begin{array}[]{ll}0&\mbox{i,j not adjacent};\\\
(1-p)^{2n}(1-p)^{2n-1}-(1-p)^{2n}(1-p)^{2n}=\frac{\mu^{2}}{3^{2n}}(\frac{p}{1-p})&\mbox{i,j
adjacent}.\end{array}\right.$ (5.7)

and finally:

$\displaystyle
Var[X(n)]=\mu-\mu(1-p)^{2n}+\frac{\mu^{2}}{3^{n}}(\frac{2np}{1-p})=\mu+\mu(1-p)^{2n}(\frac{2np}{1-p}-1)$
(5.8)

Now, since we have $Var[X(n)]$, we can use Chebyshev’s inequality to estimate
$g_{n}(p)$. Chebyshev’s inequality states that:

$\displaystyle
1-g_{n}(p)=\textbf{P}[X(n)=0]\leq\textbf{P}[|X(n)-\mu|\geq\mu]\leq\frac{Var[X(n)]}{\mu^{2}}$
(5.9)

By applying Chebyshev’s inequality when $p<(\sqrt{3}-1)/(\sqrt{3})$, one gets
$Var[X(n)]/\mu^{2}\rightarrow 0$, as $n\rightarrow\infty$. Therefore
$\lim_{n\rightarrow\infty}g_{n}(p)=1$. And finally, since $f_{n}(p)\leq
1-g_{n}(p)$, then for $p<(\sqrt{3}-1)/(\sqrt{3})$ the probability that
${}^{3}Q_{p_{n}}^{n}$ is connected, as $n\rightarrow\infty$, tends to $0$.
$\blacksquare$

For $p_{n}>\frac{\sqrt{3}-1}{\sqrt{3}}$:
Assume $p$ is fixed and $p>(\sqrt{3}-1)/(\sqrt{3})$. In order to calculate
$g_{n}(p)$ when $p>(\sqrt{3}-1)/(\sqrt{3})$, as $n\rightarrow\infty$, one can
use the following inequality:

$\displaystyle g_{n}(p)=\textbf{P}[X(n)>0]\leq E[X(n)]=\mu$ (5.10)

Since $E[X(n)]\rightarrow 0$ as $n\rightarrow\infty$, then
$\lim_{n\rightarrow\infty}g_{n}(p)=0$. This means that the probability that
there are no isolated points in ${}^{3}Q_{p_{n}}^{n}$ for
$p>(\sqrt{3}-1)/(\sqrt{3})$, as $n\rightarrow\infty$, tends to $1$.
$\blacksquare$

For $p_{n}=1-(1/\sqrt{3})\lambda^{1/2n}(1+o(1/n))$:
One needs the following theorem from [1] to find the distribution of $X(n)$
(distribution of the number of isolated points).

######  Theorem 11.

Let $\lambda=\lambda(n)$ be a non-negative bounded function on N. Suppose the
non-negative integer valued random variables $X(1),X(2),...$ are such that:

$\displaystyle\lim_{n\rightarrow\infty}\\{E_{r}[X(n)]-\lambda^{r}\\}=0,\text{
}r=0,1,...$ (5.11)

where $E_{r}[X]$ is the $r$th factorial moment of $X$, i.e.
$E_{r}[X]=E[(X)_{r}]$. Then

$\displaystyle X(n)\stackrel{{\scriptstyle
d}}{{\longrightarrow}}\textbf{P}_{\lambda}$ (5.12)

Use the definition of $X(n)$ presented in definition 25. The goal is to
calculate $E[X(n)]$.

$\displaystyle E_{r}[X(n)]=E[X(n)(X(n)-1)(X(n)-2)...(X(n)-r+1)]$ (5.13)

Since $X(n):=\sum_{i\in V(Q_{p}^{n})}X_{i}(n)$ and $X_{i}$’s are indicator
functions, therefore:

$\displaystyle
X(n)(X(n)-1)(X(n)-2)...(X(n)-r+1)=\sum_{(i_{1},i_{2},...,i_{r})}X_{i_{1}}X_{i_{2}}...X_{i_{r}}$
(5.14)

where the sum is over all ordered sets of distinct vertices. Then:

$\displaystyle E_{r}[X(n)]$
$\displaystyle=E[X(n)(X(n)-1)(X(n)-2)...(X(n)-r+1)]$ (5.15)
$\displaystyle=E[\sum_{(i_{1},i_{2},...,i_{r})}X_{i_{1}}X_{i_{2}}...X_{i_{r}}]$
(5.16)
$\displaystyle=\sum_{(i_{1},i_{2},...,i_{r})}\textbf{P}[X_{i_{1}}=1,X_{i_{2}}=1,...,X_{i_{r}}=1]$
(5.17)

One knows that a set of $r$ vertices is incident with at most $2rn$ edges.
There are $(r)_{r}\binom{3^{n}}{r}$ ways to choose such $r$ vertices. Hence:

$\displaystyle
E_{r}[X(n)]\geq(r)_{r}\binom{3^{n}}{r}(1-p_{n})^{2rn}=(3^{n})_{r}(1-p_{n})^{2rn}$
(5.18)

One the other hand, a set of $r$ vertices is incident with at least $r(2n-r)$
edges. There are at most $(r-1)_{r-1}\binom{3^{n}}{r-1}(r-1)2n$ ways to choose
a set of $r$ vertices in ${}^{3}Q_{p_{n}}^{n}$ where at least two vertices are
adjacent; since if we choose $r-1$ vertices independently, then the last
vertex must be connected to one of the chosen vertices. In other words, there
are at most $(r-1)_{r-1}\binom{3^{n}}{r-1}(r-1)2n$ ways to choose $r$ vertices
which some of them are adjacent to each other. Hence:

$\displaystyle E_{r}[X(n)]$
$\displaystyle\leq(3^{n})_{r}(1-p_{n})^{2rn}+(r-1)_{r-1}\binom{3^{n}}{r-1}2(r-1)n(1-p_{n})^{r(2n-r)}$
(5.19)
$\displaystyle\leq(3^{n})_{r}(1-p_{n})^{2rn}+(3^{n})_{r}2rn(1-p_{n})^{r(2n-r)}$
(5.20)
$\displaystyle\leq(3^{n})_{r}(1-p_{n})^{2rn}+3^{n(r-1)}2rn(1-p_{n})^{r(2n-r)}$
(5.21)

Finally from 5.18 and 5.21 one gets:

$\displaystyle(3^{n})_{r}(1-p_{n})^{2rn}\leq
E_{r}[X(n)]\leq(3^{n})_{r}(1-p_{n})^{2rn}+3^{n(r-1)}2rn(1-p_{n})^{r(2n-r)}$
(5.22)

which gives:

$\displaystyle(3(1-p_{n})^{2})^{rn}(1-\frac{r}{3^{n}})^{r}\leq
E_{r}[X(n)]\leq(3(1-p_{n})^{2})^{rn}\\{1+3^{-n}2rn(1-p_{n})^{-r^{2}}\\}$
(5.24)

Since $r$ is fixed and
$\lim_{n\rightarrow\infty}(3(1-p_{n})^{2})^{n}=\lambda$, then:

$\displaystyle\lim_{n\rightarrow\infty}(E_{r}[X(n)])=\lambda^{r}\text{ for
r=0,1,2,...}$ (5.25)

This shows that $X(n)\stackrel{{\scriptstyle
d}}{{\longrightarrow}}\textbf{P}_{\lambda}$. $\blacksquare$

For $p=0.5$:
In the calculation of $p_{n}=1-1/\sqrt{3}\lambda^{1/2n}(1+o(1/n))$, if we fix
$p=(\sqrt{3}-1)/(\sqrt{3})$ and let $\lambda=1$, then we get that the
distribution of $X(n)$ , as $n\rightarrow\infty$, tends to a Poisson
distribution with mean $1$. Therefore, one can conclude:

$\displaystyle\lim_{n\rightarrow\infty}(1-g_{n}(p))=\lim_{n\rightarrow\infty}(\textbf{P}(X(n)=0))=e^{-1}$
(5.26)

This shows that for $p=(\sqrt{3}-1)/(\sqrt{3})$ the probability that
${}^{3}Q_{p_{n}}^{n}$ has no isolated point, as $n\rightarrow\infty$, tends to
$e^{-1}$. $\blacksquare$

###  5.2 Isoperimetric problem for the 3-cube

One needs an inequality which relates the size of a subgraph of ${}^{3}Q^{n}$
to the size of its boundary. This inequality will be applied to prove that for
$p\geq(\sqrt{3}-1)/(\sqrt{3})$, the probability that subgraphs of
${}^{3}Q^{n}$ do not have a component of size larger than $2$ and smaller than
$3^{n}$, as $n\rightarrow\infty$, tends to $1$.

######  Definition 26.

The edge boundary $b_{G}(H)$, where $H$ is an induced subgraph of G, is the
number of edges which joins vertices in $H$ to the vertices in $G\backslash
H$.

The main task in this section is to calculate $b_{{}^{3}Q^{n}}(k)$. Since
${}^{3}Q^{n}$ is 2n-regular and $H$ is an induced subgraph of $G$ with
$|V(H)|=m$, then:

$\displaystyle b_{{}^{3}Q^{n}}(H)$ $\displaystyle=mn-2e(H),\text{where e(H) is
the total number of edges in H.}$ (5.27) $\displaystyle b_{{}^{3}Q^{n}}(k)$
$\displaystyle=mn-2e_{n}(k),\text{where }e_{n}(k)=max\\{e(H):H\text{ induced
subgraph of }^{3}Q^{n},|V(H)|=m\\}.$ (5.28)

######  Definition 27.

$h(i):=$ sum of digits in the ternary expansion of $i$ and
$f(l,m):=\displaystyle\sum_{l\leq i<m}h(i)$

######  Lemma 3.

If $1\leq k\leq l$, then $f(l,l+k)\geq f(0,k)+k$

Proof:
Look at the ternary expansion of a few numbers:

$\begin{array}[]{ccccc}Column&2&1&0\\\ Bin\backslash Dec&3^{2}&3^{1}&3^{0}\\\
0&&&0\\\ 1&&&1\\\ 2&&&2\\\ 3&&1&0\\\ 4&&1&1\\\ 5&&1&2\\\ 6&&2&0\\\ 7&&2&1\\\
8&&2&2\\\ 9&1&0&0\\\ 10&1&0&1\\\ 11&1&0&2\\\ 12&1&1&0\\\ 13&1&1&1\\\
14&1&1&2\\\ 15&1&2&0\\\ 16&1&2&1\\\ 17&1&2&2\\\ 18&2&0&0\\\ 19&2&0&1\\\
20&2&0&2\\\ 21&2&1&0\end{array}$

From this representation, one can observe that column $i$ starts with a block
of $3^{i}$ zeros. Therefore, sum of jth digits of $k$ numbers, one after the
other, is minimal if the first block of $0$’s is as long as possible. Hence,
one can conclude:

$\displaystyle f(l,l+k)\geq f(0,k)$ (5.29)

For every $i$ define $r$ such that $0\leq i\leq 3^{r}-1$. The ternary
expansions of $i$ and $3^{r}-1-i$ are symmetric. This means that, if there is
a $2/0$ in an specific location of the ternary expansion of $i$ then there is
a $0/2$ in the same location of the ternary expansion of $3^{r}-1-i$; and if
there is a $1$ in an specific location of the ternary expansion of $i$ then
there is a $1$ in the same location of the ternary expansion of $3^{r}-1-i$.
Therefore,

$\displaystyle h(i)+h(3^{r}-1-i)=2r\text{ for }0\leq i\leq 3^{r}-1$ (5.30)

Consequently, since:

$\displaystyle\displaystyle\sum_{l\leq
i<l+k}h(i)+\displaystyle\sum_{3^{r}-l-k\leq i<3^{r}-l}h(i)=2rk$ (5.31)

then:

$\displaystyle f(l,l+k)+f(3^{r}-l-k,3^{r}-l)=2rk,\text{where }l+k\leq 3^{r}$
(5.32)

One should first prove lemma 3 with the assumption $k\leq 3^{r}\leq l$ by
using 5.29 and 5.32. This assumption means that the length of the sequence of
0’s, 1’s and 2’s in the ternary expansion of $3^{r}+k$ and $3^{r}$ are equal.

With the same logic that one gets 5.29, one gets:

$\displaystyle f(l,l+k)\geq f(3^{r},3^{r}+k)\text{, when }3^{r}\leq l$ (5.33)

and then for $k\leq 3^{r}$ one can get:

$\displaystyle f(3^{r},3^{r}+k)=\displaystyle\sum_{3^{r}\leq i<3^{r}+k}h(i)$
(5.34)

$\sum_{3^{r}\leq i<3^{r}+k}h(i)$ is the sum over numbers with the same length
in their ternary expansion’s sequence. When one removes the last digit in
their ternary expansion, what remains is $f(0,k)$. Therefore, $\sum_{3^{r}\leq
i<3^{r}+k}h(i)$ is equal to sum of the last digits plus $f(0,k)$. Hence:

$\displaystyle f(l,l+k)\geq f(3^{r},3^{r}+k)=k+f(0,k)\text{ when }k\leq
3^{r}\leq l$ (5.35)

and finally:

$\displaystyle f(l,l+k)\geq f(0,k)+k\text{ where }k\leq 3^{r}\leq l$ (5.36)

Lemma 3 is proved with the assumption $k\leq 3^{r}\leq l$. Now, one should
prove lemma 3 without this assumption. The proof is based on induction on $K$.
We want to prove that for $1\leq K\leq l$, $f(l+K,l)\geq K+f(0,K)$. Fix $k$
such that $1\leq k\leq l$ and $K<k$. For $K=1$ the inequality is trivial.
Assume that the inequality is true for $K<k$ and $K>2$, which means:

$\displaystyle f(l,l+K)\geq K+f(0,K)\text{ when }1\leq k\leq l\text{ , and
}K<k$ (5.37)

Now, one should prove the inequality for $K=k$. Define $r\geq 1$ by
$3^{r-1}\leq k<3^{r}$. If $l\geq 3^{r}$, then $k\leq 3^{r}\leq l$ and the
lemma is implied by inequality 5.36. One may assume that $3^{r-1}<l<3^{r}$.
Finally, one should apply inequality 5.32 and 5.37 in order to get the final
result:

$\displaystyle f(l+k)$ $\displaystyle=f(l,3^{r})+f(3^{r},l+k)\text{\emph{
(from definition of f and }}l\geq 3^{r})$ (5.38)
$\displaystyle=(3^{r}-l)2r-f(0,3^{r}-l)+f(3^{r},l+k)\text{ \emph{ (from
\ref{2.5})}}$ (5.39)
$\displaystyle\geq(3^{r}-l)2r-f(0,3^{r}-l)+f(0,l+k-3^{r})+l+k-3^{r}\text{\emph{
(from \ref{2.7})}}$ (5.40)
$\displaystyle\geq(3^{r}-l)2r-f(3^{r}-k,3^{r}-k+3^{r}-l)+3^{r}-l+f(0,l+k-3^{r})+l+k-3^{r}\text{
\emph{(from \ref{2.7})}}$ (5.41)
$\displaystyle\geq(3^{r}-l)2r-f(3^{r}-k,3^{r}-k+3^{r}-l)+f(0,l+k-3^{r})+k$
(5.42) $\displaystyle\geq f(l+k-3^{r},k)+f(0,l+k-3^{r})+k\text{ \emph{(from
\ref{2.5})}}$ (5.43) $\displaystyle\geq f(0,k)+k\text{ \emph{(from
characteristics of f)}}$ (5.44)

$\blacksquare$

######  Theorem 12.

For $2\leq m\leq 3^{n}$ we have $b_{{}^{3}Q^{n}}(m)=mn-2f(0,m)$. In other
words, $f(0,m)=e_{n}(m)\text{ where }e_{n}(m)=\max\\{e(H):H\text{ induced
subgraph of ${}^{3}Q^{n}$ }|V(H)|=m\\}.$

Proof:
First, let us fix an $m$. As the first step, one should prove that
$e_{n}(m)\geq f(0,m)$. Vertex $i$ is connected to $h(i)$ vertices $j$ with
$j<i$, since for each $1$ ($2$) in the ternary expansion of $i$ there is
exactly one j $(j<i)$, which its ternary expansion differs in the position of
that $1$ ($2$). Therefore, on can conclude that $W=\\{0,1,2,...,m-1\\}$
contains $\sum_{0\leq i<m}h(i)=f(0,m)$ edges. So, $e_{n}(m)\geq f(0,m)$.

As the second step, one should prove that $e_{n}(m)\leq f(0,m)$ by induction
on $n$ for fixed $m$. For $n=1$ the inequality is trivially true. Assume that
it is true for $N<n$, which means:

$\displaystyle e_{N}(m)\leq f(0,m),\text{ where }N<n\text{ and the fixed m is
}3\leq m\leq 3^{n}$ (5.45)

Now, one should check the inequality 5.45 for $N=n$. This means that we should
find an $H$ induced subgraph of ${}^{3}Q^{n}$, $|V(H)|=m$, which maximize
$e_{n}(m)$. Let us split ${}^{3}Q^{n}$ into three (n-1)-dimensional cubes,
face-1, face-2 and face-3 each with $3^{n-1}$ vertices and $(n-1)3^{n-1}$
edges. Now, one can construct $H$. Choose $m_{1}$ vertices for $H$ from
face-1, $m_{2}$ vertices from face-2, and $m_{3}$ vertices from face-3 where
$m_{1}+m_{2}+m_{3}=m$ and $m_{1}\leq m_{2}\leq m_{3}$ and $m_{1}+m_{2}\leq
m_{3}$. In other words, $H$ is constructed from three induced subgraphs,
denoted by $H_{1}$, $H_{2}$, and $H_{3}$.

Each face is a (n-1)-dimensional cube, therefore inequality 5.45 holds for
$H_{1}$, $H_{2}$ and $H_{3}$. Also, each vertex of each face is connected to
exactly on vertex from one face and one vertex from the other face. Hence, the
number of vertices of $H$ is at most:

$\displaystyle e_{n}(m)\leq f(0,m_{1})+f(0,m_{2})+f(0,m_{3})+2m_{1}+m_{2}$
(5.46)

$2m_{1}+m_{2}$ is the maximum number of edges between three faces that one can
choose here. $2m_{1}$ is the maximum number of edges between chosen vertices
in $H_{1}$ and $H_{2}$ plus the maximum number of edges between chosen
vertices in $H_{1}$ and $H_{3}$. Consequently, $m_{2}$ is the maximum number
of edges between chosen vertices in $H_{2}$ and $H_{3}$. Therefore:

$\displaystyle e_{n}(m)$ $\displaystyle\leq
f(0,m_{1})+f(0,m_{2})+f(0,m_{3})+2m_{1}+m_{2}\text{ (from \ref{2.21})}$ (5.47)
$\displaystyle\leq f(m_{2},m_{2}+m_{1})+f(0,m_{2})+m_{1}+m_{2}\text{ (from
lemma \ref{2.1})}$ (5.48) $\displaystyle\leq
f(m_{3},m_{3}+m_{2}+m_{1})+f(0,m_{3})\text{ (from lemma \ref{2.1})}$ (5.49)
$\displaystyle\leq f(0,m)\text{ (from definition of f)}$ (5.50)

$\blacksquare$
Theorem 12 shows that, if we want to choose an induced subgraph of
${}^{3}Q^{n}$, with $m$ vertices, which has the smallest edge boundary, then
we should choose the induced subgraph of ${}^{3}Q^{n}$ with the set of
vertices $W=\\{0,1,2,...,m-1\\}$.

######  Corollary 2.

For all $k$ and $n$, $e_{n}(k)\leq k\lceil log_{3}k\rceil$, which is
equivalent to $b_{{}^{3}Q^{n}}(k)\geq 2k(n-\lceil log_{3}k\rceil)$.

Proof:
Let $r=\lceil\log_{3}k\rceil$. Then

$\displaystyle 2f(0,k)$ $\displaystyle=f(0,k)+f(0,k)\leq
f(0,k)+f(3^{r}-k,3^{r})\text{ (from \ref{2.2})}$ (5.51)
$\displaystyle=2rk\text{ (from \ref{2.5})}$ (5.52)

Therefore:

$\displaystyle e_{n}(k)=f(0,k)\leq rk=k\lceil\log_{3}k\rceil$ (5.53)

$\blacksquare$

###  5.3 Isolated components of size larger than 2 and smaller than $3^{n}$

######  Definition 28.

$C_{s}$ is the family of s-subsets (subsets with size s) of $V=V(^{3}Q^{n})$
whose induced graph is connected.

Remarks: $h(n):=o(g(n))$ means $\frac{h(n)}{g(n)}\rightarrow 0$ as
$n\rightarrow\infty$.
Remarks: The following inequality will be applied a lot in the rest of this
section:

$\displaystyle(\frac{n}{k})^{k}\leq\binom{n}{k}\leq\frac{n^{k}}{k!}\leq(\frac{ne}{k})^{k}$
(5.54)

######  Theorem 13.

If $p_{n}\geq 1-\frac{1}{\sqrt{3}}(\log n)^{\frac{1}{n}}$, the probability
that for some $S\in C_{s},2\leq s\leq\frac{3^{n}}{2}$, no edges of
${}^{3}Q_{p_{n}}^{n}$ join $S$ to $V(^{3}Q^{n})\setminus S$, as
$n\rightarrow\infty$, tends to 0.

Note: For $\frac{3^{n}}{2}<s<3^{n}$, if there exist a component of size
smaller than $3^{n}$ then there is at least one component of size smaller than
$\frac{3^{n}}{2}$ which contradicts with the theorem.

Proof:
Consider $S\subset V=V(^{3}Q^{n})$ and set $b(S)=b_{Q^{n}}(H)$ where $H$ is
the induced subgraph of ${}^{3}Q^{n}$ with the set of vertices S. One can
observe that:

$\displaystyle\textbf{P}(\text{No edges of }^{3}Q_{p_{n}}^{n}\text{ join S to
}V\setminus S)=(1-p_{n})^{b(S)}$ (5.55)

In order to prove the theorem, it is sufficient to show:

$\displaystyle\sum_{s=2}^{3^{\frac{n}{2}}}\sum_{S\in
C_{s}}(1-p_{n})^{b(S)}=o(1)$ (5.56)

From corollary 2, one knows that for $|S|=s$:

$\displaystyle b(S)\geq b(s)\geq 2s(n-\lceil\log_{3}s\rceil)$ (5.57)

and therefore:

$\displaystyle\sum_{S\in C_{s}}(1-p_{n})^{b(S)}\leq|C_{s}|(1-p_{n})^{b(s)}$
(5.58)

One may partition $s$, $2\leq s\leq\frac{3^{n}}{2}$, to different intervals in
order to find a small enough bound for $|C_{s}|$ and $(1-p_{n})^{b(s)}$.

First interval $2\leq s\leq
s_{1},s_{1}=\lfloor\frac{3^{\frac{n}{2}}}{n^{2}}\rfloor$:

First, one should find a bound for $|C_{s}|$. One has maximum $3^{n}$ choices
to choose the first element for $C_{s}$. The selected element is connected to
maximum $2n$ vertices, therefore, there are maximum $2n$ choices to choose the
second element. With the same logic, there are at most $2n(s-1)$ choices to
choose the last element for $|C_{s}|$. Hence, one can show:

$\displaystyle|C_{s}|\leq
3^{n}(2n)(2n(2))...(2n(s-1))\leq(s-1)!(2n)^{s-1}3^{n}$ (5.59)

and:

$\displaystyle|C_{s}|(1-p_{n})^{b(s)}\leq(s-1)!(2n)^{s-1}3^{n}(1-p_{n})^{2s(n-\lceil\log_{3}s\rceil)}$
(5.60)

Since $p_{n}=1-\frac{1}{\sqrt{3}}(\log n)^{\frac{1}{n}}$, so for large enough
$n$:

$\displaystyle(1-p_{n})^{2s(n-\lceil log_{3}s\rceil)}$
$\displaystyle\leq(3)^{-ns}(\log
n)^{2s}(1-p_{n})^{-2s(\log_{3}s)}\text{(neglecting some small terms)}$ (5.61)
$\displaystyle\text{( since: }(\log n)^{\frac{-2s\log_{3}s}{n}}\leq 1\text{
for large enough }n)$ (5.62) $\displaystyle=(3)^{-ns}(\log
n)^{2s}3^{s\log_{3}s}(\log n)^{\frac{-2s\log_{3}s}{n}}$ (5.63)
$\displaystyle\leq(3)^{-ns}(\log n)^{2s}s^{s}$ (5.64)

From equations 5.60 and 5.64, one gets:

$\displaystyle|C_{s}|(1-p_{n})^{b(s)}\leq(s-1)!(2n)^{s-1}3^{n}(3)^{-ns}(\log
n)^{2s}s^{s}$ (5.65)

Assume that the right hand sides of inequality 5.65 is equal to A. After
multiplying both side of inequality 5.65 with $\frac{2ns^{s+1}}{s!}$ and then
getting $\log_{3}$ from both sides, one gets:

$\displaystyle\log_{3}(|C_{s}|(1-p_{n})^{b(s)}\frac{2ns^{s+1}}{s!})\leq\log_{3}(A\frac{2ns^{s+1}}{s!})$
(5.66)

If $\log_{3}(A\frac{2ns^{s+1}}{s!})\rightarrow-\infty$ as $n\rightarrow\infty$
then $A\frac{2ns^{s+1}}{s!}$ should tend to 0\. This means that
$|C_{s}|(1-p_{n})^{b(s)}\frac{2ns^{s+1}}{s!}$ tends to 0, as
$n\rightarrow\infty$. Therefore:

$\displaystyle|C_{s}|(1-p_{n})^{b(s)}\leq\frac{s!}{2ns^{s+1}}\text{ for large
values of n}$ (5.67)

which shows that:

$\displaystyle\sum_{s=2}^{s_{1}}\sum_{S\in C_{s}}(1-p_{n})^{b(S)}=o(1)$ (5.68)

Finally, it remains to prove
$\log_{3}(A\frac{2ns^{s+1}}{s!})\rightarrow-\infty$ as $n\rightarrow\infty$.
One can verify this for $s\leq n$ and $s>n$. $\blacksquare$

Second interval $s_{1}+1\leq s\leq\frac{3^{n}}{2}$ and $S\in
C_{s}^{-},s_{1}=\lfloor\frac{3^{\frac{n}{2}}}{n^{2}}\rfloor$:
Define $C_{s}^{-}$ and $C_{s}^{+}$ as follows:

######  Definition 29.

$\displaystyle C_{s}^{-}:=\\{S\in C_{s}|b(s)\geq
2s(n-\log_{3}s+\log_{3}n)\\}\text{, and }C_{s}^{+}:=C_{s}\backslash C_{s}^{-}$
(5.69)

One can bound $|C_{s}^{-}|$ for $s_{1}+1\leq s\leq 3^{\frac{n}{2}}$ as
follows:

$\displaystyle|C_{s}^{-}|\leq|C_{s}|\leq\binom{3^{n}}{s}\leq\frac{3^{ns}}{s!}\leq(\frac{e3^{n}}{s})^{s}$
(5.70)

Hence:

$\displaystyle\displaystyle\sum_{s=s_{1}+1}^{3^{\frac{n}{2}}}\sum_{S\in
C_{s}^{-}}(1-p_{n})^{b(S)}$
$\displaystyle\leq\sum_{s=s_{1}+1}^{3^{\frac{n}{2}}}(\frac{e3^{n}}{s})^{s}(\sqrt{3}^{-1}(\log
n)^{\frac{1}{n}})^{2s(n-\log_{3}s+\log_{3}n)}$ (5.71)
$\displaystyle\leq\sum_{s=s_{1}+1}^{3^{\frac{n}{2}}}(\frac{e3^{n}3^{-(n-\log_{3}s+\log_{3}n)}(\log
n)^{\frac{2(n-\log_{3}s+\log_{3}n)}{n}}}{s})^{s}$ (5.72)
$\displaystyle\leq\sum_{s=s_{1}+1}^{3^{\frac{n}{2}}}(\frac{e3^{n}3^{-n}3^{\log_{3}s}3^{-\log_{3}n}(\log
n)^{2}}{s})^{s}(\log n)^{\frac{2n(-\log_{3}s+\log_{3}n)}{s}}$ (5.73)
$\displaystyle\text{ (since for large enough n: }(\log
n)^{\frac{2n(-\log_{3}s+\log_{3}n)}{s}}\leq 1)$ (5.74)
$\displaystyle\leq\sum_{s=s_{1}+1}^{3^{\frac{n}{2}}}(\frac{e(\log
n)^{2}}{n})^{s}=o(1)$ (5.75)

$\blacksquare$

Third interval $s_{1}\leq s\leq
s_{2},s_{1}=\lfloor\frac{3^{\frac{n}{2}}}{n^{2}}\rfloor,s_{2}=\lfloor\frac{3^{n}}{(\log
n)^{7}}\rfloor$ and $S\in C_{s}^{+}$:
For the 3rd and the 4th intervals one needs to find a bound for $|C_{s}^{+}|$.
The following lemma, presented by B.Bollobas [1], helps us in this matter:

######  Lemma 4.

Let G be a graph of order $v$ and suppose that $\Delta(G)\leq\Delta$,
$2e(G)=vd$ and $\Delta+1\leq u\leq v-\Delta-1$. Then, there is a u-set of U of
vertices with [1]:

$\displaystyle|N(U)|=|U\cup\Gamma(U)|\geq
v\frac{d}{\Delta}\\{1-\exp(\frac{-u(\Delta+1)}{v})\\}$ (5.76)

where, $\Delta(G):=$ Maximum degree in G, $d:=$ average degree in G and
$\Gamma(U)=\\{x\in V(G):xy\in E(G)\text{ for some y}\in U\\}$

Let $H=$${}^{3}Q^{n}[S]$ (the induced subgraph of ${}^{3}Q_{n}$ with the set
of vertices $S$). From the definition of $C_{s}^{+}$ one knows that the
average degree in $H$ is at least:

$\displaystyle 2(\log_{3}s-\log_{3}n)$ (5.77)

The goal is to find $U\subset S$, where $|U|:=u:=\lfloor\frac{2s}{n}\rfloor$,
$\Delta=2n$, $v=s$, $d\geq\log_{3}s-\log_{3}n$ and then use lemma 4 to
calculate the boundary size of $U,|N(U)|$. First, check if
$2n+1\leq\lfloor\frac{2s}{n}\rfloor$, as $n\rightarrow\infty$:

$\displaystyle\frac{2s}{n}=\frac{23^{n/2}}{n^{3}}\text{for minimum s, and
trivially }2n+1\leq\frac{23^{n/2}}{n^{3}},\text{for large enough }n$ (5.78)

and then check if $\lfloor\frac{2s}{n}\rfloor\leq s-(2n+1)$. One should check
if $ns-n(2n+1)\geq 2s$ which means one should check that whether:

$\displaystyle\frac{3^{\frac{n}{2}}(n-2)}{n^{3}(2n+1)}\geq 1$ (5.80)

which is clearly true for large enough $n$. Now, one can apply lemma 4 on the
graph generated by $S$ and get:

$\displaystyle\exists U\subset S:|N(U)|\geq
s\frac{2(\log_{3}s-\log_{3}n)}{2n}\\{1-\exp(-\frac{u(2n+1)}{s})\\}$ (5.81)

where:

$\displaystyle\frac{2(\log_{3}s-\log_{3}n)}{2n}\geq\frac{(\log_{3}(\frac{3^{\frac{n}{2}}}{n^{2}})-\log_{3}n)}{n}=\frac{\frac{n}{2}-3\log_{3}n}{n}$
(5.82) $\displaystyle\text{which
}\lim_{n\rightarrow\infty}\frac{\frac{n}{2}-3\log_{3}n}{n}=\frac{1}{2}$ (5.83)

on the other hand:

$\displaystyle\lim_{n\rightarrow\infty}(1-\exp(-\frac{2n+1}{s}(\frac{2s}{n}+1)))=1-e^{-4}$
(5.84)

Therefore, from 5.83 and 5.84 one gets:

$\displaystyle|N(U)|\geq\frac{1}{2}(1-e^{-4})s\geq\frac{s}{3}\text{ as
}n\rightarrow\infty$ (5.85)

Now that we have $|N(U)|$, we can estimate a bound for $|C_{s}^{+}|$ here. We
know from 5.85 that for each $S\in C_{s}^{+}$ there exist a $U\subseteq S$,
$|U|:=u:=\lfloor\frac{2s}{n}\rfloor$, such that $|N(U)|\geq s/3$. Therefore,
one can choose $S\in C_{s}^{+}$ as follows:
1\. Select u vertices of ${}^{3}Q^{n}$; there are $\binom{3^{n}}{u}$ choices
for this u.
2\. Select $\lfloor\frac{s}{3}\rfloor-u$ neighbors of the selected vertices of
u in part 1; there are maximum $(2^{n})^{u}$ choices, since there are at most
$\binom{2n}{0}+\binom{2n}{1}+\binom{2n}{2}+...\binom{2n}{2n}=2^{2n}$ ways to
find neighbors of a vertex in $U$.
3\. Select $\lfloor\frac{2s}{3}\rfloor$ other vertices; there are at most
$\binom{3^{n}}{\lfloor\frac{2s}{3}\rfloor}$ choices.
Hence:

$\displaystyle|C_{s}^{+}|\leq\binom{3^{n}}{u}(2^{2n})^{u}\binom{3^{n}}{\lfloor\frac{2s}{3}\rfloor}$
(5.86)

and:

$\displaystyle\sum_{S\in
C_{s}^{+}}(1-p_{n})^{b(S)}\leq\binom{3^{n}}{u}(2^{2n})^{u}\binom{3^{n}}{\lfloor\frac{2s}{3}\rfloor}(1-p_{n})^{b(s)}$
(5.87)

where:

$\displaystyle(1-p_{n})^{b(s)}\leq 3^{-sn}s^{s}(\log n)^{2s}$ (5.88)

consequently from 5.87, 5.88 and 5.54:

$\displaystyle\sum_{S\in
C_{s}^{+}}(1-p_{n})^{b(S)}\leq(\frac{e3^{n}}{u})^{u}2^{2un}(\frac{e3^{n}}{\lfloor\frac{2s}{3}\rfloor})^{\lfloor\frac{2s}{3}\rfloor}3^{-sn}s^{s}(\log
n)^{2s}$ (5.89)

Write $s=3^{\beta n}$, ($\beta=\frac{log_{3}s}{n}$), so that:

$\displaystyle 3^{\beta n}\leq\frac{3^{n}}{(\log n)^{7}}\Rightarrow\beta\leq
1-\frac{7\log_{3}\log n}{n}$ (5.90)

Now, find a bound for the inequality 5.89. First calculate the first part of
the inequality:

$\displaystyle(\frac{e3^{n}}{u})^{u}2^{2un}(\frac{e3^{n}}{\lfloor\frac{2s}{3}\rfloor})^{\lfloor\frac{2s}{3}\rfloor}$
$\displaystyle\leq(\frac{e3^{n}}{\frac{2s}{n}})^{\frac{2s}{n}}3^{2s}2^{4s}(\frac{e3^{n}}{\frac{2s}{3}})^{\frac{2s}{3}}$
(5.91) $\displaystyle\text{ (since for large enough n and $s_{1}\leq s\leq
s_{2}$: }(\frac{e3^{n}}{\frac{2s}{n}})^{\frac{2s}{n}}\leq 1)$ (5.92)
$\displaystyle\leq(3^{2}2^{4}(\frac{3}{2}e)^{\frac{2}{3}})^{s}\frac{3^{\frac{2s}{3n}}}{s^{\frac{2s}{3}}}=c^{s}3^{\frac{2}{3}sn(1-\frac{\log_{3}s}{n})}=c^{s}3^{\frac{2}{3}sn(1-\beta)}$
(5.93)

where c is a positive constant. Now, by substituting 5.93 in 5.89 one gets:

$\displaystyle\sum_{S\in C_{s}^{+}}(1-p_{n})^{b(S)}$ $\displaystyle\leq
3^{-sn}s^{s}(\log n)^{2s}c^{s}3^{\frac{2}{3}sn(1-\beta)}$ (5.94)
$\displaystyle=c^{s}(\log n)^{2s}3^{-\frac{sn(1-\beta)}{3}}$ (5.95)
$\displaystyle\leq c^{s}(\log n)^{2s}3^{-\frac{7s\log_{3}\log n}{3n}}\text{ ,
(from \ref{2.13})}$ (5.96) $\displaystyle=c^{s}(\log n)^{2s}3^{\log_{3}(\log
n)^{\frac{-7s}{3}}}$ (5.97) $\displaystyle\leq c^{s}(\log n)^{2s}(\log
n)^{\frac{-7s}{3}}$ (5.98) $\displaystyle=c^{s}(\log n)^{\frac{-s}{3}}$ (5.99)

and finally from 5.99:

$\displaystyle\sum_{s=s_{1}}^{s_{2}}\sum_{S\in
C_{s}^{+}}(1-p_{n})^{b(S)}\leq\sum_{s=s_{1}}^{s_{2}}c^{s}(\log
n)^{\frac{-s}{3}}=o(1)$ (5.100)

$\blacksquare$

Fourth interval $s_{2}+1\leq s\leq\frac{3^{n}}{2}$ and
$,s_{2}=\lfloor\frac{3^{n}}{(\log n)^{9}}\rfloor,S\in C_{s}^{+}$:

In $H=$${}^{3}Q^{n}[S]$ (the induced subgraph ${}^{3}Q^{n}$ with the set of
vertices S), the average degree is at least:

$\displaystyle 2(\log_{3}s-\log_{3}n)>2(n-2\log_{3}n)$ (5.101)

since:

$\displaystyle s\geq\lceil\frac{3^{n}}{(\log
n)^{9}}\rceil\Rightarrow\log_{3}(\frac{3^{n}}{(\log n)^{9}})<\log_{3}s$
(5.102)
$\displaystyle\Rightarrow\log_{3}s-\log_{3}n\geq\log_{3}(\frac{3^{n}}{(\log
n)^{9}})-\log_{3}n\geq n-\log_{3}(\log n)^{9}-\log_{3}n$ (5.103)
$\displaystyle(\text{for large enough n one can get }n>(\log n)^{9})$ (5.104)
$\displaystyle\geq n-2\log_{3}n$ (5.105)

First, look for a subgraph of H with large average degree. Let T be the set of
vertices of H with degree at least $2(n-(\log_{3}n)^{2})$, and set $t=|T|$.
From 5.101 one can conclude that the sum of degrees in $H$ is at least
$s(n-2\log_{3}n)$. We also know that:

$\displaystyle\text{Sum of degrees in }S$ $\displaystyle\leq 2s(n-2\log_{3}n)$
(5.106) $\displaystyle\leq t\times(\text{Maximum degree of vertices in set $T$
of graph $H$ })$ (5.107) $\displaystyle+(s-t)\times(\text{Maximum degree of
vertices in set $S\setminus T$ of graph $H$ })$ (5.108) $\displaystyle\leq
2tn+2(s-t)(n-(\log_{3}n)^{2}$ (5.109) $\displaystyle\Rightarrow t\geq
s(1-\frac{4}{\log_{3}n})$ (5.110)

Define $H_{1}=$${}^{3}Q^{n}[T]=H[T]$ as the induced subgraph spanned by $T$.
We want to calculate $|N_{H_{1}}(U)|$ in $H_{1}$, hence we should estimate the
size of $H_{1}$ and after that calculate the average degree in T. Let us first
calculate $e(H_{1})$, the total number of edges in $H_{1}$.

$\displaystyle e(H_{1})\geq e(H)-2(s-t)n\geq
2\frac{s}{2}(n-2\log_{3}n)-\frac{4s}{\log_{3}n}n\text{ (from \ref{2.33.1} and
\ref{2.34.1})}$ (5.111)

One knows that the average degree in $H_{1}$ is at least
$\frac{2e(H_{1})}{s}$, and:

$\displaystyle\frac{2e(H_{1})}{s}\geq 2(n-2\log_{3}n)-\frac{8n}{\log_{3}n}\geq
2n-\frac{9}{\log_{3}n}$ (5.112) $\displaystyle\text{(since:
}\log_{3}n^{2}<\frac{n}{\log_{3}n}\text{ for large enough n)}$ (5.113)

Set $u=\lfloor\frac{3^{n}}{n^{\frac{1}{2}}}\rfloor$. One should check the
conditions of lemma 3 here. Let $v=t,\Delta=2n,d\geq 2n-\frac{9}{\log_{3}n}$.
So, one should check if $2n+1\leq\frac{3^{n}}{n^{\frac{1}{2}}}\leq t-2(n+1)$,
for large enough $n$. Clearly, $2n+1\leq\frac{3^{n}}{n^{\frac{1}{2}}}$, as
$n\rightarrow\infty$. It remains to prove $\frac{3^{n}}{n^{\frac{1}{2}}}\leq
t-2(n+1)$, for large enough $n$. For minimum $s$ from 5.110 we can get:

$\displaystyle t\geq$ $\displaystyle\frac{3^{n}}{(\log
n)^{7}}(1-\frac{4}{\log_{3}n})\text{ (from \ref{2.34.1})}$ (5.114)
$\displaystyle\geq\frac{3^{n}}{n^{\frac{1}{2}}}+2(n+1)\text{ (for large enough
n) }$ (5.115)

Now, one can use lemma 3 and estimate $|N_{H_{1}}(U)|$.

$\displaystyle|N_{H_{1}}(U)|$
$\displaystyle\geq\frac{t}{2n}(2n-\frac{9n}{\log_{3}n})\\{1-\exp(-\frac{2n+1}{t}\frac{3^{n}}{n^{\frac{1}{2}}})\\}$
(5.116)
$\displaystyle\geq\frac{t}{2}(n-\frac{9}{\log_{3}n})\\{1-\exp(-\frac{2n+1}{t}\frac{3^{n}}{n^{\frac{1}{2}}})\\}$
(5.117)

Let us estimate a bound for
$\exp(-\frac{2n+1}{t}\frac{3^{n}}{n^{\frac{1}{2}}})$. One knows that $t\geq
s(1-\frac{4}{\log_{3}n})$. Since $\max(t)=s$ and $\max(s)=\frac{3^{n}}{2}$,
then:

$\displaystyle\frac{3^{n}(2n+1)}{n^{\frac{1}{2}}t}\geq\frac{3^{n}(2n+1)}{n^{\frac{1}{2}}3^{n}}=\frac{(2n+1)}{n^{\frac{1}{2}}}\geq
n^{\frac{1}{4}}\text{ (for large enough n) }$ (5.118)
$\displaystyle\Rightarrow\\{1-\exp(-\frac{2n+1}{t}\frac{3^{n}}{n^{\frac{1}{2}}})\\}\geq\exp(-n^{\frac{1}{4}})\text{
(for large enough n) }$ (5.119)

By using the bound from 5.119 in 5.117, one gets:

$\displaystyle|N_{H}(U)|\geq|N(H_{1})|$
$\displaystyle\geq\frac{t}{2}(2-\frac{9}{\log_{3}n})\\{1-\exp(-n^{\frac{1}{4}})\\}$
(5.120)
$\displaystyle=\frac{t}{2}\\{2+\exp(-n^{\frac{1}{4}})\frac{9}{\log_{3}n}-2\exp(-n^{\frac{1}{4}})-\frac{9}{\log_{3}n}\\}$
(5.121)
$\displaystyle(\lim_{n\rightarrow\infty}\exp(-n^{\frac{1}{4}})\frac{9}{\log_{3}n}=0\text{
and }\exp(-n^{\frac{1}{4}})<\frac{1}{\log_{3}n}\text{ (for large enough n) })$
(5.122)
$\displaystyle\geq\frac{t}{2}\\{2-\frac{2}{\log_{3}n}-\frac{9}{\log_{3}n}\\}=\frac{t}{2}(2-\frac{11}{\log_{3}n})$
(5.123)
$\displaystyle\geq\frac{s}{2}(1-\frac{2}{\log_{3}n})(2-\frac{11}{\log_{3}n})=\frac{s}{2}(2+\frac{2}{\log_{3}n}\frac{11}{\log_{3}n}-\frac{15}{\log_{3}n})\text{
(for large enough n) }$ (5.124)
$\displaystyle\geq\frac{s}{2}(2-\frac{15}{\log_{3}n})=s(1-\frac{7.5}{\log_{3}n})$
(5.125)

Now that we have $|N_{H}(U)|$, we can estimate a bound for $|C_{s}^{+}|$ here.
We know from 5.125 that for each $S\in C_{s}^{+}$ there exist a $U\subseteq
S$, $|U|:=u:=\lfloor\frac{3^{n}}{n^{\frac{1}{2}}}\rfloor$, such that
$|N_{H}(U)|\geq s(1-\frac{7.5}{\log_{3}n})$. Therefore, one can choose $S\in
C_{s}^{+}$ as follows:
1\. Select u vertices of ${}^{3}Q^{n}$; there are $\binom{3^{n}}{u}$ choices
for this u.
2\. Select $\lfloor s(1-\frac{7.5}{\log_{n}3})\rfloor-u$ neighbors of the
selected vertices in part 1. At most $2(\log_{3}n)^{2}$ of the $2n$ neighbors
of a vertex in $U$ do not belong to $N_{H}(U)$. Hence there are at most
$\sum_{(k_{j})}(\prod_{i=1}^{u}\binom{2n}{j})$ ways to find neighbors of $u$
vertices in $U$, where the sum is over all $(k_{1},k_{2},...,k_{u}),k_{i}\leq
2(\log_{3}n)^{2}$. We know that:

$\displaystyle\sum_{(k_{i})}\prod_{i=1}^{u}\binom{2n}{k_{i}}$
$\displaystyle\leq\sum_{(k_{i})}\prod_{i=1}^{u}(\frac{(2n)^{i}}{i!})$ (5.126)
$\displaystyle\leq\sum_{(k_{i})}\prod_{i=1}^{u}(\frac{(2n)^{(2(\log_{3}n)^{2})}}{(2(\log_{3}n)^{2})!})$
(5.127)
$\displaystyle=\sum_{(k_{i})}\frac{(2n)^{2u(\log_{3}n)^{2}}}{((2(\log_{3}n)^{2})!)^{u}}$
(5.128)
$\displaystyle={(2(\log_{3}n)^{2})}^{u}\frac{(2n)^{2u(\log_{3}n)^{2}}}{((2(\log_{3}n)^{2})!)^{u}}$
(5.129) $\displaystyle\leq(2n)^{2u(\log_{3}n)^{2}}$ (5.130)

3\. Select $\lfloor\frac{7.5}{\log_{3}n}\rfloor$ other vertices; there are
$\binom{3^{n}}{\lfloor\frac{7.5}{\log_{3}n}\rfloor}$ choices.
Hence:

$\displaystyle\sum_{S\in
C_{s}^{+}}(1-p_{n})^{b(S)}\leq\binom{3^{n}}{u}(2n)^{2u(\log_{3}n)^{2}}\binom{3^{n}}{\lfloor\frac{7.5}{\log_{3}n}\rfloor}3^{-2s(n-\log_{3}s)}(\log
n)^{2s(1-\frac{\log_{3}s}{n})}$ (5.132)

where:

$\displaystyle\binom{3^{n}}{u}(2n)^{2u(\log_{3}n)^{2}}\binom{3^{n}}{\lfloor\frac{7.5}{\log_{3}n}\rfloor}=3^{o(s)}$
(5.134)

Therefore:

$\displaystyle\sum_{S\in C_{s}^{+}}(1-p_{n})^{b(S)}\leq 3^{\varepsilon(s)}$
(5.135)

where:

$\displaystyle\varepsilon(s)=o(s)-2s\\{n-\log_{3}s-\log_{3}\log
n+\frac{\log_{3}s}{n}\log_{3}\log n\\}$ (5.136)

Since $s\leq\frac{3^{n}}{2}$, hence one can get:

$\displaystyle\varepsilon(s)$ $\displaystyle\leq
o(s)-2s\\{n-(n-1)-\log_{3}\log n+\frac{n-1}{n}\log_{3}\log n\\}$ (5.137)
$\displaystyle=o(s)-2s\\{1-\frac{1}{n}\log_{3}\log n\\}\leq-s$ (5.138)

Therefore, for large enough n, one can get:

$\displaystyle\sum_{s=s_{2}+1}^{\frac{3^{n}}{2}}\sum_{S\in
C_{s}^{+}}(1-p_{n})^{b(S)}\leq\sum_{s=s_{2}+1}^{\frac{3^{n}}{2}}3^{-s}=o(1)$
(5.139)

$\blacksquare$

##  Chapter 6 Connected random subgraph of the $P_{3}$-product

The $P_{3}^{n}$ graph is the cartesian products of $n$ copies of $P_{3}$,
where $P_{3}$ stands for a path with length 2. If one labels each vertex of
$P_{3}^{n}$ from $0$ to $3^{n}-1$, then two vertices are adjacent if the
difference between their ternary representation is 1, in other words, vertex
$x=(x_{1},x_{2},...,x_{n})$ is connected to the vertex
$y=(y_{1},y_{2},...,y_{n})$ if for some $i$ we have $|x_{i}-y_{i}|=1$ and
$x_{j}=x_{j}$ for $j\neq i$. Vertex $x=(x_{1},x_{2},...,x_{n})$ is connected
to $n+i$ vertices where $i=|\\{j|x_{j}=1,j\in\\{1,..,n\\}\\}|$. A random
subgraph of $P_{3}^{n}$ contains all vertices of $P_{3}^{n}$, and each edge
independently with probability $p$. $p$ is called the percolation parameter
and $P_{3,p}^{n}$ stands for the random subgraph of $P_{3}^{n}$

The main goal in this chapter is to explore a critical value $p_{c}$, which
for fixed values of $p$ if $p<p_{c}$ then almost no random subgraphs of
$P_{3}^{n}$ is connected, as $n\rightarrow\infty$; but if $p>p_{c}$ then
almost all random subgraphs of $P_{3}^{n}$ are connected, as
$n\rightarrow\infty$. We suggest that this critical value is $2-\sqrt{2}$. The
proof in this chapter is not complete and there is a place for further work.

In the first section of this chapter, it is proved that for $p<2-\sqrt{2}$
almost no random subgraphs of $P_{3}^{n}$ are connected, as
$n\rightarrow\infty$. Then, it is proved that, for $p>2-\sqrt{2}$ almost all
random subgraphs of $P_{3}^{n}$ have no isolated point, as
$n\rightarrow\infty$. In the second section, the probability that random
subgraphs of $P_{3}^{n}$, with the percolation parameter $p>2-\sqrt{2}$, have
no components with size larger than $1$ and smaller than $3^{n}$, as
$n\rightarrow\infty$, is explored.

###  6.1 Isolated vertices

For $p<2-\sqrt{2}:$

Let us define $X_{i}$ and $X$ for a graph $G$ as follows:

######  Definition 30.

$X_{i}(n):=\left\\{\begin{array}[]{ll}1&\mbox{Vertex $i$ is isolated, $i\in
V(G)$};\\\ 0&\mbox{Vertex $i$ is NOT isolated, $i\in
V(G)$}.\end{array}\right.$ , and $X(n):=\displaystyle\sum_{i\in
V(G)}X_{i}(n)$.

As the first step we calculate $E[X(n)]$. One can categorize the set of
vertices $V$ into $n+1$ subsets $V_{i}$’s where $x=(x_{1},x_{2},...,x_{n})\in
V_{i}$ if $|\\{j|x_{j}=1,j\in\\{1,..,n\\}\\}|=i$. Hence:

$\displaystyle\mu:=E[X(n)]=\sum_{j\in
V(P^{n}_{3,p})}E[X_{j}(n)]=\sum_{i=0}^{n}\sum_{k\in
V_{i}}E[X_{k}(n)]=\sum_{i=0}^{n}\binom{n}{i}2^{n-i}(1-p)^{n+i}=(1-p)^{n}(3-p)^{n}$
(6.1)

From (6.1), the threshold value for $E[X]$ is $p_{c}=2-\sqrt{2}$ which is the
solution to the equation $(1-p)^{n}(3-p)^{n}=1$. This means that
$E[X]\rightarrow\infty$ for $p<p_{c}$, but $E[X]\rightarrow 0$ for $p>p_{c}$.
Now, one should calculate $Var[X]$.

$\displaystyle Var[X(n)]$ $\displaystyle=\sum_{i\in
V(P^{n}_{3,p})}Var[X_{i}(n)]+\sum_{i,j\in V(P^{n}_{3,p}),i\neq
j}Cov[X_{i}(n),X_{j}(n)]$ (6.2) $\displaystyle=\sum_{i=0}^{n}\sum_{k\in
V_{i}}Var[X_{k}(n)]+\sum_{i,j\in V(P^{n}_{3,p}),i\neq
j}Cov[X_{i}(n),X_{j}(n)]$ (6.3)

where:

$\displaystyle\sum_{i=0}^{n}\sum_{k\in V_{i}}Var[X_{k}(n)]$
$\displaystyle=\sum_{i=0}^{n}\binom{n}{i}2^{n-i}((1-p)^{n+i}-(1-p)^{2n+2i})$
(6.4) $\displaystyle=(1-p)^{n}(3-p)^{n}-(1-p)^{2n}(2+(1-p)^{2})^{n}$ (6.5)

In order to calculate $\sum_{i,j\in V(P^{n}_{3,p}),i\neq
j}Cov[X_{i}(n),X_{j}(n)]$ one should know that if $x\in V_{i}$ then $x$ is
incident to $2i$ vertices in $V_{i-1}$ and $n-i$ vertices in $V_{i+1}$. Also,
one knows:

$\displaystyle Cov[X_{i}(n),X_{j}(n)]$
$\displaystyle=E[X_{i}(n)X_{j}(n)]-E[X_{i}(n)]E[X_{j}(n)]=0\text{ if i,j not
adjacent}$ (6.6)

Hence:

$\displaystyle\sum_{i,j\in V(P^{n}_{3,p}),i\neq j}$ $\displaystyle
Cov[X_{i}(n),X_{j}(n)]$ (6.7)
$\displaystyle=\sum_{i=0}^{n}\binom{n}{i}2^{n-i}\\{(n-i)(1-p)^{n+i-1}(1-p)^{n+i+1}+2i(1-p)^{n+i-1}(1-p)^{n+i-1}\\}$
(6.8)
$\displaystyle=\sum_{i=0}^{n}\binom{n}{i}2^{n-i}(1-p)^{2n+2i-1}\\{(n-i)(1-p)+\frac{2i}{1-p}\\}$
(6.9)
$\displaystyle=(1-p)^{2n}\sum_{i=0}^{n}\binom{n}{i}2^{n-1}(1-p)^{2i-1}\\{n(1-p)+i(\frac{2}{1-p}-(1-p))\\}$
(6.10)
$\displaystyle=n(1-p)^{2n}\sum_{i=0}^{n}\binom{n}{i}2^{n-i}(1-p)^{2i}+(1-p)^{2n-2}(2-(1-p)^{2})\sum_{i=0}^{n}\binom{n}{i}2^{n-i}(1-p)^{2i}i$
(6.11)
$\displaystyle=n(1-p)^{2n}(2+(1-p)^{2})^{n}+(1-p)^{2n-2}(1-(1-p)^{2})2^{n}n\frac{(1-p)^{2}}{2}(1+\frac{(1-p)^{2}}{2})^{n-1}$
(6.12)
$\displaystyle=n(1-p)^{2n}(2+(1-p)^{2})^{n}+n(2-(1-p)^{2})(2+(1-p)^{2})^{n-1}(1-p)^{2n}$
(6.13) $\displaystyle=4n(1-p)^{2n}(2+(1-p)^{2})^{n-1}$ (6.14)

and finally, from (6.5) and (6.14) one gets:

$\displaystyle Var[X(n)]$
$\displaystyle=(1-p)^{n}(3-p)^{n}-(1-p)^{2n}(2+(1-p)^{2})^{n}+4n(1-p)^{2n}(2+(1-p)^{2})^{n-1}$
(6.15)
$\displaystyle=\mu-\mu^{2}\frac{(2+(1-p)^{2})^{n}}{(3-p)^{2n}}+\mu^{2}\frac{4n(2+(1-p)^{2})^{n}}{(3-p)^{2n}}$
(6.16)

Now, since we have $Var[X(n)]$, we can use Chebyshev’s inequality to estimate
$g_{n}(p)$. Chebyshev’s inequality states that:

$\displaystyle 1-\textbf{P}[P_{3,p}^{n}\text{ contains an isolated
point}]=\textbf{P}[X(n)=0]\leq\textbf{P}[|X(n)-\mu|\geq\mu]\leq\frac{Var[X(n)]}{\mu^{2}}$
(6.17)

From 6.16 when $p<2-\sqrt{2}$, one gets $Var[X(n)]/\mu^{2}\rightarrow 0$, as
$n\rightarrow\infty$. Therefore, from (6.17) one gets
$\lim_{n\rightarrow\infty}\textbf{P}[P_{3,p}^{n}\text{ contains an isolated
point}]=1$. Finally, since

$\textbf{P}[P_{3,p}^{n}\text{ is connected}]\leq\textbf{P}[P_{3,p}^{n}\text{
does contains an isolated point}]$

, then for $p<2-\sqrt{2}$ the probability that $P_{3,p}^{n}$ is connected, as
$n\rightarrow\infty$, tends to $0$. $\blacksquare$

For $p>2-\sqrt{2}$:

In order to calculate $\textbf{P}[P_{3,p}^{n}\text{ contains an isolated
point}]$ when $p>2-\sqrt{2}$, as $n\rightarrow\infty$, one can use the
following inequality:

$\displaystyle\textbf{P}[P_{3,p}^{n}\text{ contains an isolated
point}]=\textbf{P}[X(n)>0]\leq E[X(n)]=\mu$ (6.18)

Since $E[X(n)]\rightarrow 0$ as $n\rightarrow\infty$, then
$\lim_{n\rightarrow\infty}\textbf{P}[P_{3,p}^{n}\text{ contains an isolated
point}]=0$. This means that the probability that there are no isolated points
in $P_{3,p}^{n}$ for $p>2-\sqrt{2}$, as $n\rightarrow\infty$, tends to $1$.
$\blacksquare$

###  6.2 Isolated components of size larger than 2 and smaller than $3^{n}$

######  Definition 31.

$C_{s}$ is the family of subsets of $V(P_{3}^{n})$ with size $s$ whose their
induced graph is connected.

######  Definition 32.

The edge boundary $b_{G}(H)$, where $H$ is an induced subgraph of G, is the
number of edges which joins vertices in $H$ to the vertices in $G\backslash
H$. Then $b_{G}(k)=min\\{b_{G}(H):H\subset G,|H|=k\\}$

######  Theorem 14.

If $p\geq 2-\sqrt{2}$, the probability that for some $S\in C_{s},2\leq s\leq
3^{0.44n}$, no edges of $P_{3,p}^{n}$ join $S$ to $V(P_{3}^{n})\setminus S$,
as $n\rightarrow\infty$, tends to 0.

Proof:
Consider $S\subset V=V(P_{3}^{n})$ and set $b(S)=b_{P_{3}^{n}}(H)$ where $H$
is the induced subgraph of $P_{3}^{n}$ with the set of vertices S. One can
observe that:

$\displaystyle\textbf{P}(\text{No edges of }P_{3,}^{n}\text{ join S to
}V\setminus S)=(1-p)^{b(S)}$ (6.19)

In order to prove the theorem, it is sufficient to show:

$\displaystyle\sum_{s=2}^{3^{0.44n}}\sum_{S\in C_{s}}(1-p)^{b(S)}=o(1)$ (6.20)

From [16] one knows that for $|S|=s$:

$\displaystyle b(S)\geq b(s)\geq\frac{e}{3}s\ln\frac{3^{n}}{s}=\frac{e\ln
3}{3}s(n-\log_{3}s)$ (6.21)

one knows that:

$\displaystyle\sum_{S\in C_{s}}(1-p)^{b(S)}\leq|C_{s}|(1-p)^{b(s)}$ (6.22)

First, one should find a bound for $|C_{s}|$. One has maximum $3^{n}$ choices
to choose the first element for $C_{s}$. The selected element is connected to
maximum $2n$ vertices, therefore, there are maximum $2n$ choices to choose the
second element. With the same logic, there are at most $2n(s-1)$ choices to
choose the last element for $|C_{s}|$. Hence, one can show:

$\displaystyle|C_{s}|\leq
3^{n}(2n)(2n(2))...(2n(s-1))\leq(s-1)!(2n)^{s-1}3^{n}$ (6.23)

and:

$\displaystyle|C_{s}|(1-p)^{b(s)}\leq(s-1)!(2n)^{s-1}3^{n}(1-p)^{\frac{e\ln
3}{3}s(n-\log_{3}s)}$ (6.24)

Set $a:=\frac{e\ln 3}{3}$. Assume that the right hand sides of inequality
(6.24) is equal to A. After multiplying both sides of inequality (6.24) with
$\frac{2ns^{s+1}}{s!}$ and then taking $\log_{3}$ from both sides, one gets:

$\displaystyle\log_{3}(|C_{s}|(1-p)^{b(s)}\frac{2ns^{s+1}}{s!})\leq\log_{3}(A\frac{2ns^{s+1}}{s!})$
(6.25)

If $\log_{3}(A\frac{2ns^{s+1}}{s!})\rightarrow-\infty$ as $n\rightarrow\infty$
then $A\frac{2ns^{s+1}}{s!}$ should tend to 0 for $2\leq s\leq 3^{0.44n}$.
This means that $|C_{s}|(1-p)^{b(s)}\frac{2ns^{s+1}}{s!}$ tends to 0 for
$2\leq s\leq 3^{0.44n}$, as $n\rightarrow\infty$. Therefore:

$\displaystyle|C_{s}|(1-p)^{b(s)}\leq\frac{s!}{2ns^{s+1}}\text{ for large
values of n}$ (6.26)

which shows that:

$\displaystyle\sum_{s=2}^{3^{0.44n}}\sum_{S\in C_{s}}(1-p)^{b(S)}=o(1)$ (6.27)

Finally, it remains to prove
$\log_{3}(A\frac{2ns^{s+1}}{s!})\rightarrow-\infty$ as $n\rightarrow\infty$.
One can verify this for $s\leq n$ and $s>n$. After multiplying both sides of
inequality (6.24) with $\frac{2ns^{s+1}}{s!}$ and then getting $\log_{3}$ from
both sides, one gets:

$\displaystyle\log_{3}(|C_{s}|(1-p)^{b(s)}\frac{2ns^{s+1}}{s!})\leq
s(\log_{3}2n+\log_{3}s+an\log_{3}(1-p)-a(\log_{3}s)\log_{3}(1-p))+n$ (6.28)

For $s\leq n$ the largest factor in equation (6.28) is
$n(a(\log_{3}(1-p))s+1)$ which is negative for $p=p_{c}$ and $2\leq s\leq n$.
Therefore, $\log_{3}(A\frac{2ns^{s+1}}{s!})\rightarrow-\infty$ as
$n\rightarrow\infty$ for $s\leq n$. For $s>n$ the largest factor in equation
(6.28) is $s(an(\log_{3}(1-p))+(\log_{3}s)(1-a\log_{3}(1-p))$ which is
negative if $s<3^{\frac{-a\log_{3}(1-p)}{1-a\log_{3}(1-p)}n}\approx
3^{0.44n}$. Therefore, $\log_{3}(A\frac{2ns^{s+1}}{s!})\rightarrow-\infty$ as
$n\rightarrow\infty$ for $s>n$. $\blacksquare$

For $p\geq 0.67$:

######  Theorem 15.

If $p\geq 0.67$, the probability that for some $S\in C_{s},2\leq s\leq 3^{n}$,
no edges of $P_{3,p}^{n}$ join $S$ to $V(P_{3}^{n})\setminus S$, as
$n\rightarrow\infty$, tends to 0. Hence, the probability that $P^{n}_{3,p}$ is
connected tends to $1$, as $n\rightarrow\infty$.

Proof:
We know that:

$\displaystyle|C_{s}|\leq\binom{3^{n}}{s}<(\frac{e3^{n}}{s})^{s}$ (6.29)

hence:

$\displaystyle|C_{s}|(1-p)^{b(s)}\leq\binom{3^{n}}{s}<(\frac{e3^{n}}{s})^{s}(1-p)^{\frac{e\ln
3}{3}s(n-\log_{3}s)}$ (6.30)

By using Mathematica 111Mathematica is a computational software program
developed by Wolfram Research of Champaign, Illinois one can show the right
hand side of equation (6.30) tends to zero as $n\rightarrow\infty$.
$\blacksquare$

##  Chapter 7 Reliable networks

In many engineering applications, it is of interest to construct a graph
(network), with a specific number of edges and vertices, which is the most
reliable one in that family of graph with n vertices and m edges. One of the
measures of reliability is all-terminal reliability.

###  7.1 All terminal reliability

######  Definition 33.

Random subgraph of a graph, Percolation on a graph: Random subgraph of
$G(V_{n},E_{m})$ is the graph $G_{p_{n}}$ which contains all vertices of $G$,
and each edge of $G$ independently with probability $p_{n}$. Doing percolation
on a graph with the parameter $p_{n}$ is the same as finding a random subgraph
of a graph with the parameter $p_{n}$. $p_{n}$ is called percolation
parameter.

######  Definition 34.

Uniformly optimally reliable graph (UOR): The UOR graph, if it exists, is the
graph $G_{n}\in G(n,m)$ which maximizes the probability that $G_{n}$ is
connected after percolation with the parameter $p_{n}$ for fixed $n,m$ and all
$p_{n}\in(0,1)$.

######  Definition 35.

Reliability polynomial: Let $s_{k}$ be the number of spanning connected
subgraphs of $G_{n}\in G(n,m)$ having exactly $k$ edges. Let $R(G_{n},p_{n})$
be the probability that $G_{n}$ is connected after percolation with the
parameter $p_{n}$. One can formulate $R(G_{n},p_{n})$ as follows:

$\displaystyle R(G_{n},p_{n}):=\sum_{i=0}^{m}s_{i}p_{n}^{i}(1-p_{n})^{m-i}$
(7.1)

$R(G_{n},p_{n})$ is called _reliability polynomial_ of graph $G_{n}$ or _all-
terminal reliability_. In this definition, $s_{i}=0$ for $i<n-1$ and
$s_{m}=1$. Also, $s_{m-1}$ is $m-$number of cuts in $G_{n}$, and $s_{n-1}$ is
the number of spanning tress of $G_{n}$.

The UOR graph, if it exists, is the graph $G_{n}\in G(n,m)$ which maximizes
$R(G_{n},p_{n})$ for all $p_{n}\in(0,1)$. From the definition of reliability
polynomial one can see that the value of reliability polynomial depends on the
structure of a graph as well as percolation value. Trivially, for fixed values
of $p_{n}$ there always exists an optimal solution for $R(G,p_{n})$. In other
words, for fixed values of $p_{n}$, there always exists a $G_{n}\in G(n,m)$
which maximizes $R(G_{n},p_{n})$. The following theorem and corollary can be
helpful to find the UOR graph. This theorem and corollary are extracted from
[17].

######  Theorem 16.

Let G and H be two undirected simple graphs both having n nodes and m edges
and $s_{k}(G),s_{k}(H)$ denote the number of spanning connected subgraphs of G
and H, respectively, with exactly k edges [17].

  1. 1.

If there exists an integer $0\leq k\leq m-1$ such that $s_{i}(G)=s_{i}(H)$ for
$i=0,1,...,k$ and $s_{k+1}(G)>s_{k+1}(H)$, then there exists a $\rho>0$ such
that for all $0<p<\rho$ we have $R(G,p)>R(H,p)$.

  2. 2.

If there exists an integer $0\leq k\leq m$ such that $s_{i}(G)=s_{i}(H)$ for
$i=m,m-1,...,m-k$ and $s_{m-k-1}(G)>s_{m-k-1}(H)$, then there exists a
$\rho<1$ such that for all $\rho<p<1$ we have $R(G,p)>R(H,p)$.

######  Corollary 3.

If G is UOR, then [17]:

  1. 1.

G has the maximum number of spanning trees among all simple graphs having n
nodes and m edges, and

  2. 2.

G is $max-\lambda$ , i.e. has the maximum possible value of $\lambda$ among
all simple graphs having n nodes and m edges, namely $\lambda(G)=\lfloor
2m/n\rfloor$, and the minimum number of cutsets of size $\lambda$ among all
such $max-\lambda$ graphs.

where $\lambda(G)$ is the edge connectivity of G, i.e., the minimum number of
edges whose its removal will disconnect $G$.

Important coefficients for large n: Let $n$ be large and $m$ sufficiently
larger than $n$. When $p_{n}$ is close to $0$ then $s_{n-1}$, the number of
spanning trees of $G_{n}$, has the most significant contribution in
$R(G_{n},p_{n})$ since $(1-p_{n})$ is almost $1$ and $p_{n}^{n-1}$ is much
larger than $p_{n}^{m}$. Similarly, when $p_{n}$ is close to $1$, then
$s_{m-1}$, $m-$number of cuts, has the most significant contribution in
$R(G_{n},p_{n})$.

#### Laplacian

The _Laplacian matrix_ of a graph is described briefly in chapter 1. Here, we
present a few results on Laplacian. The author calculated the algebraic
connectivity for all graphs with $n=5,6,7$ and $n-1<m<\binom{n}{2}$ and could
not find a direct relation between algebraic connectivity and all-terminal
reliability. There is a room for further work in this part.

The Laplacian matrix is $L:=(l_{i,j})_{n\times n}$ where
$l:=\left\\{\begin{array}[]{ll}deg(v_{i}),&\hbox{if $i=j$;}\\\ -1,&\hbox{if
$i\neq j$ and $v_{i}$ adjacent to $v_{j}$;}\\\ 0,&\hbox{o.w.}\\\
\end{array}\right.$. Arrange the eigenvalues of $L$ as :
$\lambda_{1}(L)\leq\lambda_{2}(L)\leq...\lambda_{n}(L)$. This set of
$\lambda_{i}$’s are called the spectrum of $L$ and $\lambda_{2}(L)$ is called
the algebraic connectivity of a graph. The following interesting lemma sheds
light on some applications of Laplacian matrix (this lemma is extracted from
[24]):

######  Lemma 5.

For a graph $G$ on $n$ vertices, we have [24]
(i):

$\sum_{i}\lambda_{i}\leq n$

with equality holding if and only if $G$ has no isolated vertices.
(ii): For $n\geq 2$

$\lambda_{1}\leq\frac{n}{n-1}$

with equality holding if and only if $G$ is the complete graph on $n$
vertices. Also, for a graph $G$ without isolated vertices, we have:

$\lambda_{n-1}\geq\frac{n}{n-1}.$

(iii:) For a graph which is not a complete graph, we have

$\lambda_{1}\leq 1.$

(iv:) If $G$ is connected, then $\lambda_{1}>0$. If $\lambda_{i}=0$ and
$\lambda_{i+1}\neq 0$, then $G$ has exactly $i+1$ connected components.
(v): For all $i\leq n-1$, we have:

$\lambda_{i}\leq 2$

with

$\lambda_{n-1}=2$

if and only of a connected component of $G$ is bipartite and nontrivial.
(vi:) The spectrum of a graph is the union of the spectrum of its connected
components.

#### Reliability for $n=5,6,7$

The author calculated $R(G,p)$ for $n=5,6,7$ and $n-1<m<\binom{n}{2}$. The
coefficients of the reliability polynomials are presented in tables 7.1, 7.2
and 7.3. As table 7.1 illustrates, for $n=5$ there is always a UOR graph. For
$n=6,7$ there are always a UOR graph except two cases. If, $(n,m)=(6,11)$, the
optimal solution for $R(G_{n},p)$ depends on the value of $p$. For $p<0.29$
(approximately 0.29) graph 7.1(a) is optimal while for $p>0.29$ graph 7.1(b)
optimal. Also, if $(n,m)=(7,15)$, the optimal solution for $R(G_{n},p)$
depends on the value of $p$. For $p<0.81$ (approximately 0.81) graph 7.2(a) is
optimal while for $p>0.81$ graph 7.2(b) is optimal. From these observation one
can conclude that the UOR does not exist for all values of $n$ and $m$.

n=5 | $s_{m-1}$ | $s_{m-2}$ | … | … | … | $s_{n-1}$
---|---|---|---|---|---|---
m=5 | 5 |  |  |  |  |
m=6 | 6 | 12 |  |  |  |
m=7 | 7 | 20 | 24 |  |  |
m=8 | 8 | 28 | 52 | 45 |  |
m=9 | 9 | 36 | 82 | 111 | 75 |
m=10 | 10 | 45 | 120 | 205 | 222 | 125

Table 7.1: The coefficients of the reliability polynomials of the UOR graph for $n=6$ and $n-1<m<\binom{n}{2}$. n=6 | $s_{m-1}$ | $s_{m-2}$ | … | … | … | … | … | … | … | $s_{n-1}$
---|---|---|---|---|---|---|---|---|---|---
m=6 | 6 |  |  |  |  |  |  |  |  |
m=7 | 7 | 16 |  |  |  |  |  |  |  |
m=8 | 8 | 26 | 36 |  |  |  |  |  |  |
m=9 | 9 | 36 | 78 | 81 |  |  |  |  |  |
m=10 | 10 | 45 | 116 | 177 | 135 |  |  |  |  |
_$m_{a}$ =11_ | 11 | 55 | 163 | 309 | 368 | 225 |  |  |  |
_$m_{b}$ =11_ | 11 | 55 | 163 | 310 | 370 | 224 |  |  |  |
m=12 | 12 | 66 | 220 | 489 | 744 | 740 | 384 |  |  |
m=13 | 13 | 78 | 286 | 771 | 1249 | 1552 | 1292 | 576 |  |
m=14 | 14 | 91 | 364 | 999 | 1978 | 2877 | 3040 | 2196 | 864 |
m=15 | 15 | 105 | 455 | 1365 | 2997 | 4945 | 6165 | 5700 | 3660 | 1296
Table 7.2: The coefficients of the reliability polynomials of the UOR graph for $n=6$ and $n-1<m<\binom{n}{2}$. For $m=11$, and $p<0.29$ (approximately 0.29) the row with $m_{a}$ is the UOR graph and for $p>0.29$ the row with $m_{b}$ is the UOR graph. n=7 | $s_{m-1}$ | $s_{m-2}$ | … | … | … | … | … | … | … | … | … | … | … | … | $s_{n-1}$
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
m=7 | 7 |  |  |  |  |  |  |  |  |  |  |  |  |  |
m=8 | 8 | 21 |  |  |  |  |  |  |  |  |  |  |  |  |
m=9 | 9 | 33 | 51 |  |  |  |  |  |  |  |  |  |  |  |
m=10 | 10 | 44 | 104 | 117 |  |  |  |  |  |  |  |  |  |  |
m=11 | 11 | 55 | 159 | 273 | 231 |  |  |  |  |  |  |  |  |  |
m=12 | 12 | 66 | 216 | 456 | 612 | 432 |  |  |  |  |  |  |  |  |
m=13 | 13 | 78 | 284 | 690 | 1146 | 1248 | 720 |  |  |  |  |  |  |  |
m=14 | 14 | 91 | 364 | 994 | 1932 | 2668 | 2460 | 1200 |  |  |  |  |  |  |
_$m_{a}$ =15_ | 15 | 105 | 455 | 1360 | 2946 | 4704 | 5464 | 4320 | 1840 |  |  |  |  |  |
_$m_{b}$ =15_ | 15 | 105 | 455 | 1360 | 2946 | 4705 | 5465 | 4305 | 1805 |  |  |  |  |  |
m=16 | 16 | 120 | 560 | 1817 | 4328 | 7766 | 10548 | 10628 | 7396 | 2800 |  |  |  |  |
m=17 | 17 | 136 | 680 | 2379 | 6169 | 1226 | 18762 | 22226 | 19808 | 12320 | 4200 |  |  |  |
m=18 | 18 | 153 | 816 | 3060 | 8562 | 18485 | 31344 | 41964 | 44000 | 35094 | 19716 | 6125 |  |  |
m=19 |  19 |  171 |  969 |  3876 |  11624 |  27073 |  49985 |  73888 |  87468 |  81976 |  58958 |  30109 |  8575 |  |
m=20 |  20 |  190 |  1140 |  4845 |  15502 |  38725 |  77240 |  124605 |  163400 |  173646 |  147500 |  96915 |  45530 |  12005 |
m=21 |  21 |  210 |  1330 |  5985 |  20349 |  54257 |  116175 |  202755 |  290745 |  343140 |  331506 |  258125 |  156555 |  68295 |  16807
Table 7.3: The coefficients of the reliability polynomials of the UOR graph
for $n=7$ and $n-1<m<\binom{n}{2}$. For $m=15$, and $p<0.81$ (approximately
0.81) the row with $m_{a}$ is the UOR graph and for $p>0.81$ the row with
$m_{b}$ is the UOR graph.

(a)

(b)

Figure 7.1: $(n,m)=(6,11)$, For $p<0.29$ (approximately 0.29) graph $(a)$ is
optimal while for $p>0.29$ graph $(b)$ is optimal.

(a)

(b)

Figure 7.2: $(n,m)=(7,15)$, For $p<0.81$ (approximately 0.81) graph $(a)$ is
optimal while for $p>0.81$ graph $(b)$ is optimal.

#### Reliability for $m=n-1,n,n+1,n+2,n+3$

For $m=n-1,n,n+1,n+2$ there always exists a UOR graph. For $m=n-1$, any tree
is the UOR graph. For $m=n$, $C_{n}$, single cycle with n vertices, is the UOR
graph. The first non-trivial case is $m=n+1$, which is solved by F. Boesch
[21], [20]. The UOR graph in this case is: for $n\geq 5$, start with a
multigraph with 2 vertices and 3 edges. Then add total of $n-2$ vertices of
degree 2 in each lines of the graph so that the number of vertices in each
line differs by at most one [20]. For $m=n+2$ the problem is also solved by F.
Boesch. The UOR graph in this case is: start with $K_{4}$, then add total of
$n-2$ vertices of degree 2 in each lines of the graph so that the number of
vertices in each line differs by at most one [20]. For $m=n+3$, the UOR graph
is found by G. Wang [22]. The UOR graph in this case is: start with $K_{3,3}$,
a complete bipartite graph with 3 vertices in each part, and then add the
remanning vertices as before.

#### Family of counterexamples

Kelmans [18] and Myrvold et al. [19] found infinite families of counter
examples which the UOR graph does not exist. As an example, for $n$ even and
$n\geq 6$ and $m=n(n-1)/2-(n+2)/2$, or for $n$ odd and $n\geq 7$ and
$m=n(n-1)/2-(n+5)/2$ there always exists a graph in which it maximizes
$R(G,p_{n})$ for $p$ close to $1$, but do not have the maximum number of
spanning trees. Therefore, from theorem 16 and corollary 3 the UOR graph does
not exists for these families.

###  7.2 Random accessibility

M. Ebneshahrashoob, T. Gao and M. Sobel introduced the concept of random
accessibility for simple graphs [23]. They believe that finding the UOR graph
is related to the concept of random accessibility. In random accessibility,
the goal is to find the expectation and the variance of the number of
transitions $X_{j}$ needed to visit $j$ new vertices in $G\in G(V_{n},E_{m})$.
In this approach the starting point is not considered as a new vertex. The
result of the expectation and the variance can depend on starting point.
Hence, one should change the starting point depending on the degree of it as a
weighing factor. If one considers a graph with enough symmetry, the result
does not depend on starting point. From analyzing numerical results, they make
the following interesting conjuncture:

  * •

If the family of graphs contains both regular and non-regular graphs, then the
UOR graph is among the regular graphs. Also, the expectation for random
accessibility of graphs is equal or greater than the corresponding result of
the UOR graph for each value of $j$ close to $m-1$ (with the same ordering of
the graph as for all-terminal reliability).

## References

  * [1] Bollobás, Bela, (2001), Random graphs. Springer.
  * [2] Bollobás, Bela, (2002), Modern Graph Theory. Cambridge University Press; 2nd edition.
  * [3] Diestel, Reinhard (2006), Graph Theory. Springer; 3rd edition.
  * [4] Erdös, Paul and Spencer, Joel, (1979), Evolution of the n-cube. Comp. $\&$ Maths. with Appls., Vol.5, pp. 33-39
  * [5] Hart, Sergiu (1976), A note on the edges of the n-cube. Discrete Mathematics, Vol.14, pp. 157-163
  * [6] Burtin, Yu. D. (1977), On the probability of connectedness of a random subgraph of the n-cube. Problemy Pered. Inf., 13, 90-95
  * [7] Spencer, Joel (1993), Nine lectures on random graphs. Springer Berlin / Heidelberg; Volume 1541/1993
  * [8] Spencer, Joel (1987), Ten Lectures on the Probabilistic Method. Society for Industrial Mathematics; Second edition
  * [9] Chai Wah Wu (2007), Synchronization in Complex Networks of Nonlinear Dynamical Systems. World Scientific Publishing Company
  * [10] L. Gross, Jonathan (2005), Graph Theory and Its Applications. Chapman and Hall/CRC; Second edition
  * [11] Alon, Noga and Spencer, Joel (2008), The probabilistics method. Wiley-Interscience; Third edition
  * [12] Matoušek, Jiřá and , Vondrák (2008), The probabilistics method. Lectures notes; Department of Applied Mathematics, Charles University
  * [13] Kolchin, V.F. (2009), Random graphs. Cambridge University Press; First edition
  * [14] Janson, Svante and Luczak, Tomasz and Rucinski, Andrzej (2000), Random graphs. Wiley-Interscience; First edition
  * [15] Clark, Lane (2002), Random subgraphs of cerain graph powers. IJMMS 32:5, 285 292
  * [16] Tillich, Jean-Pierre (2000), Edge isoperimetric inequalities for product graphs. Discrete Mathematics, V.213, Issue 1-3, 291-320
  * [17] Boesch, F T and Satyanarayana A. and Suffel, C.L. (2009), A survey of some network reliability analysis and synthesis results . Networks, V.54, Issue 2, 99-107
  * [18] Kelmans, A.K (1981), On graph with randomly deleted edges. Acta Math Acad Sci Hung, V.37, 77-88
  * [19] Myrvold, W and Cheung, L.Page and Perry J.E. (1991), Uniformly most reliable networks do not always exist. Networks, V.21, 417-419
  * [20] Boesch, F.T and Li, X. and Suffel, C. (1991), On the existence of uniformly optimally reliable networks. Networks, V.21, 181-194
  * [21] Bauer, D. and Boesch F, and Suffel, C. and Tindell, R. (1991), Combinatorial optimization problems in the analysis and design of probabilistic networks. Networks, V.15, 257-271
  * [22] Wang, G. (1994), A proof of Boesch’s conjecture. Networks, V.24, 277-284
  * [23] Ebneshahrashoob. Morteza and Gao, Tangan and Sobel, Milton (2005), Random Accessibility as a Parallelism to Reliability Studies on Simple Graphs. Communications in Statistics - Theory and Methods, V.34, 1423 - 1436
  * [24] Chung, Fan R. K. (1997), Spectral Graph Theory. American Mathematical Society