> [!NOTE] Theorem > Let $n,k$ be positive integers such that ${n \choose k }2^{1-{k \choose 2}}<1.$ Then $R(k,k)>n$ where $R(k,k)$ denotes a [[Ramsey Number on Two Colours|Ramsey number]]. ###### Proof: ![[Lower Bound for Diagonal Ramsey Numbers on Two Colours 2024-06-14 20.27.28.excalidraw]] Let $V$ be a finite set of $n$ elements. Let $G$ be a [[Random Graph Model with Edge Probability|random graph]] on $V$ with edge probability $p.$ Let $S\in {V \choose k}.$ Define the following events: - $E_C^S=\{H \mid H$ is a graph over the vertex set $V$ with the property that $H[S]$ is a clique. $\}$ - $E_I^S=\{H \mid H$ is a graph over $V$ with the property that $H[S]$ is an independent set $\}$. - $E^S=\{H \mid H$ is a graph over $V$ with the property that $H[S]$ is either an independent set or a clique$\}.$ We have $\mathbb{P}(E^{S}_{C})=\mathbb{P}(E_{I}^{S})=2^{-{k \choose 2}}.$ Subroof: Therefore, $\mathbb{P}(E^{S})=\mathbb{P}(E_{C}^{S})+\mathbb{P}(E_{I}^{S})=2^{1-{k \choose 2}}$ since $E_{C}^{S}$ and $E_{I}^{S}$ are mutually exclusive. Now by [[Probability of Union is Less than Sum of Probabilities (Boole's Inequality)|Boole's inequality]], $\mathbb{P}\left( \bigcup_{S\in {V \choose k}} E^{S} \right)\leq \sum_{S\in{V \choose k}} \mathbb{P}(E^{S})= {n \choose k }2^{1-{k \choose 2}}$that is, the probability that $G$ has an independent set of $k$ vertices or a $k$-clique is less than the LHS. Since ${n \choose k }2^{1-{k \choose 2}}<1$, we have $\mathbb{P}\left( \bigcup_{S\in {V \choose k}} E^{S} \right)<1$ which implies $\mathbb{P}\left( \Omega \setminus \bigcup_{S\in {V \choose k}} E^{S} \right)>0$that is, the probability that $G$ neither has an independent set of $k$ vertices nor a $k$-clique is strictly greater than $0.$ Then by [[Probabilistic Method]], there exists at least one graph with $n$-vertices which contains neither a $k$-clique or an independent set of $k$-vertices. Therefore, $R(k,k)>n.$ - [x] Complete ✅ 2024-06-14 # Applications [[Lower Bound for Diagonal Ramsey Numbers on Two Colours Where Row=Column is at Least 3]] asserts that ... # References - [[Week 10 Ramsey 2024.pdf]].