Groups | Search | Server Info | Login | Register

Groups > git.math.class.1507a4 > #1

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

Show all headers | View raw

Let us try 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 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 an upper bound, I started reading "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 
also failed to understand the last subscript index "𝑖+ℎ𝑘, 𝑗′+ℎ𝑘" in 
the following 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 git.math.class.1507a4 | 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:57 +0100

csiph-web