Skip to main content
edited body
Source Link
Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147

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{(2c-1)^2 d^2}{2 (d-2c)c}.$$$$\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.

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{(2c-1)^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.

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.

Source Link
Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147

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{(2c-1)^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.