Reducibility number

• Published in: Discrete Applied Mathematics 2007-10, Vol.155 (16), p.2069-2076
• Main Authors: Kharat, V.S., Waphare, B.N., Thakare, N.K.
• Format: Article
• Language: English
• Subjects: Algorithmics. Computability. Computer arithmetics; Applied sciences; Boolean lattices; Combinatorics; Combinatorics. Ordered structures; Computer science; control theory; systems; Deletable elements in semidistributive; Distributive; Exact sciences and technology; Group theory; Group theory and generalizations; Lattice of subgroups of a group; Mathematics; Modular; Order, lattices, ordered algebraic structures; Pseudo-complemented; Reducibility in lattices and posets; Reducibility number; Sciences and techniques of general use; Theoretical computing; USM posets
• ISSN: 0166-218X; 1872-6771
• DOI: 10.1016/j.dam.2007.05.008

Let P be a poset in a class of posets P . A smallest positive integer r is called reducibility number of P with respect to P if there exists a non-empty subset S of P with | S | = r and P - S ∈ P . The reducibility numbers for the power set 2 n of an n-set ( n ⩾ 2 ) with respect to the classes of distributive lattices, modular lattices and Boolean lattices are calculated. Also, it is shown that the reducibility number r of the lattice of all subgroups of a finite group G with respect to the class of all distributive lattices is 1 if and only if the order of G has at most two distinct prime divisors; further if r is a prime number then order of G is divisible by exactly three distinct primes. The class of pseudo-complemented u-posets is shown to be reducible. Deletable elements in semidistributive posets are characterized.