Covering a random graph with triangles
Search
Subjects
- All (170)
- Ramsey Theory (40)
- Extremal Graph Theory (40)
- Coloring, Packing, and Covering (25)
- Random Graphs and Graph Enumeration (16)
- Hypergraphs (35)
- Infinite Graphs (14)
About Erdös
About This Site
Problem
(proposed by Erdös and Spencer)
Start with \(n\) vertices and add edges at random one at a time. If we stop when
every vertex is contained in a triangle, is there almost surely a set
of vertex disjoint triangles covering every vertex (except for
at most two vertices)?
The above question can be posed for other configurations as well \( ^{[3]}\). In particular, Bollobás and Frieze \( ^{[1]}\) showed that by stopping as soon as there is no isolated vertex, then there already almost surely is a perfect matching if the number of vertices is even. Also, if we stop when every vertex has degree at least \( 2\), Ajtai, Komlós and Szemerédi \( ^{[4]}\), and Bollobás \( ^{[2]}\), proved that there already almost surely is a Hamiltonian cycle. Alon and Yuster \( ^{[5]}\) and Rucinski \( ^{[6]}\) examined the threshold function of a random graph on \( n\) vertices for the existence of \( \lfloor n/\vert V(H)\vert \rfloor\) vertex-disjoint copies of a given graph \( H\). Krivelevich \( ^{[7]}\) proved that for \( p=O(n^{-3/5})\), the random graph \( G_{n,p}\) almost surely contains \( \lfloor n /3 \rfloor\) vertex-disjoint triangles. He conjectured that \( p=O(n^{-2/3} \log ^{1/3} n)\) is already enough for \( G_{n,p}\) to have a triangle factor.
Bibliography | |
---|---|
1 | B. Bollobás and A. M. Frieze, On matchings and Hamiltonian cycles in random graphs, Random graphs '83 , 23-46, North-Holland Math. Stud., 118, North-Holland, Amsterdam-New York, 1985. |
2 | B. Bollobás, The evolution of sparse graphs, Graph theory and Combinatorics (Cambridge, 1983), 35-57, Academic Press, London-New York, 1984. |
3 | N. Alon, J. H. Spencer and P. Erdös, The Probabilistic Method, Wiley and Sons, New York, 1992. (Link To sample sections.) |
4 | M. Ajtai, J. Komlós and E. Szemerédi, First occurrence of Hamilton cycles in random graphs, Cycles in graphs (Burnaby, B. C., 1982), 173-178, North-Holland Math. Stud., 115, North-Holland, Amsterdam-New York, 1985. |
5 | N. Alon and R. Yuster, Threshold functions for \( H\)-factors, Combinatorics, Prob. and Computing 2 (1993), 137-144. |
6 | A. Rucinski, Matching and covering the vertices of a random graph by copies of a given graph, Discrete Math. 105 (1992), 185-197. |
7 | M. Krivelevich,Triangle factors in random graphs,
Comb. Prob. Computing(1997), 337-348.
|