Hostname: page-component-74656f9884-j7cmm Total loading time: 0 Render date: 2026-11-07T20:12:49.118Z Has data issue: false hasContentIssue false

Triangle Factors in Random Graphs

Published online by Cambridge University Press:  01 September 1997

MICHAEL KRIVELEVICH
Affiliation:
Department of Mathematics, Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 69978, Israel (e-mail: krivelev@math.tau.ac.il)
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.

For a graph G=(V, E) on n vertices, where 3 divides n, a triangle factor is a subgraph of G, consisting of n/3 vertex disjoint triangles (complete graphs on three vertices). We discuss the problem of determining the minimal probability p=p(n), for which a random graph G∈[Gscr](n, p) contains almost surely a triangle factor. This problem (in a more general setting) has been studied by Alon and Yuster and by Ruciński, their approach implies p=O((log n/n)1/2). Our main result is that p=O(n)−3/5) already suffices. The proof is based on a multiple use of the Janson inequality. Our approach can be extended to improve known results about the threshold for the existence of an H-factor in [Gscr](n, p) for various graphs H.

Information

Type
Research Article
Copyright
1997 Cambridge University Press