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?
Best Answer
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.