3
$\begingroup$

Let $G$ be a random cubic graph on $n$ vertices. Let $M$ be the set of (not necessarily maximum) matchings of $G$. What is the expected size (i.e. number of edges) of an element of $M$?

In other words, what is the typical size of a matching in a typical cubic graph?

The Bethe lattice approximation gives the number $\frac{3}{10}n$, which coincides with experimental results. I'm wondering whether it is the true number.

$\endgroup$
4
$\begingroup$

This has been done before, but I can't find it. I'll outline how it can be proved, without dotting all the "$i$"s.

Consider the $d$-regular case, for $n$ vertices. The expected number of matchings with $K$ edges can be obtained by dividing two values from (for example) Thm 1 in this paper and multiplying by the number of positions that a matching can occupy. The result is a bit of a mess. However, if $E(K)$ is the expected number of matchings with $K$ edges, we find that, for constant $c\in(0,\frac12)$, $$\frac{E(cn+1)}{E(cn)} \to \frac{(1-2c)^2 d^2}{2 (d-2c)c}.$$ The maximum occurs when this ratio is 1, which is when $$ c = \frac{(2d+1-\sqrt{4d-3})\,d}{4(d^2+1)}, $$ which is indeed equal to $\frac3{10}$ when $d=3$.

To make this rigorous one needs to show that the mean is near this maximum point. It can be done by working harder on the values already calculated. It can also be done using the theory of the matchings polynomial: see this paper for the ideas.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.