Search

We derive a generating series for the number of free subgroups of finite index in $\Delta^+ = \mathbb{Z}_p*\mathbb{Z}_q$ by using a connection between free subgroups of $\Delta^+$ and certain hypermaps (also known as ribbon graphs or "fat" graphs), and show that this generating series is transcendental. We provide non-linear recurrence relations for the above numbers based on differential equations that are part of the Riccati hierarchy. We also study the generating series for conjugacy classes of free subgroups of finite index in $\Delta^+$, which correspond to isomorphism classes of hypermaps. Asymptotic formulas are provided for the numbers of free subgroups of given finite index, conjugacy classes of such subgroups, or, equivalently, various types of hypermaps and their isomorphism classes., Comment: 27 pages, 3 figures; supplementary SAGE worksheets available at http://sashakolpakov.wordpress.com/list-of-papers/

A relationship between the general linear group G L ( n , m ) and integer partitions was investigated by Macdonald in order to calculate the number of conjugacy classes in G L ( n , m ) . In this paper, the author introduced two different factorizations for a special case of Lambert series in order to prove that the number of conjugacy classes in the general linear group G L ( n , m ) and the number of partitions of n into k different magnitudes are related by a finite discrete convolution. New identities involving overpartitions, partitions into k different magnitudes and other combinatorial objects are discovered and proved in this context.

The conjugacy relation defines a partition of words into equivalence classes. We call these classes circular words. Periodic properties of circular words are investigated in this article. The Periodicity Theorem of Fine and Wilf does not hold for weak periods of circular words; instead we give a strict upper bound on the length of a non-unary circular word that has two given relatively prime weak periods. Weak periods also lead to a way of representing circular words in a more compact form. We investigate in which cases are these representations unique or minimal. We will also analyze weak periods of circular Thue-Morse, Fibonacci and Christoffel words.

In this paper, we introduce a generalization of Catalan numbers. To obtain this extension, we construct a family of subsets which depend on three parameters and whose cardinals originate it. The elements of this family are used to classify canonical primitive connected matrices of the p-Sylow of GL"n(q), problem that is related to Higman's Conjecture, which asserts that if G"n is the subgroup of GL"n(q) consisting of upper unitriangular matrices, then the number of conjugacy classes of G"n is a polynomial in q. The construction of these subsets allows us to prove by elementary way the recurrence relations and properties of our generalization of Catalan numbers. The associated sequences of integers can be arranged in tables called s-triangles. If s=1, the 1-triangle is the Catalan triangle. Consequently, to particularize the identities and properties of the s-triangles to the 1-triangle, we can deduce identities of Catalan numbers already proved. Moreover, for [email protected]?5 the first diagonals of the s-triangles are well-known sequences of integers which arise in many mathematical scopes.

The number of minimal transitive star factorizations of a permutation was shown by Irving and Rattan to depend only on the conjugacy class of the permutation, a surprising result given that the pivot plays a very particular role in such factorizations. Here, we explain this symmetry and provide a bijection between minimal transitive star factorizations of a permutation \pi having pivot k and those having pivot k'., Comment: Final version, to appear in Discrete Mathematics

Lagarias showed that the shift dynamical system S on the set Z"2 of 2-adic integers is conjugate to the famous 3x+1 map T under a conjugacy @F. Thus for each continuous endomorphism f"~ of S there is a corresponding endomorphism H"f=@F@?f"~@?@F^-^1 of T and a map @J"f from the coimage of H"f to itself defined by @J"f([x])=[T(x)]. In this paper, we completely classify all continuous endomorphisms f"~ of S for which @J"f is conjugate to T. We then define an infinite family of such maps, @J"M"""k, that are ''neutral'' modulo 2^k^-^1 in the sense that each element of the domain is a complete residue system modulo 2^k^-^1. By investigating the relationships between T-cycles and the @J"M"""k-cycles that contain them, we obtain an alternate method for studying the dynamics of T. This method is used to prove several new results pertaining to T-cycles, which are then applied to yield several possible approaches to the 3x+1 conjecture.

We use the conceptual idea of “maps on orbifolds” and the theory of the non-Euclidean crystallographic groups (NEC groups) to enumerate rooted and unrooted maps (both sensed and unsensed) on surfaces regardless of genus. As a consequence we deduce a formula for the number of chiral pairs of maps. The enumeration principle used in this paper is due to Mednykh (2006) [15], it counts the number of conjugacy classes of subgroups in NEC groups which are in one-to-one correspondence with unrooted (sensed or unsensed) maps.

