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

9 views
Skip to first unread message

Md Ayquassar

unread,
Feb 9, 2020, 2:25:15β€―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}^𝑛 (𝑝_{πœ‹,π‘˜}^2 π‘˜ βˆ’ 𝑝_{πœ‹,π‘˜}).

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 βˆ€ π‘Ž,𝑏 ∈
πœ‹β‚(𝑆)βˆͺπœ‹β‚‚(𝑆): π‘Žπ‘†π‘ ⇔ 𝑓(π‘Ž)𝑆′𝑓(𝑏).

Bruh

unread,
Aug 27, 2021, 7:46:29β€―PM8/27/21
to
--
----
CONFIDENTIALITY NOTICE: Β This email message, including any
attachments, is for the sole use of the
intended recipient(s) and may
contain information that is legally privileged, confidential and/or exempt
from
disclosure under applicable law. Β If you are not an intended
recipient, you may not review, use, copy, disclose
or distribute this
message or any of the information contained in this message to anyone. Β If
you are not the intended
recipient, please contact the sender by reply
email and destroy all copies of this message and any
attachments. Β Hampton
City Schools may monitor e-mail messages to and from the Hampton City
Schools
network. Β  Unintended transmission shall not constitute waiver of
any privilege or confidentiality protected under
federal statutes, the
Virginia Freedom of Information Act or any applicable laws.

Reply all
Reply to author
Forward
0 new messages