Part I Algebra and its applications

Inequalities concerning transitive and equivalence relations

Firdous Ahmad Mala GDC Sopore, Baramulla, India Chandigarh University, Mohali, India Suhail Gulzar GCET Safapora, Ganderbal, India Ravinder K. Poonia Chandigarh University, Mohali, India

Abstract

In this paper, we obtain inequalities concerning t(n), the count of all transitive relations on an n-set and Bn, the famous Bell numbers that count all the equivalence relations on a set. We show that the problem of counting such relations can be tackled by enumerating relations that are symmetric but not transitive. We also present some new inequalities concerning the number of transitive relations on a set. These inequalities improve the results available in the existing literature.

Keywords: Transitive relations, enumeration, Bell numbers, counting, MSC 2010: 05A20,

1 Introduction

Let S be a nonempty set. Any subset R of S×S is a relation on S. A relation R on S is an equivalence relation if

(a)

(x,x)?R?x?S,

(b)

(x,y)?R?(y,x)?R?x,y?S,

(c)

(x,y),(y,z)?R?(x,z)?R?x,y,z?S,

that is, if R is reflexive, symmetric, and transitive.

Checking reflexivity and symmetry is pretty easy. However, deciding upon the transitivity of a relation may be challenging.

Using the elementary result of graph theory that if M is the matrix of a graph G, then M2 gives the number of paths of length 2 that connect two vertices of the graph. In [1] the following convenient and useful characterization of transitivity was given in terms of the matrix of a relation.

Let S={si:1?i?n} be a set on which a relation R is defined. Let a matrix A=[aij] be defined by

aij=1ifsiRsj,0otherwise.

If we express the relation as a graph, then this graph has a matrix A. It follows that A?A, where ? denotes Boolean multiplication of matrices (that is, multiplication of matrices with the operations of addition and multiplication on the elements carried out according to the laws of Boolean algebra), gives pairs of elements of S which "can be reached in two steps". Now the transitivity means, in fact, that elements that can be reached in two steps can also be reached in one step. Writing B=[bij] for A?A, this means that R is transitive if and only if bij=1?atj=1 ( i,j=1,2,.,n). This condition can be conveniently expressed in the form

(A?A)?A=A,

where ? denotes Boolean addition of matrices.

Enumerative combinatorics is a branch of mathematics that concerns itself with problems of counting. Despite the fact that transitive relations have been known and studied for long, counting all the transitive relations on a finite set is still an open problem in enumerative combinatorics. In spite of several efforts made in the past such as those in [7] and [2] and some efforts made recently such as those in [4], [5], and [6], no explicit formula or a recursive relation is known for the count of all relations on a set that are transitive. Very recently, in [4], numerous results concerning the count of transitive relations on a set were obtained. In particular, the author showed that if t(n) denotes this number on an n-set and n1,n2?N with n=n1+n2, then we have the following inequality:

(1.1)t(n)>t(n1)t(n2)+t(n2)Sr=1n1n1rt(n1-r)+t(n1)Sr=1n2n2rt(n2-r).

2 Main discussion

It was shown in [3] that relations that are reflexive, symmetric, and transitive on an n-set are equinumerous with those that are symmetric and transitive on a set with n+1 elements. This suggests that the open problem concerning the count of transitive relations could be attacked by taking into consideration relations that are symmetric but not transitive or, equivalently, by considering relations that are transitive but not symmetric. This provides some useful equivalent formulation of the problem.

Let ts(r) denote the number of relations on an n-element set that are both symmetric and transitive. If Bn is the number of equivalence relations on a set with n elements, then in view of [3], we have

(1.2)ts(n)=Bn+1.

If tns(n) denotes the number of relations on an n-element set that are transitive but not symmetric and t(n) denotes the number of transitive relations on a set with n elements, then

(1.3)t(n)=ts(n)+tns(n).

This simplifies to

(1.4)t(n)=Bn+1+tns(n).

Since there are several ways of calculating Bell numbers Bn, the problem of enumerating transitive relations on a set is reduced to the problem of enumerating transitive relations on a set that are not symmetric.

Theorem 1. If n,n1,n2?N are such that n=n1+n2, then (1.5)t(n)>(tns(n1)+Bn1+1)(tns(n2)+Bn2+1)+(tns(n2)+Bn2+1)Sr=1n1n1r(tns(n1-r)+Bn1-r+1)+(tns(n1)+Bn1+1)Sr=1n2n2r(tns(n2-r)+Bn2-r+1).

Proof.

The proof is immediate by using (1.4) in (1.1). ?

Theorem 2. If n,n1,n2?N are such that n=n1+n2, then (1.6)t(n)>(tns(n1)+(n12)n14)(tns(n2)+(n22)n24)+(tns(n2)+(n22)n24)Sr=1n1n1r(tns(n1-r)+(n1-r2)n1-r4)+(tns(n1)+(n12)n14)Sr=1n2n2r(tns(n2-r)+(n2-r2)n2-r4).

Proof.

Using the well-known relation

Bn+1=Sk=0nnkBk,

we observe that

Bn+1=Bn+nBn-1=nBn-1,Bn+1=n(n-2)(n-4)=?=(n2)n4.

Thus

(1.7)Bn+1=(n2)n4.

Inequality (1.6) is immediate by using (1.7) in (1.5). ?

Theorem 3. If n?N and n>1, then (1.8)t(n)>3(tns(n-1)+Bn)+2Sr=1n-1n1r(tns(n-r-1)+Bn-r).

Proof.

In (1.6), take n1=n-1 and n2=1. This gives

t(n)>(tns(n-1)+Bn)(tns(1)+B2)+(tns(1)+B2)(Sr=1n-1n-1r(tns(n-r-1)+Bn-r))+(tns(n-1)+Bn)(tns(0)+B1).

Since all relations on the null set and on a singleton are...