Let G be a group of order 4n and t an involution of G. A 2n-subset R of G is called a left Hadamard transversal of G with respect to if G=R and R@^R^(^-^1^)@^=nS"1@^+2nS"2@^ for some subsets S"1 and S"2 of G. Let H be a subgroup of G such that G=[G,G]H, t@?H, and t^G@?H, where t^G is the conjugacy class of t and [G,G] is the commutator subgroup of G. In this article, we show that if R satisfies a condition (*)R xR@?x@?G@?{1}, then R is a (2n,2,2n,n) relative difference set and one can construct a vxv integral matrix B such that BB^T=B^TB=(n/2)I, where v is a positive integer determined by H and t^G (see Theorem 2.6). Using this we show that there is no left Hadamard transversal R satisfying (*) in some simple groups.

It is known that each conjugacy class of actions of PGL ( 2 , Z ) on F q ∪ { ∞ } can be represented by a coset diagram D ( θ , q ) , where θ ∈ F q and q is a power of a prime p. In this paper, we are interested in parametrizing the conjugacy classes of actions of the infinite triangle group △ ( 2 , 3 , 11 ) = 〈 x , y : x 2 = y 3 = ( xy ) 11 = 1 〉 on F q ∪ { ∞ } . For each θ ∈ F q we then associate a coset diagram D ( θ , q ) depicting the conjugacy class of actions of △ ( 2 , 3 , 11 ) on F q ∪ { ∞ } . We have obtained conditions on θ and q which guarantee only those coset diagrams which depict homomorphic images of △ ( 2 , 3 , 11 ) in PGL ( 2 , q ) . We are interested in finding also when the coset diagrams for the actions of PGL ( 2 , Z ) on F q ∪ { ∞ } contain vertices on the vertical line of symmetry. It will enable us to show that for infinitely many values of q , the group PGL ( 2 , q ) has minimal genus, while also for infinitely many q , the group PSL ( 2 , q ) is an H * -group.

Consider a conjugacy class of a Coxeter group, and define an equivalence relation on the elements using the length function. Then define a partial order on the equivalence classes, to form a partially ordered set. In this paper, we show some properties of these posets. In particular, we prove properties of the minimal elements, such as how many are there in a particular poset and how many group elements are in the minimal equivalence classes. We deal especially with the finite classical groups A n , B n , and D n .

We present a simple proof of the Littlewood-Richardson rule using a sign-reversing involution, and show that a similar involution provides a combinatorial proof of the SXP algorithm of Chen et al. (1984) which computes the Schur function expansion of the plethysm of a Schur function and a power sum symmetric function. The methods of this paper have also been applied to prove combinatorial formulas for the characters of coordinate rings of nilpotent conjugacy classes of matrices (Shimozono, 1998).

Let Г̃ be a bipartite digraph. Then the digraphs Γ whose canonical double covering is isomorphic with Г̃ are (up to isomorphisms) in one to one correspondence with the conjugacy classes, in Aut(Г̃), of involutions inverting the color classes of Г̃.

We study permutation enumeration of the hyperoctahedral group Bn through a combinatorial use of the Bn-analogues of symmetric functions, denoted AB. We define an appropriate homomorphism ζ:AB → Q[x] and remarkably, applying this homomorphism to one of the bases of AB produces polynomials which correspond to enumerating Bn with respect to descents. Applying ζ to a second basis corresponds to enumerating a conjugacy class of Bn with respect to a new descent type statistic which arises naturally.

Given a free partially commutative monoid, we interpret equivalence classes of words (also called ‘traces’) in terms of Viennot's heaps of pieces. We study the notion of conjugacy applied to this context. Each heap has a unique representative in the set of ‘standard words’ which are lexicographically ordered. Then, by definition, Lyndon heaps are the minimal elements of the conjugacy classes of heaps. Most combinatorial properties of Lyndon words have a counterpart in the theory of Lyndon heaps. For instance, a ‘standard factorization’ exists, the set of Lyndon heaps provides a complete factorization of the monoid, etc.

A method allowing an analysis of the suborbits of permutation groups with conjugacy complete stabilizers is derived and applied to the special case of the linear group PSL(2, p ) acting on cosets of A 4 .

