4 views

Skip to first unread message

Jan 20, 2020, 12:05:11β―PM1/20/20

to

Here, we try to derive an explicit and good upper bound on the number of

reflexive 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 reflexive

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 reflexive 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 reflexive on a set π if ππ π for all

π β π. Here, πα΅’ is the projection to the πth component (πβ{1,2}).

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

reflexive 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 reflexive

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 reflexive 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 reflexive on a set π if ππ π for all

π β π. Here, πα΅’ is the projection to the πth component (πβ{1,2}).

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

Jan 21, 2020, 9:40:07β―AM1/21/20

to

Here, we try to derive an explicit and good upper bound on the number of

reflexive binary relations on the set {1,β¦,π} up to isomorphism. A

trivial upper bound is 2^{π(πβ1)}, and an asymptotic approximation
reflexive binary relations on the set {1,β¦,π} up to isomorphism. A

(which I don't believe yet) is 2^{π(πβ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 reflexive

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 reflexive 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 reflexive on a set π if ππ π for all

π β π. Relations π
,π
Μ
are called isomorphic if there is a bijection
to derive an explicit and good upper bound on the number of reflexive

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 reflexive 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 reflexive on a set π if ππ π for all

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

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu