The arity gap of order-preserving functions and extensions of pseudo-Boolean functions
English
Couceiro, Miguel[University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Mathematics Research Unit >]
Lehtonen, Erkko[University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) >]
Waldhauser, Tamás[University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Mathematics Research Unit >]
[en] arity gap ; order-preserving function ; aggregation function ; Owen extension ; Lovász extension
[en] The aim of this paper is to classify order-preserving functions according to their arity gap. Noteworthy examples of order-preserving functions are the so-called aggregation functions. We first explicitly classify the Lovász extensions of pseudo-Boolean functions according to their arity gap. Then we consider the class of order-preserving functions between partially ordered sets, and establish a similar explicit classification for this function class.