Permutation group | EPFL Graph Search

In mathematics, a permutation group is a group G whose elements are permutations of a given set M and whose group operation is the composition of permutations in G (which are thought of as bijective functions from the set M to itself). The group of all permutations of a set M is the symmetric group of M, often written as Sym(M). The term permutation group thus means a subgroup of the symmetric group. If M = {1, 2, ..., n} then Sym(M) is usually denoted by Sn, and may be called the symmetric group on n letters. By Cayley's theorem, every group is isomorphic to some permutation group. The way in which the elements of a permutation group permute the elements of the set is called its group action. Group actions have applications in the study of symmetries, combinatorics and many other branches of mathematics, physics and chemistry. Basic properties and terminology Being a subgroup of a symmetric group, all that is necessary for a set of permu

Unique decomposition of homogeneous languages and application to isothetic regions

Nicolas René Jean Ninin

A language is said to be homogeneous when all its words have the same length. Homogeneous languages thus form a monoid under concatenation. It becomes freely commutative under the simultaneous actions of every permutation group G(n) on the collection of homogeneous languages of length n is an element of N. One recovers the isothetic regions from (Haucourt 2017, to appear (online since October 2017)) by considering the alphabet of connected subsets of the space vertical bar G vertical bar, viz the geometric realization of a finite graph G. Factoring the geometric model of a conservative program amounts to parallelize it, and there exists an efficient factoring algorithm for isothetic regions. Yet, from the theoretical point of view, one wishes to go beyond the class of conservative programs, which implies relaxing the finiteness hypothesis on the graph G. Provided that the collections of n-dimensional isothetic regions over G (denoted by R-n vertical bar G vertical bar) are co -unital distributive lattices, the prime decomposition of isothetic regions is given by an algorithm which is, unfortunately, very inefficient. Nevertheless, if the collections R-n vertical bar G vertical bar satisfy the stronger property of being Boolean algebras, then the efficient factoring algorithm is available again. We relate the algebraic properties of the collections R-n vertical bar G vertical bar to the geometric properties of the space I GI. On the way, the algebraic structure R-n vertical bar G vertical bar is proven to be the universal tensor product, in the category of semilattices with zero, of n copies of the algebraic structure R-1 vertical bar G vertical bar.

2019

The Minimal Faithful Permutation Degree For A Direct Product Obeying An Inequality Condition

Neil John Saunders

The minimal faithful permutation degree (G) of a finite group G is the least nonnegative integer n such that G embeds in the symmetric group Sym(n). Clearly (G x H) (G) + (H) for all finite groups G and H. In 1975, Wright ([10]) proved that equality occurs when G and H are nilpotent and exhibited an example of strict inequality where G x H embeds in Sym(15). In 2010 Saunders ([7]) produced an infinite family of examples of permutation groups G and H where (G x H) < (G) + (H), including the example of Wright's as a special case. The smallest groups in Saunders' class embed in Sym(10). In this article, we prove that 10 is minimal in the sense that (G x H)=(G) + (H) for all groups G and H such that (G x H)

Taylor & Francis Inc2016

Geometry of the Loss Landscape in Overparameterized Neural Networks: Symmetries and Invariances

Johanni Michael Brea, Wulfram Gerstner, Clément Hongler, Berfin Simsek, Francesco Spadaro

We study how permutation symmetries in overparameterized multi-layer neural networks generate `symmetry-induced' critical points. Assuming a network with

L

layers of minimal widths

r_1^*, \ldots, r_{L-1}^*

reaches a zero-loss minimum at

r_1^*! \cdots r_{L-1}^*!

isolated points that are permutations of one another, we show that adding one extra neuron to each layer is sufficient to connect all these previously discrete minima into a single manifold. For a two-layer overparameterized network of width

r^*+ h =: m

we explicitly describe the manifold of global minima: it consists of

T(r^*, m)

affine subspaces of dimension at least

h

that are connected to one another. For a network of width

m

, we identify the number

G(r,m)

of affine subspaces containing only symmetry-induced critical points that are related to the critical points of a smaller network of width

r&lt;r^*

. Via a combinatorial analysis, we derive closed-form formulas for

T

and

G

and show that the number of symmetry-induced critical subspaces dominates the number of affine subspaces forming the global minima manifold in the mildly overparameterized regime (small

h

) and vice versa in the vastly overparameterized regime (

h \gg r^*

). Our results provide new insights into the minimization of the non-convex loss function of overparameterized neural networks.

2021