Asymptotic Density of Graphs Excluding Disconnected Minors

Abstract

For a graph $H$, let $$c_{\infty }(H)=\underset{n\to \infty }{\lim }\max \frac{|E(G)|}{n},$$ where the maximum is taken over all graphs $G$ on $n$ vertices not containing $H$ as a minor. Thus $c_{\infty }(H)$ is the asymptotic maximum density of graphs not containing $H$ as a minor. Employing a structural lemma due to Eppstein, we prove new upper bounds on $c_{\infty }(H)$ for disconnected graphs $H$. In particular, we determine $c_{\infty }(H)$ whenever $H$ is union of cycles. Finally, we investigate the behaviour of $c_{\infty }(s{K}_r)$ for fixed $r$, where $s{K}_r$ denotes the union of $s$ disjoint copies of the complete graph on $r$ vertices. Improving on a result of Thomason, we show that $$c_{\infty }(s{K}_r)=s(r-1)-1\mathrm{for}s=\Omega \left(\frac{\log r}{\log \log r}\right),$$ and $$c_{\infty }(s{K}_r)>s(r-1)-1\mathrm{for}s=o\left(\frac{\log r}{\log \log r}\right).$$