2 ms·
Maybe someone familiar with the graph theory math can help me. I don't understand why these properties aren't numerically accessible. Why is the estimation nec
by sharpener 4y ago
Maybe someone familiar with the graph theory math can help me.
I don't understand why these properties aren't numerically accessible. Why is the estimation necessary?
E.g. Assume N nodes, and edges E can be created at random with redundancy (picking same edge e twice just keeps the prior edge) by picking pairs of points.
Assume N random edge picks are made, then the probability of e.g. a Hamiltonian cycle appearing in those N picks can be calculated.
(My quick back of envelope sketch says P(H-cycle) = N! / N^N , but please consult the expert literature.)
But one can also calculate the probability of a H-cycle given N+1 random picks, N+2 random picks, ... and that appears as
= P(H-cycle) * (1 + extra factors that account for increases in other edges not redundantly in the H-cycle)
(Again, my back of envelope sketch for N + 2 picks gives:
= P(H-cycle) * ( 1 + 2/(N-1)[N - 3 - 1/N]) , but please consult the expert literature.)
These probabilities would seem to tell a user that given a graph with N nodes and E edges, that if e.g. in the H-cycle case, E > N the user can get an explicit probability for the likelihood of a H-cycle being present.
Are there graph properties that prevent this approach being viable?