# Pair matching between divisors less and more than $\sqrt{N}$

Let $$n$$ be the positive integer. Let $$A$$ and $$B$$ be sets of divisors of $$n$$ less and more than $$\sqrt{n}$$ respectively.

Consider bipartite graph $$(A, B)$$, where two vertices are connected when one divides another. Denote $$M(n)$$ number of perfect matchings in this graph.

Is $$M(n) > 0$$ for all $$n$$(maybe excluding squares)?

Is there some formula for $$M(n)$$ or maybe an estimate?

• For $1 \le n \le 100$ I get this sequence for $M(n)$: 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 4, 1, 1, 1, 2, 1, 4, 1, 1, 1, 1, 1, 14, 1, 1, 2, 1, 1, 11, 1, 6, 1, 1, 1, 8, 1, 1, 1, 14, 1, 1, 1, 1, 4, 1, 1, 36, 1, 4, 1, 1, 1, 4, 1, 14, 1, 1, 1, 74, 1, 1, 4, 6, 1, 1, 1, 1, 1, 11, 1, 72, 1, 1, 4, 1, 1, 1, 1, 46, 2, 1, 1, 74, 1, 1, 1, 1, 1, 74, 1, 1, 1, 1, 1, 252, 1, 4, 1, 8. Not in OEIS. Aug 3, 2023 at 10:29
• The values of $n$ with $M(n)>1$ seem to form oeis.org/A063539. It is easy to see that the numbers NOT in A063539 have $M(n)=1$. Aug 3, 2023 at 13:44

Here is a proof that $$M(n)>0$$.
Denote $$[\alpha]=\{0,1,\dots,\alpha\}$$. All divisors of $$n$$ correspond, in a natural way, to the points in a parallelepiped $$P=[\alpha_1]\times\dots\times [\alpha_k]$$. For $$a=(a_i), b=(b_i)\in P$$ we write $$a\leq b$$ if $$a_i\leq b_i$$ for all $$i$$. Let $$S$$ and $$L$$ denote the sets of points corresponding to small ($$<\sqrt n$$) and large divisors, respectively. We implement the Hall lemma to show a perfect matching between $$S$$ and $$L$$ exists.
Say that a subset $$A\subseteq P$$ is downward-closed if for any $$a\in A$$ and $$b\leq a$$ we have $$b\in A$$. We use the following version of a well-known lemma by Kleitman; it is also a special case of the FKG Inequality, or, specifically, of the Harris inequality, see here.
Lemma. For any two downward-closed subsets $$A,B\in P$$ we have $$|A|\cdot |B|\leq |A\cap B|\cdot |P|$$
This lemma allows us to check that the Hall conditions are satisfied. Indeed, take $$X\subset L$$ and set $$A=\{ b\in P\colon \exists x\in X \; b\leq X\}.$$ Then we need to check that $$|A\cap S|\geq |X|$$. But the Lemma gives $$|A\cap S|\geq |A|\cdot \frac{|S|}{|P|}=|A|/2$$, and hence $$|X|\leq |A\cap L|\leq |A|/2\leq |A\cap S|$$, as desired.