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?



Pair matching between divisors less and more than $\sqrt{N}$
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](https://en.wikipedia.org/wiki/FKG_inequality).


**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.


