Title: Theory / Unimportant / CS / Fundamental / Graph / Bondy - Murty / 13 Probabilistic
Tags: examplesSwitchExample1 hasSeenConjDef

Name: A finite probability space
Definition: A finite set \(\Omega\)
Page: 330
Chapter: 12
Section: 1
Definition2: \(P:\Omega\to[0,1]\) with \(\sum_{\omega\in \Omega} P(\omega)=1\)
Conjdef: A pair
Denoted by: \((\Omega,P)\)

Name: A random graph of order \(n\),
Definition: Any graph of \(\mathcal G_n\) with probability \(2^{-{n \choose 2}}\)
Page: 330
Chapter: 12
Section: 1
Variables: \(n\in\mathbb N\)
Intuition: Takes \(n\) vertices.
Choose each edge with probability 1/2

Name: The set of random graph of order \(n\), with probability \(p\)
Definition: belonging \(\mathcal G_n\)
Page: 330
Chapter: 12
Section: 1
Variables: \(n\in\mathbb N\)
\(p\in [0,1]\)
Notation: \(\mathcal G_{n,p}\)
Definition2: with probability \(p^{e(G)}(1-p)^{N-e(G)}\)
Conjdef: The set of graph \(G\)
Intuition: Takes \(n\) vertices.
Choose each edge with probability \(p\)

Smaller0: \(p<p'\)
Greater0: higher in \(\mathcal G_{n,p}\) than in \(\mathcal G_{n,p'}\)
Page: 330
Chapter: 12
Section: 1
Variables: \(n\in\mathbb N\)
\(p,p'\in [0,1]\)
Prefix Greater: the probability of having a sparse graph is

Name: An event
Definition: A subset of \(\Omega\)
Page: 330
Chapter: 12
Section: 1
Variables: \((\Omega,P)\)
Denoted by: \(A\)

Name: The probability of \(A\)
Definition: \(\sum_{\omega\in A}P(\omega)\)
Page: 330
Chapter: 12
Section: 1
Variables: \((\Omega,P)\),
\(A\subseteq \Omega\)