Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-16T13:23:36.761Z Has data issue: false hasContentIssue false

Turán theorems for unavoidable patterns

Published online by Cambridge University Press:  26 April 2021

ANTÓNIO GIRÃO
Affiliation:
School of Mathematics, University of Birmingham, Edgbaston, Birmingham, B15 2TT. Department of Mathematics, Rutgers University, Piscataway, NJ 08854, U.S.A. e-mails: tzgiraoa@gmail.com, narayanan@math.rutgers.edu
BHARGAV NARAYANAN
Affiliation:
School of Mathematics, University of Birmingham, Edgbaston, Birmingham, B15 2TT. Department of Mathematics, Rutgers University, Piscataway, NJ 08854, U.S.A. e-mails: tzgiraoa@gmail.com, narayanan@math.rutgers.edu
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 prove Turán-type theorems for two related Ramsey problems raised by Bollobás and by Fox and Sudakov. First, for t ≥ 3, we show that any two-colouring of the complete graph on n vertices that is δ-far from being monochromatic contains an unavoidable t-colouring when δ ≫ n−1/t, where an unavoidable t-colouring is any two-colouring of a clique of order 2t in which one colour forms either a clique of order t or two disjoint cliques of order t. Next, for t ≥ 3, we show that any tournament on n vertices that is δ-far from being transitive contains an unavoidable t-tournament when δ ≫ n−1/[t/2], where an unavoidable t-tournament is the blow-up of a cyclic triangle obtained by replacing each vertex of the triangle by a transitive tournament of order t. Conditional on a well-known conjecture about bipartite Turán numbers, both our results are sharp up to implied constants and hence determine the order of magnitude of the corresponding off-diagonal Ramsey numbers.

MSC classification

Information

Type
Research Article
Creative Commons
Creative Common License - CCCreative Common License - BY
This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.
Copyright
© The Author(s), 2021. Published by Cambridge University Press on behalf of Cambridge Philosophical Society