The character values of the irreducible constituents of a transitive permutation representation

In this article we determine the irreducible ordinary characters c_r \chi_r of a finite group G occurring in a transitive permutation representation (1_M )^G of a given subgroup M of G, and their multiplicities m_r = ((1_M)^G, c_r) 1 0 m_r = ((1_{M})^G, \chi_r) \neq 0 by means of a new explicit formula calculating the coefficients a_rk of the central idempotents e_r = ?_k=1^d a_rk D_k e_r = \sum\limits_{k=1}^{d} a_{rk} D_k in the intersection algebra B \cal B of (1_M )^G generated by the intersection matrices D_k corresponding to the double coset decomposition G = è_k=1^d Mx_k M G = \bigcup\limits_{k=1}^{d} Mx_{k} M .¶Furthermore, an explicit formula is given for the calculation of the character values c_r(x) \chi_{r}(x) of each element x ? G x \in G . Using this character formula we obtain a new practical algorithm for the calculation of a substantial part of the character table of G.     

On the quiver with relations of a repetitive algebra

Let A = kQ/ár?A = kQ/\langle \rho \rangle be a finite-dimensional k-algebra where r\rho is a set of relations for the quiver Q. Assume that r\rho contains only zero-relations or commutativity-relations. We describe explicitly the quiver with relations of the repetitive algebra  of A. The following well known result of D. Happel is one of the main reasons for studying Â: If A is of finite global dimension, then the stable module category of  and the derived category of A are equivalent.     

Independent Trees in Planar Graphs Independent trees

We prove the following statement: Let G be a finite k-connected undirected planar graph and s be a vertex of G. Then there exist k spanning trees T₁,…,T_k in G such that for each vertex xps of G, the k paths from x to s in T₁,…,T_k are pairwise openly disjoint.     

Auto-equivalences of derived categories acting on cohomology

Let A be a k-algebra which is projective as a k-module, let M be an A-module whose endomorphisms are given by multiplication by central elements of A, and let TrPic_k(A) be the group of standard self-equivalences of the derived category of bounded complexes of A-modules. Then we define an action of the stabilizer of M in TrPic_k(A) on the Ext-algebra of M. In case M is the trivial module for the group algebra kG = A, this defines an action on the cohomology ring of G which extends the well-known action of the automorphism group of G on the cohomology group.     

On the Number of Edges in Colour-Critical Graphs and Hypergraphs

A (hyper)graph G is called k-critical if it has chromatic number k, but every proper sub(hyper)graph of it is (k-1)-colourable. We prove that for sufficiently large k, every k-critical triangle-free graph on n vertices has at least (k-o(k))n edges. Furthermore, we show that every (k+1)-critical hypergraph on n vertices and without graph edges has at least (k-3/³?{k}) n(k-3/\sqrt[3]{k}) n edges. Both bounds differ from the best possible bounds by o(kn) even for graphs or hypergraphs of arbitrary girth.     

On locally graded groups with an Engel condition on infinite subsets

A group G is said to be in E_k^*E_k^* (k a positive integer), if every infinite subset of G contains a pair of elements that generate a k-Engel group.¶It is shown that a finitely generated locally graded group G in E_k^*E_k^* is a finite-by- (k-Engel) group, in particular a finite extension of a k-Engel group.     

Finding Large p-Colored Diameter Two Subgraphs

Given a coloring of the edges of the complete graph K on n vertices in k colors, a p-colored subgraph of K_n is any subgraph whose edges only use colors from some p element set. We show for k̿ and k\2hphk that there is always a p-colored diameter two subgraph of K_n containing at least [((k+p)n)/(2k)]\displaystyle{(k+p)n \over 2k} vertices and that this is best possible up to an additive constant l satisfying 0hl<k\2.     

Power residues on Abelian varieties

Given a prime l and an elliptic curve E defined over a number field k, we show that a non-zero point P] E(k) lies in lE(k) if and only if P lies in lE(k)(mod ) for almost all finite primes  of k. We give conditions on l under which analogous results hold for Abelian varieties and with one point replaced by a finite number of points. We also construct examples to show that these conditions are essential.     

Local calibration of mass and systolic geometry

