On the maximum size of the terms in the realization of symmetric functions

Abstract

The symmetric functions of m-valued logic have a sum-product (i.e. max-min) representation whose terms are sums of fundamental symmetric functions (FSFs). These sums may be simplified if they contain adjacent SFSs. This naturally leads to the combinatorial problem of determining the maximum size M(m, n) of adjacent-free sets of n-variable SFSs. J. C. Muzio (1990) related M(m, n) to a special graph F(m, n). Continuing in this direction, the authors give a simple closed formula for M (m, n) and then deduce that for large m or large n the largest nonsimplifiable set of n-variable SFSs consists of approximately one-half of all possible FSFs, proving thus also all the conjectures from the Muzio paper.