Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

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

1 view
Skip to first unread message

Md Ayquassar

unread,
Feb 9, 2020, 7:38:10β€―PM2/9/20
to
My (intermediate) goal is to derive an explicit and good upper bound on
the number of irreflexive binary relations on the set {1,…,𝑛} up to
isomorphism. A trivial upper bound is 2^{𝑛(π‘›βˆ’1)}, and an asymptotic
estimation (for which I have not seen a gap-free proof yet) could be
2^{𝑛(π‘›βˆ’1)}/𝑛!. (For a longer-term goal, see http://mathoverflow.net/
questions/350508 .)

To determine the upper bound, I read "The number of structures of finite
relations" by Robert L. Davis (1953) till Corollary 3A and "Calculations
on the number of structures of relations on finite sets" by McIlroy
(1955). McIlroy starts with a (slightly simplified and cleaned up)
formula

refβ‚™ = βˆ‘_{[πœ‹]} 2^{d_{refβ‚™}(πœ‹)} / (𝑝_{πœ‹,1}!1^{𝑝_{πœ‹,1}} β‹― 𝑝_{πœ‹,𝑛}!
𝑛^{𝑝_{πœ‹,𝑛}}) (⋆)

where [πœ‹] denotes the conjugate class of the permutation πœ‹, the term
𝑝_{πœ‹,π‘˜} denotes the number of cycles of length π‘˜ in the disjoint-cycles
representation of πœ‹ (πœ‹ ∈ 𝔖ₙ) and

d_{refβ‚™}(πœ‹) = 2 βˆ‘_{1β‰€β„Ž<π‘˜β‰€π‘›} 𝑝_{πœ‹,β„Ž} 𝑝_{πœ‹,π‘˜} gcd(β„Ž,π‘˜) + βˆ‘_{π‘˜=1}^𝑛 (𝑝_{πœ‹,π‘˜}Β² π‘˜
βˆ’ 𝑝_{πœ‹,π‘˜}).

Then, McIlroy says that the dominant contribution to the total number of
structures is due to just one of the partitions, namely, the partition
that consists of 𝑛 1-cycles and corresponds to the identity transform of
the group of transforms of the incidence matrix. Why is it the case?

The rest is easy: the term from the sum (⋆) corresponding to the identity
is 2^{𝑛(π‘›βˆ’1)}/𝑛!. (This one is indeed a straightforward simplification
using 𝑝_{id,1}=𝑛 and 𝑝_{id,π‘˜}=0 for π‘˜>1.) The author claims that refβ‚™ ∼
2^{𝑛(π‘›βˆ’1)}/𝑛!, probably meaning lim_{π‘›β†’βˆž} refβ‚™ : (2^{𝑛(π‘›βˆ’1)} / 𝑛!) = 1.

Question: Is there a clean, self-contained derivation of an explicit
upper bound on the number of irreflexive 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 McIlroy 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}?

I have consulted http://oeis.org/A000273, which links to various sources,
but I have not looked into any source precisely, except the
aforementioned papers of Davis and McIlroy. To the best of my knowledge,
neither the OEIS entry nor the two papers contain an answer.

Glossary of used terms:

A binary relation 𝑅 is called irreflexive if π‘Žβ‰ π‘ for all (π‘Ž,𝑏)βˆˆπ‘…. (By the
way, in the question above, it does not matter whether we count reflexive
or irreflexive relations.) 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
homomorphism between binary relations 𝑆 and 𝑆′ if dom 𝑓 βŠ‡ πœ‹β‚(𝑆)βˆͺπœ‹β‚‚(𝑆) and
βˆ€ π‘Ž,𝑏 ∈ πœ‹β‚(𝑆)βˆͺπœ‹β‚‚(𝑆): π‘Žπ‘†π‘ ⇔ 𝑓(π‘Ž)𝑆′𝑓(𝑏).
0 new messages