Explicit upper bound on the number of reflexive relations on {1,…,𝑛} up to isomorphism

4 views
Skip to first unread message

Jack Muller

unread,
Jan 20, 2020, 12:05:11β€―PM1/20/20
to
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 one (which I
don't believe yet) is 2^{𝑛(π‘›βˆ’1)}/(π‘›βˆ’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
π‘Ž ∈ 𝑋. Here, πœ‹α΅’ is the projection to the 𝑖th component (π‘–βˆˆ{1,2}).
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. A map 𝑓 is a
homomorphism between binary relations 𝑆 and 𝑆′ if dom 𝑓 βŠ‡
πœ‹β‚(𝑆)βˆ©πœ‹β‚‚(𝑆) and βˆ€ π‘Ž,𝑏 ∈ πœ‹β‚(𝑆)βˆ©πœ‹β‚‚(𝑆): π‘Žπ‘†π‘ ⇔ 𝑓(π‘Ž)𝑆′𝑓(𝑏).

Md Ayquassar

unread,
Jan 21, 2020, 9:40:07β€―AM1/21/20
to
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
Reply all
Reply to author
Forward
0 new messages