0
$\begingroup$

The number of non-isomorphic equivalence relations on a set of $n$ elements is the partition function $$p(n) =\frac{1}{\pi\sqrt{2}} \sum_{k=1}^{\infty} \sum_{h=1}^{k} \delta_{\gcd(h,k),1} \text{exp}\left(\pi i \sum_{j=1}^{k-1} \frac{j}{k}\left(\frac{hj}{k} - \left\lfloor \frac{hj}{k} \right\rfloor - \frac{1}{2}\right) - \frac{2\pi i h n}{k} \right) \sqrt{k} \frac{d}{dn}\left[ \frac{\sinh\left(\frac{\pi}{k} \sqrt{\frac{2}{3}(n - \frac{1}{24})}\right)}{\sqrt{n - \frac{1}{24}}} \right]$$ The Hardy-Ramanujan asymptotic formula states that $$p(n) \sim \frac{1}{4\sqrt{3}n}e^{\pi \sqrt{2n/3}}$$

By this answer (I would appreciate any reference to an actual derivation of this formula) the number of non-isomorphic relations on a set of $n$ elements is

$$a(n) = \sum_{1s_{1} + 2s_{2} + \cdot\cdot\cdot =n} \left(2^{\sum_{i,j \geq 1} \gcd(i,j)s_{i}s_{j}} \bigg/ \prod_{k=1} k^{s_{k}}s_{k}!\right)$$

I have no idea about the asymptotics of $a(n)$, but if you know of a reference that would be amazing. My question is whether anyone has researched, or if you have any idea about, whether or not $$\frac{p(n)}{a(n)} \sim 0$$ I conjecture that it is asymptotic to zero, but I have no idea how to prove it.

$\endgroup$
6
  • $\begingroup$ Consider a normal form for (the isomorphism classes of) the equivalence relations. (I like to think of them as diagonal block matrices.) There should be a region of "area" o(n) of unrelated elements, and in my picture a column of n/2 empty cells are guaranteed. Toggling elements in this area should give you that your ratio is smaller than 2/n, and likely even smaller with more astute toggling. Gerhard "Ask Me About Fibbonacci Matrices" Paseman, 2013.04.10 $\endgroup$ Apr 10, 2013 at 15:52
  • $\begingroup$ It appears to me that for every equivalence relation $E$ there are at least $n$ nonisomorphic ways of making a relation $R$ such that $E$ is generated by $R$. If so, then $\frac{p(n)}{a(n)}\le \frac{1}{n}$. $\endgroup$ Apr 10, 2013 at 16:02
  • 1
    $\begingroup$ The formula should be in Graphical Enumeration by Harary and Palmer, but I'm not sure. You can find a (sketch of a) derivation in Section 2.2 of Combinatorial Species and Tree like structures by Bergeron, Labelle and Leroux. $\endgroup$ Apr 10, 2013 at 16:47
  • $\begingroup$ @Tom: Consider the empty relation. $\endgroup$ Apr 11, 2013 at 9:13
  • $\begingroup$ OK, I'm considering it. $\endgroup$ Apr 11, 2013 at 23:42

1 Answer 1

3
$\begingroup$

You don’t need either of the two fancy formulas. Since every equivalence relation is the kernel of a function from the $n$-element set into itself, their number is at most $n^n$ (and taking them up to isomorphism can only make it smaller). On the other hand, there are $2^{n^2}$ binary relations in total, and each isomorphism class has at most $n!$ elements, hence there are at least $2^{n^2}/n!$ nonisomorphic relations. Thus, $$\frac{p(n)}{a(n)}\le\frac{n^nn!}{2^{n^2}}=2^{O(n\log n)-n^2}\to0.$$

$\endgroup$
4
  • $\begingroup$ Algebra, pah! Where is a lovely combinatorial proof? Gerhard "Some Logicians Don't Appreciate Distinction" Paseman, 2013.04.10 $\endgroup$ Apr 10, 2013 at 16:13
  • $\begingroup$ I’d prefer “Some Logicians Don’t Bother With Sophistication If There Is An Easy Way To Get Things Done”. $\endgroup$ Apr 10, 2013 at 16:30
  • $\begingroup$ This seems like a strange use of the term "kernel" to me. $\endgroup$ Apr 10, 2013 at 16:37
  • $\begingroup$ Well, that’s how it is called in universal algebra (though here the algebra would be just a set with empty signature). Any better name? $\endgroup$ Apr 10, 2013 at 16:51

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.