Groups | Search | Server Info | Login | Register

Groups > umn.math.dept > #2

Explicit upper bound on the number of irreflexive binary 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 one 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 irreflexive 
binary relations on the set {1,…,𝑛} up to isomorphisms that map 1 to 1.)

To determine such an upper bound, I tried to understand "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 fail to understand the last subscript index "𝑖+ℎ𝑘, 𝑗′+ℎ𝑘" in 
the following block 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 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 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 irreflexive if 𝑎𝑅𝑎 for no 𝑎 ∈ 𝜋₁(𝑅) 
∪ 𝜋₂(𝑅).  Here, 𝜋ᵢ is the projection to the 𝑖th component 
(𝑖∈{1,2}).  (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.  A map 𝑓 is a homomorphism 
between binary relations 𝑆 and 𝑆′ if dom 𝑓 ⊇ 𝜋₁(𝑆)∩𝜋₂(𝑆) and ∀ 
𝑎,𝑏 ∈ 𝜋₁(𝑆)∩𝜋₂(𝑆): 𝑎𝑆𝑏 ⇔ 𝑓(𝑎)𝑆′𝑓(𝑏).

Back to umn.math.dept | Previous | Next | Find similar

Thread

Explicit upper bound on the number of irreflexive binary relations on {1,…,𝑛} up to isomorphism Jack Muller <Just_A_ManFUCKSPAM@mein.SPAMFUCKgmx> - 2020-01-20 17:27 +0100

csiph-web