Complete minors and average degree: A short proof

DOI10.1002/JGT.22937MaRDI QIDQ6074598zbMATH OpenFDO

Authors Noga Alon, Michael Krivelevich, Benny Sudakov

Publication date 12 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2202.08530

zbMATH Keywords

clique minorsprobabilistic methods

Mathematics Subject Classification ID

Graph minors (05C83) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: We provide a short and self-contained proof of the classical result of Kostochka and of Thomason, ensuring that every graph of average degree $d$ has a complete minor of order $d/sqrtlogd$.

Recommendations

• A lower bound on the average degree forcing a minor
• Small minors in dense graphs
• Logarithmically small minors and topological minors
• Forcing unbalanced complete bipartite minors
• On \(K_{s,t}\)-minors in graphs with given average degree

Cites work

• An extremal function for contractions of graphs
• Homomorphiesätze für Graphen
• scientific article; zbMATH DE number 3865318 (Why is no real title available?)
• Lower bound of the Hadwiger number of graphs by their average degree
• The extremal function for complete minors

Cited in

(8)

• A lower bound on the average degree forcing a minor
• Average degree conditions forcing a minor
• Small minors in dense graphs
• Logarithmically small minors and topological minors
• Large complete minors in random subgraphs
• Minors in small-set expanders
• Minors, connectivity, and diameter in randomly perturbed sparse graphs
• Extremal eigenvalues with respect to graph minors

This page was built for publication: Complete minors and average degree: A short proof

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6074598)