We prove the simultaneous (k, n -- k)-systolic freedom, for a pair of adjacent integers k < n/2, of a simply connected n-manifold X. Our construction, related to recent results of I. Babenko, is concentrated in a neighborhood of suitable k-dimensional submanifolds of X. We employ calibration by differential forms supported in such neighborhoods, to provide lower bounds for the (n -- k)-systoles. Meanwhile, the k-systoles are controlled from below by the monotonicity formula combined with the bounded geometry of the construction in a neighborhood of suitable (n -- k + 1)-dimensional submanifolds, in spite of the vanishing of the global injectivity radius. The construction is geometric, with the algebraic topology ingredient reduced to Poincaré duality and Thom's theorem on representing multiples of homology classes by submanifolds. The present result is di.erent from the proof, in collaboration with A. Suciu, and relying on rational homotopy theory, of the k-systolic freedom of X. Our results concerning systolic freedom contrast with the existence of stable systolic inequalities, studied in joint work with V. Bangert.     

Eigenvalues of Random Power law Graphs

Many graphs arising in various information networks exhibit the "power law" behavior -the number of vertices of degree k is proportional to k^-# for some positive #. We show that if # > 2.5, the largest eigenvalue of a random power law graph is almost surely(1+ o(1))?m (1+ o(1))\sqrt{m} where m is the maximum degree. Moreover, the klargest eigenvalues of a random power law graph with exponent # have power law distribution with exponent 2# if the maximum degree is sufficiently large, where k is a function depending on #, mand d, the average degree. When 2<#< 2.5, the largest eigenvalue is heavily concentrated at cm^3-# for some constant c depending on # and the average degree. This result follows from a more general theorem which shows that the largest eigenvalue of a random graph with a given expected degree sequence is determined by m, the maximum degree, and [(d)\tilde] \tilde{d} , the weighted average of the squares of the expected degrees. We show that the k-th largest eigenvalue is almost surely (1+ o(1))?{m_k} (1+ o(1))\sqrt{m_k} where m_k is the k-th largest expected degree provided m_k is large enough. These results have implications on the usage of spectral techniques in many areas related to pattern detection and information retrieval.     

Regular orbits in powers of permutation representations

Let (Q,G) be a faithful permutation representation of a finite group G. Suppose that the G-set Q has t distinct non-zero marks. In a permutation representation analogue of a theorem of Brauer on linear representations, it is shown that the direct power (Q,G)^t of (Q,G) contains a regular orbit. As a corollary, the probability that a random element of Q^r lies in a regular orbit of (Q,G)^r is shown to tend to 1 exponentially fast as r tends to \infin\infin. Further, knowledge of the rate of convergence is equivalent to knowledge of the second largest value of the character of the linear permutation representation.     

(2, 3, k)-generated groups of large rank

For any fixed k 3 7k \geq 7 there exist integers n_k and a_k such that if the ring R is generated by a set of m elements t₁,...,t_m, where 2t₁-t₁²2t_1-t_1^2 is a unit of finite multiplicative order, and n 3 n_k+ma_kn \geq n_k+ma_k, then the group E_n(R) generated by elementary transvections is an epimorphic image of the triangle group D(2,3,k).\Delta (2,3,k).     

Invariants of free Lie algebras

Let k be a principal ideal domain with identity and characteristic zero. For a positive integer n, with n \geqq 2n \geqq 2, let H(n) be the group of all n x n matrices having determinant ±1\pm 1. Further, we write SL(n) for the special linear group. Let L be a free Lie algebra (over k) of finite rank n. We prove that the algebra of invariants L^B(n) of B(n), with B(n) ? { H(n), SL(n)}B(n) \in \{ H(n), {\rm SL}(n)\} , is not a finitely generated free Lie algebra. Let us assume that k is a field of characteristic zero and let áSem(n) ?\langle {\rm Sem}(n) \rangle be the Lie subalgebra of L generated by the semi-invariants (or Lie invariants) Sem(n). We prove that áSem(n) ?\langle {\rm Sem}(n) \rangle is not a finitely generated free Lie algebra which gives a positive answer to a question posed by M. Burrow [4].     

On matrix near-rings

