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 β π,π β
πβ(π)βͺπβ(π): πππ β π(π)πβ²π(π).