Menu
This paper addresses the following questions. In any graph \(G\) with at least \(\alpha\binom{n}{2}\) edges, how large of an induced subgraph \(H\) can we guarantee the existence of with minimum degree \(\delta(H) \geq \lfloor\alpha|V(H)|\rfloor\)? In any graph \(G\) with at least \(\alpha\binom{n}{2} – f(n)\) edges, where \(f(n)\) is an increasing function of \(n\), how large of an induced subgraph \(H\) can we guarantee the existence of containing at least \(\alpha\binom{|V(H)|}{2}\) edges? In any graph \(G\) with at least \(\alpha n^2\) edges, how large of an induced subgraph \(H\) can we guarantee the existence of with at least \(\alpha|V(H)|^2 + \Omega(n)\) edges? For \(\alpha = 1 – \frac{1}{r}\), for \(r = 2, 3, \ldots\), the answer is zero since if \(G\) is a complete \(r\)-partite graph, no subgraph \(H\) of \(G\) has more than \(\alpha|V(H)|^2\) edges. However, we show that for all admissible \(\alpha\) except these, the answer is \(\Omega(n)\). In any graph \(G\) with minimum degree \(\delta(G) \geq \alpha n – f(n)\), where \(f(n) = o(n)\), how large of an induced subgraph \(H\) can we guarantee the existence of with minimum degree \(\delta(H) \geq \Omega|V(H)|\)?