The category of combinatorial species was introduced by Joyal, and has been studied extensively by him and others. This category is equipped with a derivative operation (endofunctor). This allows one to differentiate species in a manner similar to differentiating power series. We solve, completely, the family of differential equations D k y = X n for species. For this, we use results on the conjugacy classes of sharply k -transitive groups. We provide, also, a new proof of a sharpened version of Zassenhaus' theorem on sharply 2-transitive groups of type I.

We determine the properties of the conjugate τ = ϕ −1 Δϕ of a diagonal function Δ by the mark function ϕ in the incidence algebra of the poset of conjugacy classes of subgroups of a finite group G . Particular choices for Δ provide applications to the Burnside ring of G , to the theory of β-rings and to Redfield-Polya enumeration. In particular, we obtain a Polya-like substitution formula for the K [ J ]-inventory of colorings of a set whose symmetry group is a wreath product G [ F ].

We show that the number of permutations π on N symbols, with k cycles, such that π is the product of an arbitrary but fixed full cycle and a permutation in a designated conjugacy class satisfies a linear recurrence equation with a fixed number of terms.

Garsia (1988) gives a remarkably simple expression for the major index enumerator for permutations of a fixed cycle type evaluated at a primitive root of unity. He asks for a direct combinatorial proof of this identity. Here we give such a combinatorial derivation.

The product of conjugacy classes of the symmetric group in its group algebra is found as a linear combination of conjugacy classes with integer coefficients. The purpose of this paper is to give a partial answer to the problem of finding simple combinatorial rules to obtain these coefficients. In particular, we will show that the product C (n) ∗C (n) of the class of circular permutations with itself can be decomposed in a simple manner.

