Expected Crossing Numbers
The expected value for the weighted crossing number of a randomly weighted graph is
studied. We focus on the case where G= K n and the edge-weights are independent random
variables that are uniformly distributed on [0, 1]. The first non-trivial case is K 5. We compute
this via an unexpectedly involved calculation, and consider bounds for larger values of n. A
variation of the Crossing Lemma for expectations is proved.
studied. We focus on the case where G= K n and the edge-weights are independent random
variables that are uniformly distributed on [0, 1]. The first non-trivial case is K 5. We compute
this via an unexpectedly involved calculation, and consider bounds for larger values of n. A
variation of the Crossing Lemma for expectations is proved.
Abstract
The expected value for the weighted crossing number of a randomly weighted graph is studied. We focus on the case where G = K n and the edge-weights are independent random variables that are uniformly distributed on [0,1]. The first non-trivial case is K 5. We compute this via an unexpectedly involved calculation, and consider bounds for larger values of n. A variation of the Crossing Lemma for expectations is proved.
Springer