6
$\begingroup$

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?

$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$ Aug 3, 2023 at 10:29
  • $\begingroup$ 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$. $\endgroup$ Aug 3, 2023 at 13:44

1 Answer 1

6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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