Exploring Statistics Around Kahn-Kalai Conjecture by Using Parallel Algorithms

There are many questions about the statistical properties of random graphs, particularly those related to cyclic structures. However, theoretical advances have been made in the sparse connection regime. Recent results on the Kahn-Kalai conjecture show that there is a limiting connection probability beyond which it s very likely to find Hamiltonian cycles. It is shown that this probability is P ∼ log(n)/n where n is the number of nodes. We explore experimentally around this limit by showing its empirical statistical behavior. These results are useful in configuring various engineering problems based on sparse graphs. © 2022 IEEE.