OFFSET
0,2
COMMENTS
Equivalently, a(n) is the number of binary relations R on [n] such that for all x,y in [n], if (x,y) is in R then there is a z in [n] such that (x,z) and (z,y) are both in R. A relation having this property is sometimes called a dense relation.
Almost all relations are dense.
A relation is idempotent if and only if it is both transitive and dense. A transitive relation R is dense (hence idempotent) if and only if there does not exist a pair (C_1,C_2) of edgeless components such that C_1 covers C_2 in the condensation of G(R). Here, G(R) is the directed graph (with self loops allowed) associated to R. The condensation of G(R) is the acyclic digraph obtained from G(R) by replacing every strongly connected component (SCC) by a single vertex and all directed edges from one SCC to another with a single directed edge. See Schein reference.
If R is contained in R^2 then the maximal cyclic nets in R are primitive (A070322) so that R is convergent, i.e., the period of R is equal to 1. Moreover, R converges to its transitive closure so that the index of R is at most n. See Rosenblatt reference. - Geoffrey Critzer, Sep 05 2023
LINKS
G. Markowsky, Bounds on the index and period of a binary relation on a finite set, Semigroup Forum, Vol 13 (1977), 253-259.
D. Rosenblatt, On the graphs of finite Boolean relation matrices, Journal of Research of the National Bureau of Standards, 67B No. 4, 1963.
B. M. Schein, A construction for idempotent binary relations, Proc. Japan Acad., Vol. 46, No. 3 (1970), pp. 246-247.
Wikipedia, Dense order.
FORMULA
Limit_{n->oo} a(n)/2^(n^2) = 1.
EXAMPLE
a(2) = 13 because all 16 binary relations on [2] are dense except for {{0,1},{0,0}}, {{0,0},{1,0}}, {{0,1},{1,0}}.
MATHEMATICA
Table[B = Tuples[Tuples[{0, 1}, nn], nn]; subsetQ[matrix1_, matrix2_] :=
Apply[And, Map[! MemberQ[#, 1] &, matrix1 - matrix2]]; Select[B, subsetQ[#, Clip[#.#]] &] // Length, {nn, 0, 4}]
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Geoffrey Critzer, Jul 15 2022
EXTENSIONS
a(5)-a(6) from Pontus von Brömssen, Jul 19 2022
Comments clarified by Geoffrey Critzer, Oct 16 2023
STATUS
approved