A lower bound on the average degree forcing a minor (Q2189420)

Summary: We show that for sufficiently large \(d\) and for \(t\geq d+1\), there is a graph \(G\) with average degree \((1-\varepsilon)\lambda t \sqrt{\ln d}\) such that almost every graph \(H\) with \(t\) vertices and average degree \(d\) is not a minor of \(G\), where \(\lambda=0.63817\dots\) is an explicitly defined constant. This generalises analogous results for complete graphs by \textit{A. Thomason} [J. Comb. Theory, Ser. B 81, No. 2, 318--338 (2001; Zbl 1024.05083)] and for general dense graphs by \textit{J. S. Myers} and \textit{A. Thomason} [Combinatorica 25, No. 6, 725--753 (2005; Zbl 1092.05064)]. It also shows that an upper bound for sparse graphs by \textit{B. Reed} and \textit{D. R. Wood} [Comb. Probab. Comput. 25, No. 2, 300--322 (2016; Zbl 1372.05211)] is best possible up to a constant factor.