Función de conjunto subaditivo

En matemáticas, una función de conjunto subaditiva es aquella cuyo valor, informalmente, tiene la propiedad de que el valor de la función en la unión de dos conjuntos es, como máximo, la suma de los valores de la función en cada uno de los conjuntos. Esto guarda relación temática con la propiedad de subaditividad de las funciones de valor real.

Dejar${\displaystyle \Omega }$ser un conjunto y${\displaystyle f\colon 2^{\Omega }\rightarrow \mathbb {R} }$sea ​​una función de conjunto , donde${\displaystyle 2^{\Omega }}$denota el conjunto potencia de${\displaystyle \Omega }$La función f es subaditiva si para cada subconjunto${\displaystyle S}$y${\displaystyle T}$de${\displaystyle \Omega }$, tenemos${\displaystyle f(S)+f(T)\geq f(S\cup T)}$. ^{[ 1 ] [ 2 ]} Nótese que por sustitución de${\displaystyle T=S}$En la ecuación definitoria, se deduce que${\displaystyle f(S)\geq 0}$para todos${\displaystyle S}$⁠ .

Toda función de conjunto submodular no negativa es subaditiva (la familia de funciones submodulares no negativas está estrictamente contenida en la familia de funciones subaditivas).

La función que cuenta el número de conjuntos necesarios para cubrir un conjunto dado es subaditiva.${\displaystyle T_{1},\dotsc ,T_{m}\subseteq \Omega }$de tal manera que${\displaystyle \cup _{i=1}^{m}T_{i}=\Omega }$. Definir${\displaystyle f}$como el número mínimo de subconjuntos necesarios para cubrir un conjunto dado. Formalmente,${\displaystyle f(S)}$es el número mínimo${\displaystyle t}$de tal manera que existan conjuntos${\displaystyle T_{i_{1}},\dotsc ,T_{i_{t}}}$satisfactorio${\displaystyle S\subseteq \cup _{j=1}^{t}T_{i_{j}}}$. Entonces${\displaystyle f}$es subaditivo.

El máximo de las funciones de conjuntos aditivos es subaditivo (dualmente, el mínimo de las funciones aditivas es superaditivo ). Formalmente, para cada${\displaystyle i\in \{1,\dotsc ,m\}}$, dejar${\displaystyle a_{i}\colon \Omega \to \mathbb {R} }$sean funciones de conjuntos aditivos. Entonces${\displaystyle f(S)=\max _{i}a_{i}(S)}$es una función de conjunto subaditiva.

Las funciones de conjuntos subaditivos fraccionarios son una generalización de las funciones submodulares y un caso especial de funciones subaditivas. Una función subaditiva${\displaystyle f}$es además subaditivo fraccional si satisface la siguiente definición. ^{[ 1 ]} Para cada${\displaystyle S\subseteq \Omega }$, cada${\displaystyle X_{1},\dotsc ,X_{n}\subseteq \Omega }$y cada${\displaystyle \alpha _{1},\dotsc ,\alpha _{n}\in [0,1]}$, si${\displaystyle 1_{S}\leq \sum _{i=1}^{n}\alpha _{i}1_{X_{i}}}$, entonces${\displaystyle f(S)\leq \sum _{i=1}^{n}\alpha _{i}f(X_{i})}$El conjunto de funciones fraccionariamente subaditivas es igual al conjunto de funciones que pueden expresarse como el máximo de funciones aditivas, como en el ejemplo del párrafo anterior. ^{[ 1 ]}

• Función de conjunto submodular
• Funciones de utilidad sobre bienes indivisibles