Hostname: page-component-745bb68f8f-mzp66 Total loading time: 0 Render date: 2025-02-06T13:43:35.384Z Has data issue: false hasContentIssue false
  • English
  • Français

Triangle-Free Subgraphs of Random Graphs

Part of: Graph theory

Published online by Cambridge University Press:  14 August 2017

PETER ALLEN ,
JULIA BÖTTCHER ,
YOSHIHARU KOHAYAKAWA  and
BARNABY ROBERTS
PETER ALLEN
Affiliation:
Department of Mathematics, The London School of Economics and Political Science, Houghton Street, London WC2A 2AE, UK (e-mail: p.d.allen@lse.ac.uk, j.boettcher@lse.ac.uk, b.j.roberts@lse.ac.uk)
JULIA BÖTTCHER
Affiliation:
Department of Mathematics, The London School of Economics and Political Science, Houghton Street, London WC2A 2AE, UK (e-mail: p.d.allen@lse.ac.uk, j.boettcher@lse.ac.uk, b.j.roberts@lse.ac.uk)
YOSHIHARU KOHAYAKAWA
Affiliation:
Instituto de Matemática e Estatística, Universidade de São Paulo, Rua do Matão 1010, 05508–090 São Paulo, Brazil (e-mail: yoshi@ime.usp.br)
BARNABY ROBERTS
Affiliation:
Department of Mathematics, The London School of Economics and Political Science, Houghton Street, London WC2A 2AE, UK (e-mail: p.d.allen@lse.ac.uk, j.boettcher@lse.ac.uk, b.j.roberts@lse.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.

Recently there has been much interest in studying random graph analogues of well-known classical results in extremal graph theory. Here we follow this trend and investigate the structure of triangle-free subgraphs of G(n, p) with high minimum degree. We prove that asymptotically almost surely each triangle-free spanning subgraph of G(n, p) with minimum degree at least (2/5 + o(1))pn is (p−1n)-close to bipartite, and each spanning triangle-free subgraph of G(n, p) with minimum degree at least (1/3 + ϵ)pn is O(p−1n)-close to r-partite for some r = r(ϵ). These are random graph analogues of a result by Andrásfai, Erdős and Sós (Discrete Math.8 (1974), 205–218), and a result by Thomassen (Combinatorica22 (2002), 591–596). We also show that our results are best possible up to a constant factor.

MSC classification

Primary: 05C35: Extremal problems
Secondary: 05C80: Random graphs
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 27 , Issue 2 , March 2018 , pp. 141 - 161
Copyright
Copyright © Cambridge University Press 2017 

References

[1] Allen, P., Böttcher, J., Ehrenmüller, J. and Taraz, A. (2016) The Bandwidth Theorem in sparse graphs. arXiv:1612.00661 Google Scholar
[2] Allen, P., Böttcher, J., Griffiths, S., Kohayakawa, Y. and Morris, R. (2013) The chromatic thresholds of graphs. Adv. Math. 235 261–295.Google Scholar
[3] Allen, P., Böttcher, J., Hàn, H., Kohayakawa, Y. and Person, Y. (2016) Blow-up lemmas for sparse graphs. arXiv:1612.00622 Google Scholar
[4] Andrásfai, B., Erdős, P. and Sós, V. T. (1974) On the connection between chromatic number, maximal clique and minimal degree of a graph. Discrete Math. 8 205–218.Google Scholar
[5] Balogh, J., Morris, R. and Samotij, W. (2015) Independent sets in hypergraphs. J. Amer. Math. Soc. 28 669–709.Google Scholar
[6] Descartes, B. (1947) A three-colour problem. Eureka 9 (April 1947) 21. Solution March 1948.Google Scholar
[7] Brandt, S. and Thomassé, S. Dense triangle-free graphs are four colorable: A solution to the Erdős-Simonovits problem. J. Combin. Theory Ser. B, to appear.Google Scholar
[8] Conlon, D. (2014) Combinatorial theorems relative to a random set. In Proceedings of the International Congress of Mathematicians. 4 303–328.Google Scholar
[9] Conlon, D., Gowers, W. T., Samotij, W. and Schacht, M. (2014) On the KLR conjecture in random graphs. Israel J. Math. 203 535–580.Google Scholar
[10] DeMarco, B. and Kahn, J. (2015) Mantel's theorem for random graphs. Random Struct. Alg. 47 59–72.CrossRefGoogle Scholar
[11] Erdős, P. and Simonovits, M. (1973) On a valence problem in extremal graph theory. Discrete Math. 5 323–334.CrossRefGoogle Scholar
[12] Janson, S., Łuczak, T. and Ruciński, A. (2000) Random Graphs, Wiley-Interscience.CrossRefGoogle Scholar
[13] Kohayakawa, Y. (1997) Szemerédi's regularity lemma for sparse graphs. In Foundations of Computational Mathematics (Cucker, F. and Shub, M., eds), Springer, pp. 216–230.CrossRefGoogle Scholar
[14] Kohayakawa, Y., Łuczak, T. and Rödl, V. (1997) On K4-free subgraphs of random graphs. Combinatorica 17 173–213.Google Scholar
[15] Kohayakawa, Y., Rödl, V., Schacht, M. and Szemerédi, E. (2011) Sparse partition universal graphs for graphs of bounded degree. Adv. Math. 226 5041–5065.Google Scholar
[16] Lyle, J. (2011) On the chromatic number of H-free graphs of large minimum degree. Graphs Combin. 27 741–754.Google Scholar
[17] Mantel, W. (1907) Problem 28. Wiskundige Opgaven 10 60–61 (solution by Gouwentak, H., Mantel, W., de Mattes, J. Texeira, Schuh, F. and Wythoff, W. A.).Google Scholar
[18] Saxton, D. and Thomason, A. (2015) Hypergraph containers. Invent. Math. 201 925–992.Google Scholar
[19] Thomassen, C. (2002) On the chromatic number of triangle-free graphs of large minimum degree. Combinatorica 22 591–596.Google Scholar