The arity gap of order-preserving functions and extensions of pseudo-Boolean functions (Q412326): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(5 intermediate revisions by 4 users not shown) | |||
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 | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1972195584 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 1003.2192 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the Number of Operations in a Clone / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the lattice of equational classes of Boolean functions and its closed intervals / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: ON THE EFFECT OF VARIABLE IDENTIFICATION ON THE ESSENTIAL ARITY OF FUNCTIONS ON FINITE SETS / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Generalizations of Świerczkowski's lemma and the arity gap of finite functions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Decompositions of functions based on arity gap / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On a quasi-ordering on Boolean functions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Equational characterizations of Boolean function classes / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The forbidden projections of unate functions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3639652 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5538300 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Descending chains and antichains of the unary, linear, and monotone subfunction relations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Equivalence of operations with respect to discriminator clones / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3682236 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A theory of fuzzy measures: Representations, the Choquet integral, and null sets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Multilinear Extensions of Games / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Galois theory for minors of finite functions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5344158 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Extensions of functions of 0-1 variables and applications to combinatorial optimization / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Boolean minors / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Essential arities of term operations in finite algebras / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Characterizations of closed classes of Boolean functions in terms of forbidden subfunctions and Post classes / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 04:02, 5 July 2024
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
0 references
0 references
0 references