Generalizations of Świerczkowski's lemma and the arity gap of finite functions

Miguel Couceiro, Erkko Lehtonen

Research output: Contribution to journalArticlepeer-review

21 Scopus citations

Abstract

Świerczkowski's lemma-as it is usually formulated-asserts that if f : An → A is an operation on a finite set A, n ≥ 4, and every operation obtained from f by identifying a pair of variables is a projection, then f is a semiprojection. We generalize this lemma in various ways. First, it is extended to B-valued functions on A instead of operations on A and to essentially at most unary functions instead of projections. Then we characterize the arity gap of functions of small arities in terms of quasi-arity, which in turn provides a further generalization of Świerczkowski's lemma. Moreover, we explicitly classify all pseudo-Boolean functions according to their arity gap. Finally, we present a general characterization of the arity gaps of B-valued functions on arbitrary finite sets A.

Original languageBritish English
Pages (from-to)5905-5912
Number of pages8
JournalDiscrete Mathematics
Volume309
Issue number20
DOIs
StatePublished - 28 Oct 2009

Keywords

  • Arity gap
  • Boolean functions
  • Essential variables
  • Finite functions
  • Pseudo-Boolean functions
  • Semiprojection
  • Variable identification minors
  • Variable substitution

Fingerprint

Dive into the research topics of 'Generalizations of Świerczkowski's lemma and the arity gap of finite functions'. Together they form a unique fingerprint.

Cite this