Notes on random graphs from CS2304.

Introduction

G(n, p) Model [Erd ሷ𝑜s and R ƴ𝑒nyi1960]:

|V|=n is the number of vertices, and for and different $u ,v \in V$,$Pr({u, v} \in E)=p$

G actually denotes a probability space

• 𝑮(𝑛, 1/2)

$$\mu=n \mu'=E(K)=\frac{n}{2},$$ $$\sigma^{2}=n\left(\sigma'\right)^{2}=Var(K)=n / 4$$

(CLT) Near the mean, the binomial distribution is well approximated by the normal distribution.

$$\frac{1}{\sigma \sqrt{2 \pi}} e^{-\frac{(k-n \mu)^{2}}{2 \sigma^{2}}}=\frac{1}{\sqrt{\pi n / 2}} e^{-\frac{(k-n / 2)^{2}}{n / 2}}$$

Lemma.

• For all integers n , k with n ≥ k ≥ 2; the probability that $G \in G(n, p)$ has a set of k independent vertices is at most

  $$Pr(\alpha(G) \geq k) \leq\left(\begin{array}{l}n \\ k\end{array}\right)(1-p)^{\left(\begin{array}{l}k \\ 2\end{array}\right)}$$

• the probability that $G \in G(n, p)$ has a set of k clique is at most

$$Pr(\omega(G) \geq k) \leq\left(\begin{array}{l}n \\ k\end{array}\right)(p)^{\left(\begin{array}{l}k \\ 2\end{array}\right)}$$

• The expected number of k -cycles in $G \in G(n, p)$ is $E(x)=\frac{(n)_{k}}{2 k} p^{k}$ .

Properties of Almost All Graphs

• Definition: as , if the probability that a graph property appears in :

  • tends to 1: we say the property holds for almost all graphs
  • tends to 0: we say the property fails for almost all graphs

• Key theorems:

  1. Existence of induced subgraphs:
     For any constant and any graph , almost all contain an induced copy of .

     $$\Pr[\text{no induced } H] \leq (1 - r)^{\lfloor n/k \rfloor} \xrightarrow{n \to \infty} 0$$

  2. Adjacency property :
     For any disjoint vertex sets (), there exists a vertex such that:

     • is adjacent to every vertex in
     • is adjacent to no vertex in $$\Pr[\exists U,W \text{ with no suitable } v] \leq n^{i+j} (1 - p^iq^j)^{n-i-j} \xrightarrow{n \to \infty} 0$$

Chromatic Number

• Definition:

  • Vertex coloring: a map such that adjacent vertices receive different colors
  • Chromatic number : the minimum

• Lower bound: for any , almost all graphs satisfy:

  $$\chi(G) > \frac{\log(1/q)}{2+\epsilon} \cdot \frac{n}{\log n}$$

  Proof: use the upper bound on independent sets:

  $$\Pr(\alpha(G) \geq k) \leq \binom{n}{k} q^{\binom{k}{2}} \leq n^k q^{k(k-1)/2}$$

  Taking , the probability tends to 0.

Phase Transition

• Threshold definition: there exists a function such that:

  • when , almost surely does not have the property
  • when , almost surely has the property

• Phase transition table:
  | Probability | Structural property of the graph |
  |—————————————-|————————————————————————|
  | | A forest of trees, no connected component larger than |
  | | All connected components have size | | | Connected components have size | | | A giant component exists + small components of size |
  | | Diameter is 2 |
  | | Giant component + isolated vertices |
  | | Isolated vertices disappear; a Hamiltonian cycle appears; diameter |
  | | A clique of size exists |

Moment Methods

First Moment Method

• Markov’s inequality: for a non-negative random variable and : $$\Pr(X \geq a) \leq \frac{E[X]}{a}$$
• Application: $$\Pr(X > 0) \leq E[X]$$ If , the property almost surely does not occur.

Second Moment Method

• Theorem: if and , then almost surely:

  $$\Pr(X = 0) \leq \Pr(|X - E[X]| \geq E[X]) \leq \frac{\text{Var}(X)}{E^2[X]} \to 0$$

• Example application (the threshold for diameter 2):

  • Threshold point:
  • Define the indicator variables: $$I_{ij} = \begin{cases} 1 & \{i,j\} \notin E \text{ and no common neighbor} \\ 0 & \text{otherwise} \end{cases}$$
  • When :
    • : → diameter
    • : → diameter

Monotone Properties and the Existence of Thresholds

• Monotone property: adding edges never destroys the property (e.g. connectivity, no isolated vertices)
• Theorem: every monotone property has a threshold , where is the smallest real number satisfying: $$\Pr(G(n, p(n)) \text{ satisfies } Q) = \frac{1}{2}$$
• Key of the proof:
  • when : the -fold replication technique shows
  • when :

---

Translated from the Chinese original.