9 views

Skip to first unread message

Feb 9, 2020, 2:25:15β―PM2/9/20

to

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 β π,π β

πβ(π)βͺπβ(π): πππ β π(π)πβ²π(π).

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 β π,π β

πβ(π)βͺπβ(π): πππ β π(π)πβ²π(π).

Aug 27, 2021, 7:46:29β―PM8/27/21

to

----

CONFIDENTIALITY NOTICE: Β This email message, including any

attachments, is for the sole use of the

intended recipient(s) and may

contain information that is legally privileged, confidential and/or exempt

from

disclosure under applicable law. Β If you are not an intended

recipient, you may not review, use, copy, disclose

or distribute this

message or any of the information contained in this message to anyone. Β If

you are not the intended

recipient, please contact the sender by reply

email and destroy all copies of this message and any

attachments. Β Hampton

City Schools may monitor e-mail messages to and from the Hampton City

Schools

network. Β Unintended transmission shall not constitute waiver of

any privilege or confidentiality protected under

federal statutes, the

Virginia Freedom of Information Act or any applicable laws.

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu