Hostname: page-component-74656f9884-npj9w Total loading time: 0 Render date: 2026-11-09T03:57:41.218Z Has data issue: false hasContentIssue false
  • English
  • Français

Graphs without Large Complete Minors are Quasi-Random

Published online by Cambridge University Press:  21 November 2002

JOSEPH SAMUEL MYERS
JOSEPH SAMUEL MYERS
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, Centre for Mathematical Sciences, Wilberforce Road, Cambridge CB3 0WB, England (e-mail: J.S.Myers@dpmms.cam.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We answer a question of Sós by showing that, if a graph G of order n and density p has no complete minor larger than would be found in a random graph G(n, p), then G is quasi-random, provided either p > 0.45631 … or κ(G) [ges ] n(log log log n)/(log log n), where 0.45631 … is an explicit constant.

The results proved can also be used to fill the gaps in an argument of Thomason, describing the extremal graphs having no Kt minor for given t.

Information

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 11 , Issue 6 , November 2002 , pp. 571 - 585
Copyright
2002 Cambridge University Press