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.

  • $\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$ – Gerhard Paseman Apr 10 '13 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$ – Tom Goodwillie Apr 10 '13 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$ – Martin Rubey Apr 10 '13 at 16:47
  • $\begingroup$ @Tom: Consider the empty relation. $\endgroup$ – Brendan McKay Apr 11 '13 at 9:13
  • $\begingroup$ OK, I'm considering it. $\endgroup$ – Tom Goodwillie Apr 11 '13 at 23:42

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

| cite | improve this answer | |
  • $\begingroup$ Algebra, pah! Where is a lovely combinatorial proof? Gerhard "Some Logicians Don't Appreciate Distinction" Paseman, 2013.04.10 $\endgroup$ – Gerhard Paseman Apr 10 '13 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$ – Emil Jeřábek Apr 10 '13 at 16:30
  • $\begingroup$ This seems like a strange use of the term "kernel" to me. $\endgroup$ – Greg Martin Apr 10 '13 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$ – Emil Jeřábek Apr 10 '13 at 16:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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