## Abstract

Świerczkowski's lemma-as it is usually formulated-asserts that if f : A^{n} → 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 language | British English |
---|---|

Pages (from-to) | 5905-5912 |

Number of pages | 8 |

Journal | Discrete Mathematics |

Volume | 309 |

Issue number | 20 |

DOIs | |

State | Published - 28 Oct 2009 |

## Keywords

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