The toughness of random graphs

Source abstract

For a connected and non-complete graph $G$ of order $n$, its toughness is defined as $$τ(G)=\min\bigl\{|S|/c(G-S):S\subseteq V(G),\ c(G-S)>1\bigr\},$$ where $c(G-S)$ denotes the number of components of $G-S$. Let $α(G)$ denote the independence number of $G$. An elementary bound on toughness is $$τ(G)\leq\frac{n-α(G)}{α(G)}.$$ Let $G(n,p)$ be the binomial random graph on vertex set $[n]$. Set $a=α(G(n,p))$. In this paper, we prove that $$τ(G(n,p))=\frac{n-a}{a}+o(1)$$ with high probability. Moreover, we show that there is a sequence $n_m\to\infty$ such that with high probability, $$τ(G(n_{m},p)) \le\frac{n_{m}-a}a-\frac{1}{a}.$$