A355730 - OEIS

%I #37 Oct 16 2023 23:38:17

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

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

%C 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.

%C Almost all relations are dense.

%C 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.

%C 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

%H G. Markowsky, <a href="http://gdz.sub.uni-goettingen.de/dms/resolveppn/?PPN=GDZPPN001251775">Bounds on the index and period of a binary relation on a finite set</a>, Semigroup Forum, Vol 13 (1977), 253-259.

%H D. Rosenblatt, <a href="https://nvlpubs.nist.gov/nistpubs/jres/67B/jresv67Bn4p249_A1b.pdf">On the graphs of finite Boolean relation matrices</a>, Journal of Research of the National Bureau of Standards, 67B No. 4, 1963.

%H B. M. Schein, <a href="https://doi.org/10.3792/pja/1195520400">A construction for idempotent binary relations</a>, Proc. Japan Acad., Vol. 46, No. 3 (1970), pp. 246-247.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Dense_order">Dense order</a>.

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

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

%t Table[B = Tuples[Tuples[{0, 1}, nn], nn]; subsetQ[matrix1_, matrix2_] :=

%t   Apply[And, Map[! MemberQ[#, 1] &, matrix1 - matrix2]];Select[B, subsetQ[#, Clip[#.#]] &] // Length, {nn, 0, 4}]

%Y Cf. A006905, A121337, A070322.

%K nonn,more

%O 0,2

%A _Geoffrey Critzer_, Jul 15 2022

%E a(5)-a(6) from _Pontus von Brömssen_, Jul 19 2022

%E Comments clarified by _Geoffrey Critzer_, Oct 16 2023