Let R be a right near-ring with identity and M_n(R) be the near-ring of n 2 n matrices over R in the sense of Meldrum and Van der Walt. In this paper, M_n(R) is said to be s\sigma-generated if every n 2 n matrix A over R can be expressed as a sum of elements of X_n(R), where X_n(R)={f_ij^r | 1\leqq i, j\leqq n, r ? R}X_n(R)=\{f_{ij}^r\,|\,1\leqq i, j\leqq n, r\in R\}, is the generating set of M_n(R). We say that R is s\sigma-generated if M_n(R) is s\sigma-generated for every natural number n. The class of s\sigma-generated near-rings contains distributively generated and abstract affine near-rings. It is shown that this class admits homomorphic images. For abelian near-rings R, we prove that the zerosymmetric part of R is a ring, so the class of zerosymmetric abelian s\sigma-generated near-rings coincides with the class of rings. Further, for every n, there is a bijection between the two-sided subgroups of R and those of M_n(R).     

Cyclic codes and the Frobenius automorphism

Using the theory of cyclic codes the following problem of K. Burde' on characterizing finite fields GF (qⁿ) is solved:¶ Consider GF (qⁿ) as a vector space over GF (q). For which GF (qⁿ) exists for any k = 0, . . . ,n exactly one subspace C of dimension k and which is invariant under the Frobenius automorphism?     

Helly-type theorems for appropriate colorings of visibility sets

Summary. For positive integers q and n, think of P as the vertex set of a (qn + r)-gon, 0 ￡ r ￡ q - 1 0 \leq r \leq q - 1 . For 1 ￡ i ￡ qn + r 1 \leq i \leq qn + r , define V(i) to be a set of q consecutive points of P, starting at p(i), and let S be a subset of {V(i) : 1 ￡ i ￡ qn + r } \lbrace V(i) : 1 \leq i \leq qn + r \rbrace . A q-coloring of P = P(q) such that each member of S contains all q colors is called appropriate for S, and when 1 ￡ j ￡ q 1 \leq j \leq q , the definition may be extended to suitable subsets P(j) of P. If for every 1 ￡ j ￡ q 1 \leq j \leq q and every corresponding P(j), P(j) has a j-coloring appropriate for S, then we say P = P(q) has all colorings appropriate for S. With this terminology, the following Helly-type result is established: Set P = P(q) has all colorings appropriate for S if and only if for every (2n + 1)-member subset T of S, P has all colorings appropriate for T. The number 2n + 1 is best possible for every r 3 1 r \geq 1 . Intermediate results for q-colorings are obtained as well.     

Finding Convex Sets in Convex Position

Let F{\cal{F}} denote a family of pairwise disjoint convex sets in the plane. F{\cal{F}} is said to be in convex position, if none of its members is contained in the convex hull of the union of the others. For any fixed k 3 5k\ge5, we give a linear upper bound on P_k(n)P_k(n), the maximum size of a family F{\cal{F}} with the property that any k members of F{\cal{F}} are in convex position, but no n are.     

Some observations on the arithmetic of Eisenstein series for the modular group SL(2, \Bbb Z)

For even integers k\geqq4k\geqq4, let j_k(X)\varphi_k(X) be the separable rational polynomial that encodes the j-invariants of non-elliptic zeroes of the Eisenstein series E_k for the modular group SL(2,Bbb Z)(2,{Bbb Z}). We prove Kummer-type congruence properties for the j_k\varphi_k and, based on extensive calculations, make observations about the Galois group, the discriminant, and the distribution of zeroes of j_k(X)\varphi_k(X).     

A linear functional equation with a singularity at a fixed point

Summary. Local solutions of the functional equation¶¶z^k f( z) = ?_k=1ⁿG_k( z) f( s_kz ) +g( z) z{^\kappa} \phi \left( z\right) =\sum_{k=1}^nG_k\left( z\right) \phi \left( s_kz \right) +g\left( z\right) ¶with k > 0 \kappa > 0 and | s_k| \gt 1 \left| s_k\right| \gt 1 are considered. We prove that the equation is solvable if and only if a certain system of k \kappa conditions on G_k (k = 1, 2, ... , n) and g is fulfilled.     

Restricted 1-3-2 Permutations and Generalized Patterns

Recently, Babson and Steingrimsson (see [2]) introduced generalized permutations patterns that allow the requirement that two adjacent letters in a pattern must be adjacent in the permutation. We study generating functions for the number of permutations on n letters avoiding 1-3-2 (or containing 1-3-2 exactly once) and an arbitrary generalized pattern t \tau on k letters, or containing t \tau exactly once. In several cases, the generating function depends only on k and can be expressed via Chebyshev polynomials of the second kind, and the generating function of Motzkin numbers.