Entropy bounds for perfect matchings and Hamiltonian cycles (Q624182): Difference between revisions

For a graph \(G = (V,E)\) and \( \boldsymbol{x}: E \to {\mathbb R}^+\) satisfying \(\sum_{e\ni v}x_e = 1\) for each \(v\in V,\) set \(h(x)= \sum_e x_e \log(1/x_e)\) (with \(\log = \log_2\)). We show that, for any \(n\)-vertex \(G\), a random (not necessarily uniform) perfect matching \(\boldsymbol{f}\) satisfying a mild technical condition, and \(x_e =Pr(e\in\boldsymbol{f}),\) \[ H(\boldsymbol{f})<h(\boldsymbol{x})-\frac{n}{2}\log e+o(n), \] where \(H\) is the binary entropy. This implies a similar bound for random Hamiltonian cycles. Specializing these bounds completes a proof, begun in [\textit{B. Cuckler} and \textit{J. Kahn}, Combinatorica 29, No.~3, 299--326 (2009; Zbl 1212.05146)], of a quite precise determination of the numbers of perfect matchings and Hamiltonian cycles in Dirac graphs (graphs with minimum degree at least \(\frac{n}{2}\)) in terms of \(h(G):=\max\sum_e x_e \log(1/x_e)\) (the maximum over \(\boldsymbol{x}\) as above). For instance, for the number \(\Psi(G)\) of Hamiltonian cycles in such a \(G\), we have \[ \Psi(G)=\exp_2[2h(G)-n\log e- o(n)]. \]