Are there any theoretical reasons out there which show us that why do we still not have a closed-form expression for transitivity counting. If you consider counting n-element binary relations of different types in the wiki article, then only transitivity seems to be missing(as partial order and preorder subsume transitivity). Are there any properties of transitivity that demonstrate the hardness of this problem.

  • 4
    $\begingroup$ mathoverflow.net/a/8980 perhaps relevant? $\endgroup$ Apr 10, 2020 at 3:50
  • $\begingroup$ It's not clear what problem you are referring to by "transitivity counting" or "counting transitivity". $\endgroup$
    – D.W.
    Jul 7, 2020 at 3:17
  • $\begingroup$ It is referring to getting a closed-form expression to this series : oeis.org/A006905 $\endgroup$
    – SagarM
    Jul 7, 2020 at 21:37


Your Answer

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