1
$\begingroup$

Does some function exist that takes a desired probability of a certain cycle existing in a random graph as input and outputs the extremal properties of a graph to achieve that probability?

For example, is there a way to answer a question of the form 'what is the smallest number of nodes/edges such that the probability that a random graph contains an Eulerian/Hamiltonian cycle is less than p'?

$\endgroup$
0
$\begingroup$

For the usual types of random graphs, the probability of existence of a Hamiltonian cycle will be essentially impossible to compute, however the expected number of Hamiltonian cycles is very easy: you just take the probability of a particular possibility being a cycle and multiply by the number of possible cycles. If the expected number of Hamiltonian cycles is less than $1$, that gives you an upper bound on the probability of there being a Hamiltonian cycle.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.