Symmetry groups of Boolean functions and constructions of permutation groups
Let \(n\) and \(k\) be natural numbers, \(n\geq 1\) and \(k\geq 2\). A subgroup \(G\) of the symmetric group \(S_n\) is called \(k\)-representable iff there is a \(k\)-valued boolean function in \(n\) variables \(f\colon\{0,1\}^n\to\{0,1,\ldots,k-1\}\) such that \(G\) coincides with the symmetry group \(S(f)\) defined by \(S(f):=\{\sigma\mid\sigma\in S_n\) and \(f(x_1,\ldots,x_n)=f(x_{\sigma(1)},\ldots,x_{\sigma(n)})\) for all \((x_i)\in\{0,1\}^n\}\). \(G\) is called representable if it is \(k\)-representable for some \(k\geq 2\). In the present paper conditions are investigated for a subgroup \(G\leq S_n\) to be \(k\)-representable or not \(k\)-representable. As a counterexample to an assertion of \textit{P. Clote} and \textit{E. Kranakis} [SIAM J. Comput. 20, No. 3, 553-590 (1991; Zbl 0734.68038)]\ it is shown that there exists a \(3\)-representable permutation group which is not \(2\)-representable. Also several ways to construct non-(\(k\)-)representable groups are introduced and discussed in some detail, in particular intransitive and imprimitive group constructions. It is conjectured that for all \(k\geq 2\) there are \((k+1)\)-representable permutation groups which are not \(k\)-representable.
- Regular symmetric groups of Boolean functions.
- scientific article; zbMATH DE number 4055863
- ON PERMUTATION GROUPS AND PARTITIONS
- scientific article; zbMATH DE number 61082
- Symmetry groups of Boolean functions.
- The existential transversal property: a generalization of homogeneity and its impact on semigroups
- Permutation groups on unordered sets. II: On a theorem of Frucht
- t-representability of maximal subgroups of symmetric groups
- Über die reellen Kollineationsgruppen, die der symmetrischen oder der alternierenden Gruppe isomorph sind.
- Maximal Subgroups of Infinite Symmetric Groups
- A Construction for Vertex-Transitive Graphs
- Almost all Boolean functions have no linear symmetries
- Boolean Functions, Invariance Groups, and Parallel Complexity
- Characterization of \(p_ n\)-sequences for nonidempotent algebras
- Direct product and uniqueness of automorphism groups of graphs
- Essential arities of term operations in finite algebras
- Finite Permutation Groups and Finite Simple Groups
- scientific article; zbMATH DE number 3137403 (Why is no real title available?)
- scientific article; zbMATH DE number 3943825 (Why is no real title available?)
- scientific article; zbMATH DE number 4055862 (Why is no real title available?)
- scientific article; zbMATH DE number 3750987 (Why is no real title available?)
- scientific article; zbMATH DE number 192892 (Why is no real title available?)
- scientific article; zbMATH DE number 3223737 (Why is no real title available?)
- scientific article; zbMATH DE number 3341276 (Why is no real title available?)
- scientific article; zbMATH DE number 3419161 (Why is no real title available?)
- Idempotent algebras with log-linear free spectra
- On Lovász' lattice reduction and the nearest lattice point problem
- Set-Transitive Permutation Groups
- Cut approach to invariance groups of lattice-valued functions
- Direct product of automorphism groups of colored graphs
- Permutability class of a semigroup
- Invariance groups of functions and related Galois connections
- Abelian permutation groups with graphical representations
- Invariance groups of finite functions and orbit equivalence of permutation groups.
- Cyclic permutation groups that are automorphism groups of graphs
- Graphical representations of cyclic permutation groups
- Linear symmetries of Boolean functions.
- Graphical complexity of products of permutation groups
- Totally symmetric colored graphs
- Symmetry groups of Boolean functions.
- Orbit equivalence and permutation groups defined by unordered relations.
- Content and singletons bring unique identification minors
- Wreath product in automorphism groups of graphs
- Orbit closed permutation groups, relation groups, and simple groups
- Symmetries, graph properties, and quantum speedups
- Permutation groups on unordered sets. II: On a theorem of Frucht
- Symmetry groups for social preference functions
- Regular symmetric groups of Boolean functions.
This page was built for publication: Symmetry groups of Boolean functions and constructions of permutation groups
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1378434)
