Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-26T17:08:57.416Z 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: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

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

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)