Groups | Search | Server Info | Login | Register

Groups > tum.math.linalg > #1

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

Show all headers | View raw

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.  What does the 
author mean exactly by "dominant" and 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)}/𝑛!, whatever ∼ might exactly mean.

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 ∀ 𝑎,𝑏 ∈ 
𝜋₁(𝑆)∪𝜋₂(𝑆): 𝑎𝑆𝑏 ⇔ 𝑓(𝑎)𝑆′𝑓(𝑏).

Back to tum.math.linalg | Next | Find similar

Thread

Explicit upper bound on the number of irreflexive relations on {1,…,𝑛} up to isomorphism Md Ayquassar <MdAyqFUCKSPAM@ramblerSPAMFUCK.ru> - 2020-01-22 20:00 +0100

csiph-web