Hostname: page-component-586b7cd67f-2plfb Total loading time: 0 Render date: 2024-11-25T22:33:11.574Z 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: [email protected])

Abstract

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.

Type
Research Article
Copyright
1997 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)