Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-26T12:40:06.906Z Has data issue: false hasContentIssue false
  • English
  • Français

The minimal density of triangles in tripartite graphs

Part of: Graph theory

Published online by Cambridge University Press:  01 August 2010

Rahil Baber ,
J. Robert Johnson  and
John Talbot
Rahil Baber
Affiliation:
Department of Mathematics, UCL, Gower Street, London WC1E 6BT, United Kingdom (email: [email protected])
J. Robert Johnson
Affiliation:
School of Mathematical Sciences, Queen Mary University of London E1 4NS, United Kingdom (email: [email protected])
John Talbot
Affiliation:
Department of Mathematics, UCL, Gower Street, London WC1E 6BT, United Kingdom (email: [email protected])

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 determine the minimal density of triangles in a tripartite graph with prescribed edge densities. This extends a previous result of Bondy, Shen, Thomassé and Thomassen characterizing those edge densities guaranteeing the existence of a triangle in a tripartite graph. To be precise we show that a suitably weighted copy of the graph formed by deleting a certain 9-cycle from K3,3,3 has minimal triangle density among all weighted tripartite graphs with prescribed edge densities.

Supplementary materials are available with this article.

MSC classification

Secondary: 05C35: Extremal problems
Type
Research Article
Information
LMS Journal of Computation and Mathematics , Volume 13 , January 2010 , pp. 388 - 413
Copyright
Copyright © London Mathematical Society 2010

References

[1] Bollobás, B., ‘Relations between sets of complete subgraphs’, Proceedings of the Fifth British Combinatorial Conference, Congressus Numerantium 15 (eds C. St. J. A. Nash-Williams and J. Sheehan; Utilitas Mathematica, Winnipeg, 1976) 79–84.Google Scholar
[2] Bondy, A., Shen, J., Thomassé, S. and Thomassen, C., ‘Density conditions for triangles in multipartite graphs’, Combinatorica 26 (2006) no. 2, 121–131.CrossRefGoogle Scholar
[3] Erdős, P., ‘On a theorem of Rademacher–Turán’, Illinois J. Math. 6 (1962) 122–127.CrossRefGoogle Scholar
[4] Fisher, D. C., ‘Lower bounds on the number of triangles in a graph’, J. Graph Theory 13 (1989) no. 4, 505–512.CrossRefGoogle Scholar
[5] Lovász, L. and Simonovits, M., ‘On the number of complete subgraphs of a graph, II’, Studies in pure mathematics (Birkhäuser, Basel, 1983) 459–495.CrossRefGoogle Scholar
[6] Mantel, V. W., ‘Problem 28’, Wiskundige Opgaven 10 (1907) 60–61.Google Scholar
[7] Razborov, A. A., ‘On the minimal density of triangles in graphs’, Combin. Probab. Comput. 17 (2008) no. 4, 603–618.CrossRefGoogle Scholar
Supplementary material: File

Baber Supplementary Material

Supplementary material.zip

Download Baber Supplementary Material(File)
File 7.6 KB