On unavoidable graphs (Q595677): Difference between revisions

A graph \(G\) is called an \((n,e)\)-unavoidable graph if every graph on \(n\) vertices and \(e\) edges contains \(G\) as a subgraph. Let \(f(n,e)\) denote the largest integer \(m\) with the property that there exists an \((n,e)\)-unavoidable graph on \(m\) edges. In this paper the authors obtain bounds on \(f(n,e)\) which are in many cases asymptotically best possible.