Here, we try to derive an explicit and good upper bound on the number of
reflexive binary relations on the set {1,β¦,π} up to isomorphism. A
trivial upper bound is 2^{π(πβ1)}, and an asymptotic approximation
(which I don't believe yet) is 2^{π(πβ1)}/π!. (My longer-term and
slightly more complicated goal, which we are not dealing with here, is
to derive an explicit and good upper bound on the number of reflexive
binary relations on the set {1,β¦,π} up to isomorphisms that map 1 to 1.)
To determine an upper bound, I started reading "The number of structures
of finite relations" by Robert L. Davis. The first place I got stuck is
on p. 488, l. 16: "The effect of π on the submatrix π΄β is fully
determined by the effect of (1 2 β― β) on its rows, and that of (1β² 2β² β―
πβ²) on its columns." (As a consequence of me not understanding this, I
also failed to understand the last subscript index "π+βπ, πβ²+βπ" in
the following equality "π_{ππβ²} = β― = 2_{π+βπ,πβ²+βπ}".) What
does the author mean in the sentence "The effectβ¦" and why? I thought
that these two cycles are disjoint, and that each of them induces a
cyclic permutation of both rows and columns; after all, we are dealing
with an adjacency matrix, aren't we? Any ideas?
Question: Is there a clean, self-contained derivation of an explicit
upper bound on the number of reflexive binary relations on {1,β¦,π} up
to isomorphism? In case the answer to the question is no: is there
perhaps just a reformulation of the result of Davis with another (or
better explained) proof? In case the answer to the question is yes: is
there perhaps even an upper bound that is exact for π β {1,2}?
Glossary of used terms:
A binary relation π
is called reflexive on a set π if ππ
π for all
π β π. Relations π
,π
Μ
are called isomorphic if there is a bijection
between πβ(π
)βͺπβ(π
) and πβ(π
Μ
)βͺπβ(π
Μ
) that is a homomorphism
such that the inverse of the bijection is also a homomorphism. Here,
πα΅’ is the projection to the πth component (πβ{1,2}). A map π is a