Densities of minor-closed graph families (Q612915)

Summary: We define the limiting density of a minor-closed family of simple graphs \(\mathcal F\) to be the smallest number \(k\) such that every \(n\)-vertex graph in \(\mathcal F\) has at most \(kn(1 + o(1))\) edges, and we investigate the set of numbers that can be limiting densities. This set of numbers is countable, well-ordered, and closed; its order type is at least \(\omega^{\omega}\). It is the closure of the set of densities of density-minimal graphs, graphs for which no minor has a greater ratio of edges to vertices. By analyzing density-minimal graphs of low densities, we find all limiting densities up to the first two cluster points of the set of limiting densities, 1 and 3/2. For multigraphs, the only possible limiting densities are the integers and the superparticular ratios \(i/(i + 1)\).