Hostname: page-component-586b7cd67f-rcrh6 Total loading time: 0 Render date: 2024-11-24T19:28:55.305Z Has data issue: false hasContentIssue false
  • English
  • Français

Turán theorems for unavoidable patterns

Part of: Graph theory Extremal combinatorics

Published online by Cambridge University Press:  26 April 2021

ANTÓNIO GIRÃO  and
BHARGAV NARAYANAN
ANTÓNIO GIRÃO
Affiliation:
School of Mathematics, University of Birmingham, Edgbaston, Birmingham, B15 2TT. Department of Mathematics, Rutgers University, Piscataway, NJ08854, U.S.A. e-mails: [email protected], [email protected]
BHARGAV NARAYANAN
Affiliation:
School of Mathematics, University of Birmingham, Edgbaston, Birmingham, B15 2TT. Department of Mathematics, Rutgers University, Piscataway, NJ08854, U.S.A. e-mails: [email protected], [email protected]
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

Primary: 05C35: Extremal problems
Secondary: 05D10: Ramsey theory
Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 172 , Issue 2 , March 2022 , pp. 423 - 442
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

References

Bowen, M., Lamaison, A. and Müyesser, N. A.. Finding unavoidable colourful patterns in multicolored graphs. Preprint, arXiv:1807.02780.Google Scholar
Caro, Y., Hansberg, A. and Montejano, A.. Unavoidable chromatic patterns in 2-colourings of the complete graph. Preprint, arXiv:1810.12375.Google Scholar
Conlon, D.. A new upper bound for diagonal Ramsey numbers. Ann. of Math. 170 (2009), 941–960.CrossRefGoogle Scholar
Cutler, J. and Montágh, B.. Unavoidable subgraphs of colored graphs., Discrete Math. 308 (2008), 4396–4413.CrossRefGoogle Scholar
Erdös, P.. Some remarks on the theory of graphs. Bull. Amer. Math. Soc. 53 (1947), 292–294.CrossRefGoogle Scholar
Erdös, P. and Moser, L.. On the representation of directed graphs as unions of orderings. Magyar Tud. Akad. Mat. Kutató Int. Közl. 9 (1964), 125–132.Google Scholar
Erdös, P. and Szekeres, G.. A combinatorial problem in geometry. Compositio Math. 2 (1935), 463–470.Google Scholar
Fox, J. and Sudakov, B.. Unavoidable patterns. J. Combin. Theory Ser. A 115 (2008), 1561–1569.CrossRefGoogle Scholar
Fox, J. and Sudakov, B.. Dependent random choice. Random Structures Algorithms 38 (2011), 68–99.CrossRefGoogle Scholar
Füredi, Z. and Simonovits, M.. The history of degenerate (bipartite) extremal graph problems. Erdös centennial, Bolyai Soc. Math. Stud., vol. 25 (János Bolyai Math. Soc., Budapest, 2013), pp. 169–264.CrossRefGoogle Scholar
Gishboliner, L.. Personal communication.Google Scholar
Graham, R. L., Rothschild, B. L. and Spencer, J. H.. Ramsey Theory, 2nd ed., Wiley-Interscience Series in Discrete Mathematics and Optimization (John Wiley & Sons, Inc., New York, 1990).Google Scholar
Kövari, T., Sós, V. T. and Turán, P.. On a problem of K. Zarankiewicz. Colloquium Math. 3 (1954), 50–57.CrossRefGoogle Scholar
Long, E.. Large unavoidable subtournaments. Combin. Probab. Comput. 26 (2017), 68–77.CrossRefGoogle Scholar
Ramsey, F. P.. On a problem of formal logic. Proc. London Math. Soc. 30 (1930), 264–286.CrossRefGoogle Scholar
Sterns, R.. The voting problem. Amer. Math. Monthly 66 (1959), 761–763.CrossRefGoogle Scholar
A. Thomason. An upper bound for some Ramsey numbers. J. Graph Theory 12 (1988), 509–517.CrossRefGoogle Scholar