A355730 Number of binary relations R on [n] such that R is contained in R^2.

1, 2, 13, 333, 34924, 15339497, 28399641433

Offset: 0

Author

Geoffrey Critzer, Jul 15 2022

Keywords

• nonn
• more

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

Examples

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

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.

Crossrefs

Cf. A006905, A121337, A070322.

Programs

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}]

Formula

Limit_{n->oo} a(n)/2^(n^2) = 1.

Extensions

a(5)-a(6) from Pontus von Brömssen, Jul 19 2022

Comments clarified by Geoffrey Critzer, Oct 16 2023