An explicit bound on the extremal function for complete graph minors
Kostochka and Thomason independently proved that every graph with density at least $β\,t\sqrt{\log t}$ has a $K_t$ minor, for some constant $β$. Thomason later proved that the least such density is $(0.319\ldots+o(1))\,t\sqrt{\log t}$. However, the $o(1)$ term in this formula is not explicit, so the formula gives no bound for any specific value of $t$. The goal of this paper is a bound of the form $β\,t\sqrt{\log t}$ that holds for every $t$, with $β$ small. We prove that, for every integer $t\geqslant2$, every graph with density at least $4.5\,t\sqrt{\log t}$ has a $K_t$ minor.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.41060
curl -X POST /api/v1/records/arxiv/2610.41060/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.41060/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'