{"id":"arxiv/2606.24326","url":"https://arxiv.org/abs/2606.24326","tags":["math.CO","cs.DM"],"score":0,"title":"Obstructions for Minor-Closed Classes of limiting Densities Below 3/2","domain":"math.CO","source":"arxiv","authors":["Antonios Kominatos","Reem Mahmoud","Dimitrios M. Thilikos"],"reviews":0,"subject":"math.CO","summary":"Given a graph class $\\mathcal{G}$, the limiting density of $\\mathcal{G}$ is defined as $δ(\\mathcal{G})=\\lim_{n\\to\\infty} \\mathsf{ex}(\\mathcal{G},n)/n$ where $\\mathsf{ex}(\\mathcal{G},n)$ is the maximum number of edges of a graph in $\\mathcal{G}$ on $n$ vertices. The limiting density $δ(\\mathcal{G})$ is known to be a rational number when $\\mathcal{G}$ is a minor-closed graph class. For every $δ\\in[0,\\frac{3}{2})$, we prove that the set of $\\subseteq$-minimal minor-closed graph classes with densities $>δ$ is finite and we identify it completely. A consequence of our results is an algorithm…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-23","reactions":{}}