Necessary and sufficient conditions for a permutation to be a product of two reflections (permutations of order = = @?"0, X^3 S"A, where X is the conjugacy class of reflections with no fixed point.

In the usual treatment of covering spaces, the algebraic object associated with a cover is a conjugacy class of subgroups of the fundamental group of the target space. For finite degree covers, one could as easily choose the algebraic object to be a class of homomorphisms from the fundamental group of the target space to the symmetric group on n letters, where n is the degree of the cover. A description of the representation of covering spaces is given in this paper. Then the permutation voltage assignment used in the permutation voltage construction of graph and surface covers described in [6] is viewed as a means of defining one such homomorphism. Using this view, methods are given for counting the number of connected components in the constructed cover and for determining the orientability of the surface cover. In addition, it is observed that every branched surface cover can be constructed by permutation voltage assignments.

Using combinatorial methods, we will examine products of conjugacy classes in the symmetric group S"0 of all permutations of a countably infinite set. If [email protected]"0 has at least one infinite orbit in the underlying set and if [email protected]"0, we give a characterization of when s is a product of two conjugates of p. From this, we derive that if four permutations p"[email protected]"0 (i = 1, 2, 3, 4) are given which all have infinite support, then any permutation of S"0 is a product of four elements conjugate to p"1, p"2, p"3 and p"4, respectively. Similar results for permutations of uncountable sets are shown and classical group-theoretical results are obtained from these theorems.

In a λ-ring there are operations λ π , ψ π and β π for π a partition of n . These operations are related by identities analogous to those between the symmetric functions a π , s π and h π . In a β-ring there is defined an operation β H for [ H ] a conjugacy class of subgroups of the symmetric group S n . This paper defines operations ψ H and λ H in a β-ring such that whenever the β-ring is a λ-ring, and H a Young subgroup S π of S n , then the β H , ψ H and λ H reduce to β π , ψ π and λ π , respectively. The identities relating the new operations are also investigated.

Let k τ denote the sum of all members of a conjugacy class τ of a finite symmetric group. Let k ρ · k σ = ∑ τ£ρστ k τ . Generating functions are obtained for the coefficients c ρστ , where ρ and σ are reflection classes.

Results on vertex coloring and the vertex independence number of a finite graph are used to prove:Theorem. Let G be a finite group with conjugacy classes indexed by cardinality: 1 = |[x1]| ⩽|[x2]| ⩽···, and let CG(x) denote the centralizer of x. If m is the smallest integer i such that |[x1]|+|[x2]|+···+|[x1]|⩾|C(x1)|, then each abelian subgroup A of G has card inality|A|⩽ |[x1]|+|[x2]|+···+|[xm]|.Theorem. Let G be a finite group with a proper subgroup M, suchthat x∈M−{1}⇒CG(x)⊆ M. Then G contains at least [|G|13] pairwise non-commuting elements, and hence G cannot be covered by the union of fewer than [|G|13] abelian subgroups.Theorem. Let S be a locally maximal sum-free subset of the abelian group G. Then |S−S|+|SU−S|−3⩽|G|(1−|S−S|-1), with equality if and only if S−S is a subgroup H of G, [G:H]=3, and S is a coset of H.Some open problems are also stated.

The 3x+1 map T is defined on the 2-adic integers by T(x)=x/2 for even x and T(x)=(3x+1)/2 for odd x and the 3x+1 conjecture states that the T-orbit of any positive integer contains 1. We define and study properties of the unique nontrivial autoconjugacy Ω of T. This autoconjugacy sends x to the unique 2-adic integer whose parity vector is the one's complement of the parity vector of x. We prove that if Ω maps rational numbers to rational numbers then there are no divergent T-orbits of positive integers. The map Ω is then used to restate the 3x+1 conjecture in a parity neutral form. We derive a necessary and sufficient condition for a cycle to be self-conjugate and show that self-conjugate cycles contain only positive elements. It is then shown that the only self-conjugate cycle of integers is {1,2}. Finally, we prove that for any rational 2-adic integer x, lim̄κn(x)n+limκn(Ω(x))/n=1 where κn(x) is the number of ones in the first n digits of the parity vector of x, and we use this along with generalizations of known restrictions on lim̄κn(x)/n to prove most of the results in the paper.

To an absolute plane (E,L,=,@a) in the general sense of Karzel et al. [Einfuhrung in die Geometrie, UTB 184, Vandenhoeck, Gottingen, 1973, Section 16] there will be associated an ordered commutative group (W,+

We express the number of elements of the hyperoctahedral group Bn, which have descent set K and such that their inverses have descent set J, as a scalar product of two representations of Bn. We also give the number of elements of Bn, which have a prescribed descent set and which are in a given conjugacy class of Bn by another scalar product of representations of Bn. For this, we first establish corresponding results for certain wreath products. We finally give, by generating series of symmetric functions, some analogs of the classical formulas which express the exponential generating series of alternating elements in the Bn's.

In this paper, we present formulas for the number of decompositions of elements of the Weyl groups of type An, Dn and Bn as products of a number of reflections that is not necessarily minimal. For this purpose, we consider the poset of conjugacy classes of W introduced in Bédard and Goupil (1992) for the symmetric group. This poset describes the action of the set of reflections of a reflection group on its conjugacy classes. In particular, we show how the reflection decompositions in the symmetric group %plane1D;50A;n are related to the reflection decompositions in Dn.

All continuous endomorphisms f"~ of the shift dynamical system S on the 2-adic integers Z"2 are induced by some f:B"n->{0,1}, where n is a positive integer, B"n is the set of n-blocks over {0, 1}, and f"~(x)=y"0y"1y"2... where for all i@?N, y"i=f(x"ix"i"+"1...x"i"+"n"-"1). Define D:Z"2->Z"2 to be the endomorphism of S induced by the map {(00,0),(01,1),(10,1),(11,0)} and V:Z"2->Z"2 by V(x)=-1-x. We prove that D, V@?D, S, and V@?S are conjugate to S and are the only continuous endomorphisms of S whose parity vector function is solenoidal. We investigate the properties of D as a dynamical system, and use D to construct a conjugacy from the 3x+1 function T:Z"2->Z"2 to a parity-neutral dynamical system. We also construct a conjugacy R from D to T. We apply these results to establish that, in order to prove the 3x+1 conjecture, it suffices to show that for any m@?Z^+, there exists some n@?N such that R^-^1(m) has binary representation of the form x"0x"1...x"2"^"n"-"1@? or x"0x"1x"2...x"2"^"n@?.

A finite group G is said to be action reconstructible if, for any action of G on a finite set, the numbers of orbits under restriction to each subgroup always give enough information to reconstruct the action up to equivalence. G is character reconstructible if, given any matrix representation of G, the mean value of the character on each subgroup always gives enough information to reconstruct the character. The conjugacy matrix of G is the matrix whose (ij) entry is the number of elements of the jth conjugacy class belonging to a typical subgroup of the ith subgroup conjugacy class. It is shown that G is action reconstructible if and only if the rows of this matrix are linearly independent (which is in turn true if and only if G is cyclic), and is character reconstructible if and only if the columns are linearly independent (which is true if and only if any two elements of G which generate conjugate cyclic subgroups are themselves conjugate).