The arity gap of order-preserving functions and extensions of pseudo-Boolean functions (Q412326): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / review text | |||
The arity gap (\(\text{gap}f\)) of a function \(f:A^n\to B\) that depends on all of its variables (\(n\geq2\)) is essentially the minimum decrease in the number of essential variables when variables of \(f\) are identified. In a previous paper, the first two authors [Discrete Math. 309, No. 20, 5905--5912 (2009; Zbl 1200.08001)] described all pseudo-Boolean functions \(f:\{0,1\}^n\to{\mathbb R}\) for which \(\text{gap}f=2\) and proved that \(\text{gap}f=1\) in the remaining cases. Every pseudo-Boolean function \(f\) can be written in the form \(f(\mathbf{x})=\sum_{S\subseteq[n]}m(S)\prod_{i\in S}x_i\;(\mathbf{x}\in\{0,1\}^n)\). The Owen extension (Lovász extension) of \(f\) is the function \(F_f:{\mathbb R}^n\to{\mathbb R}\) obtained from the above formula by taking \(\mathbf{x}\in{\mathbb R}\) (by taking \(\mathbf{x}\in{\mathbb R}\) and replacing \(\prod x_i\) by \(\bigwedge x_i\)). It is proved that \(\text{gap}F_f=\text{gap}f\) and a theorem similar to the above one holds for \(F_f\). If \(A\) and \(B\) are posets, \(A\) being upward directed and downward directed, and \(f:A^n\to B\) \((n\geq2)\) is an order-preserving function that depends on all of its variables, then \(\text{gap}f=2\) if and only if \(n=3\) and there is a non-constant order-preserving function \(h:A\to B\) such that \(f(x,x,y)=f(x,y,x)=f(y,x,x)=h(x)\); otherwise \(\text{gap}f=1\). | |||
Property / review text: The arity gap (\(\text{gap}f\)) of a function \(f:A^n\to B\) that depends on all of its variables (\(n\geq2\)) is essentially the minimum decrease in the number of essential variables when variables of \(f\) are identified. In a previous paper, the first two authors [Discrete Math. 309, No. 20, 5905--5912 (2009; Zbl 1200.08001)] described all pseudo-Boolean functions \(f:\{0,1\}^n\to{\mathbb R}\) for which \(\text{gap}f=2\) and proved that \(\text{gap}f=1\) in the remaining cases. Every pseudo-Boolean function \(f\) can be written in the form \(f(\mathbf{x})=\sum_{S\subseteq[n]}m(S)\prod_{i\in S}x_i\;(\mathbf{x}\in\{0,1\}^n)\). The Owen extension (Lovász extension) of \(f\) is the function \(F_f:{\mathbb R}^n\to{\mathbb R}\) obtained from the above formula by taking \(\mathbf{x}\in{\mathbb R}\) (by taking \(\mathbf{x}\in{\mathbb R}\) and replacing \(\prod x_i\) by \(\bigwedge x_i\)). It is proved that \(\text{gap}F_f=\text{gap}f\) and a theorem similar to the above one holds for \(F_f\). If \(A\) and \(B\) are posets, \(A\) being upward directed and downward directed, and \(f:A^n\to B\) \((n\geq2)\) is an order-preserving function that depends on all of its variables, then \(\text{gap}f=2\) if and only if \(n=3\) and there is a non-constant order-preserving function \(h:A\to B\) such that \(f(x,x,y)=f(x,y,x)=f(y,x,x)=h(x)\); otherwise \(\text{gap}f=1\). / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Sergiu Rudeanu / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 06E30 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 08A40 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 90C09 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6030376 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
arity gap | |||
Property / zbMATH Keywords: arity gap / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
pseudo-Boolean function | |||
Property / zbMATH Keywords: pseudo-Boolean function / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Owen extension | |||
Property / zbMATH Keywords: Owen extension / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Lovász extension | |||
Property / zbMATH Keywords: Lovász extension / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
order-preserving function | |||
Property / zbMATH Keywords: order-preserving function / rank | |||
Normal rank |
Revision as of 19:51, 29 June 2023
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The arity gap of order-preserving functions and extensions of pseudo-Boolean functions |
scientific article |
Statements
The arity gap of order-preserving functions and extensions of pseudo-Boolean functions (English)
0 references
4 May 2012
0 references
The arity gap (\(\text{gap}f\)) of a function \(f:A^n\to B\) that depends on all of its variables (\(n\geq2\)) is essentially the minimum decrease in the number of essential variables when variables of \(f\) are identified. In a previous paper, the first two authors [Discrete Math. 309, No. 20, 5905--5912 (2009; Zbl 1200.08001)] described all pseudo-Boolean functions \(f:\{0,1\}^n\to{\mathbb R}\) for which \(\text{gap}f=2\) and proved that \(\text{gap}f=1\) in the remaining cases. Every pseudo-Boolean function \(f\) can be written in the form \(f(\mathbf{x})=\sum_{S\subseteq[n]}m(S)\prod_{i\in S}x_i\;(\mathbf{x}\in\{0,1\}^n)\). The Owen extension (Lovász extension) of \(f\) is the function \(F_f:{\mathbb R}^n\to{\mathbb R}\) obtained from the above formula by taking \(\mathbf{x}\in{\mathbb R}\) (by taking \(\mathbf{x}\in{\mathbb R}\) and replacing \(\prod x_i\) by \(\bigwedge x_i\)). It is proved that \(\text{gap}F_f=\text{gap}f\) and a theorem similar to the above one holds for \(F_f\). If \(A\) and \(B\) are posets, \(A\) being upward directed and downward directed, and \(f:A^n\to B\) \((n\geq2)\) is an order-preserving function that depends on all of its variables, then \(\text{gap}f=2\) if and only if \(n=3\) and there is a non-constant order-preserving function \(h:A\to B\) such that \(f(x,x,y)=f(x,y,x)=f(y,x,x)=h(x)\); otherwise \(\text{gap}f=1\).
0 references
arity gap
0 references
pseudo-Boolean function
0 references
Owen extension
0 references
Lovász extension
0 references
order-preserving function
0 references