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,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

Table of n, a(n) for n=0..6.

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

Cf. A006905, A121337, A070322.

Sequence in context: A134485 A236551 A304727 * A075620 A336188 A348015

Adjacent sequences: A355727 A355728 A355729 * A355731 A355732 A355733

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