Advances in Pure and Applied Algebra (eBook)

Proceedings of the CONIAPS XXVII International Conference 2021

Ratnesh Kumar Mishra, Manoj Kumar Patel, Shiv Datt Kumar (Herausgeber)

eBook Download: EPUB

2023
170 Seiten
De Gruyter (Verlag)
978-3-11-078589-0 (ISBN)

Infos

This proceedings volume documents the contributions presented at the CONIAPS XXVII International Conference on Recent Advances in Pure and Applied Algebra. The entries focus on modern trends and techniques in various branches of pure and applied Algebra and highlight their applications in coding, cryptography, graph, and fuzzy theory. The book comprised a total of eighteen chapters, among which the first fourteen chapters are devoted to Algebra and related topics, and the last four chapters are included applied mathematics parts. The chapters present the latest research work being done on the frontiers of the various branches of algebra as well as showcase the cross-fertilization of the ideas and connection among these branches.Covering a broad range of topics in pure and applied Algebra, this volume would appeal to a wide spectrum of the researcher in Mathematics. The main aim of this monograph is to contribute to the development of pure and applied Algebra and hence we purposely sought a cross-section of topics in Algebra and encouraged expository presentations and research papers that provide an innovative link between research areas of Algebra and the field of their applications. This volume will be useful not only to experts but also to beginners of research in algebras and related topics.

Manoj Kumar Patel, NIT, Nagaland, India; Ratnesh Kumar Mishra, NIT, Jamshedpur, India; Shiv Datt Kumar, NIT, Allahabad, India.

Textauszug

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)∑r=1n1n1rt(n1−r)+t(n1)∑r=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)∑r=1n1n1r(tns(n1−r)+Bn1−r+1)+(tns(n1)+Bn1+1)∑r=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)∑r=1n1n1r(tns(n1−r)+(n1−r2)n1−r4)+(tns(n1)+(n12)n14)∑r=1n2n2r(tns(n2−r)+(n2−r2)n2−r4).

Proof.

Using the well-known relation

Bn+1=∑k=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)+2∑r=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)(∑r=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...

Produkt-Details

• Erscheint lt. Verlag: 3.4.2023
• Reihe/Serie: De Gruyter Proceedings in Mathematics
• Reihe/Serie: De Gruyter Proceedings in Mathematics
• Reihe/Serie: ISSN
• Zusatzinfo: 14 b/w ill.
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Mathematik
• Schlagworte: Codierungstheorie • Codierungstheroie • coding theory • cryptography. • Fuzzy-Theorie • Fuzzy Theory • Graphentheorie • graph theory • Pure and applied algebra • Pure and applied algebra, coding theory, graph theory, fuzzy theory, cryptography. • Reine und angewandte Algebra • Reine und applizierte lagebra
• ISBN-10: 3-11-078589-7 / 3110785897
• ISBN-13: 978-3-11-078589-0 / 9783110785890