Skip to content
DraconiticResearch
Search Sources API
201,683 studies31 sourcesUpdated 53 min ago
PreprintCC BY-NC-ND 4.0arXiv

An explicit bound on the extremal function for complete graph minors

  • David R. Wood
Open at sourcePDFDOICite

Abstract

Kostochka and Thomason independently proved that every graph with density at least β t√(log t) has a Kt minor, for some constant β. Thomason later proved that the least such density is (0.319…+o(1)) t√(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√(log t) that holds for every t, with β small. We prove that, for every integer tgeqslant2, every graph with density at least 4.5 t√(log t) has a Kt minor.

Related

  1. Extremal function for rooted K5 minors
    Zdeněk Dvořák
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. Guaranteed indirect delivery in directed networks: The joint extremal function and explicit attaining constructions
    Angel Ivanov Raychev
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. Plotkin-Like Bound and Explicit Function-Correcting Code Constructions for Lee Metric Channels
    K. Hareesh, Rashid Ummer N. T., Balaji Sundar Rajan
    IEEE Transactions on Information TheoryPeer-reviewedLicence not statedFull text10 citedCombinatorics & discrete mathematicsOpenAlex
  4. Large Complete Minors from a Cheeger Condition
    Chengli Li, Leyou Xu, Bo Zhou
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. The complete spectrum of the linearized p-Laplacian at a Sobolev extremal
    Yitian Zhang
    arXivPreprintarXiv licenceFull textAnalysis & PDEsarXiv

Cite

BibTeXRIS
BibTeX
@misc{wood2026explicit,
  title = {{An explicit bound on the extremal function for complete graph minors}},
  author = {David R. Wood},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.41060},
  eprint = {2610.41060},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.41060},
  note = {CC BY-NC-ND 4.0},
}
RIS
TY  - UNPB
TI  - An explicit bound on the extremal function for complete graph minors
AU  - David R. Wood
PY  - 2026
DA  - 2026/10/29
PB  - arXiv
DO  - 10.48550/arxiv.2610.41060
UR  - https://arxiv.org/abs/2610.41060
AB  - Kostochka and Thomason independently proved that every graph with density at least β t√(log t) has a K_t minor, for some constant β. Thomason later proved that the least such density is (0.319…+o(1)) t√(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√(log t) that holds for every t, with β small. We prove that, for every integer tgeqslant2, every graph with density at least 4.5 t√(log t) has a K_t minor.
ER  -