| 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? |