Small complete minors above the extremal edge density (Q313429): Difference between revisions

For any graph \(G\), \(d(G)=\frac{| E(G)|}{| V(G)|}\); a \(K_t\)-minor consists of \(t\) vertex-disjoint connected subgraphs \(S_1\), \(\dots\), \(S_t\) and a set of \(t\choose 2\) paths \(\left\{P_{i,j}:1\leq i<j\leq t\right\}\), such that \(P_{i,j}\) connects \(S_i\) to \(S_j\), each path \(P_{i,j}\) is disjoint from all sets \(V\left(S_k\right)\) with \(k\neq i,j\), and the paths \(P_{i,j}\) are internally vertex disjoint. For \(S\subseteq V(G)\), \(N(S)\) is the set of vertices not in \(S\) adjacent to at least one vertex in \(S\). An \(m\)-vertex graph \(H\) is a \(\delta\)-expander if, for every integer \(k\) such that \(0\leq k\leq \log\log m-1\) and subset \(S\subseteq V(H)\) of order \(| S| \leq \frac m{2^{2^k}}\), \(| N(S)| \geq\frac{\delta 2^k}{\log m(\log\log m)^2}| S| \). The authors strengthen a result attributed to W.\ Mader in Lemma 1.2: If \(G\) satisfies \(d(G)=c\), then, for every \(0<\delta\leq\frac1{256}\) we can find in \(G\) a subgraph \(H\) such that \(d(H)\geq (1-\delta)c\) and \(H\) is a \(\delta\)-expander. This is applied in the main theorem to a problem of \textit{S. Fiorini} et al. [Eur. J. Comb. 33, No. 6, 1226--1245 (2012; Zbl 1242.05260)]: Theorem 1. For every \(\varepsilon>0\) and integer \(t\geq3\), there exists \(n_0=n_0(\varepsilon,t)\) such that every \(n\)-vertex graph \(G\) with \(n\geq n_0\) and \(d(G)\geq c(t)+\varepsilon\) contains a \(K_t\)-minor of order \({\text O}\left(\frac{c(t)t^2}{\varepsilon}\log n\log\log n\right)\).