Entropy bounds for perfect matchings and Hamiltonian cycles
by
Bill Cuckler
University of Delaware
Coauthors: Jeffry Kahn, Rutgers University

For a graph G=(V, E) and x:E→ ℜ⁺ satisfying ∑_{e ∍ v}x_e = 1 for each v ∈ V, set h(x) = ∑_e x_elog(1/x_e) (with log = log₂). We show that for any n-vertex G, random (not necessarily uniform) perfect matching f satisfying a mild technical condition, and x_e=Pr(e ∈ f),

H(f) < h(x) - n 2 loge +o(n)

(where H is binary entropy). This implies a similar bound for random Hamiltonian cycles.

Specializing these bounds completes a proof of a quite precise determination of the numbers of perfect matchings and Hamiltonian cycles in Dirac graphs (graphs with minimum degree at least n/2) in terms of h(G): = max∑_e x_elog(1/x_e) (the maximum over x as above). For instance, for the number, Y(G), of Hamiltonian cycles in such a G, we have

Y(G) = exp2[2 h(G) -nloge -o(n)].

Date received: February 28, 2008