We propose a problem concerning the determination of the threshold function for the edge probability that guarantees, almost surely, the existence of various sparse spanning subgraphs in random graphs. We prove some bounds and demonstrate them in the cases of a d-cube and a two dimensional lattice.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics