Limit theorem concerning random mapping patterns

Mapping patterns may be represented by unlabelled directed graphs in which each point has out-degree one. Assuming uniform probability distribution on the set of all mapping patterns onn points, we obtain limit distributions of some characteristics associated with the graphs of mapping patterns (connected and disconnected), asn. In particular, we study the number of points belonging to cycles, the number of cycles and components having prescribed (fixed) number of points and the total number of components.     

The asymptotic number of acyclic digraphs. I

We obtain an asymptotic formula forA _n,q , the number of digraphs withn labeled vertices,q edges and no cycles. The derivation consists of two separate parts. In the first we analyze the generating function forA _n,q so as to obtain a central limit theorem for an associated probability distribution. In the second part we show combinatorially thatA _n,q is a smooth function ofq. By combining these results, we obtain the desired asymptotic formula. Research supported by NSF under grant MCS-8300414. Research supported by NSERC under grant A4067. Research supported by NSF under grant MCS-8302282. Research supported by the Australian Department of Science and Technology under the Queen Elizabeth II Fellowship Scheme, while this author was at the University of Newcastle, Australia.     

An upper bound for the number of Eulerian orientations of a regular graph

We establish a new upper bound for the number of Eulerian orientations of a regular graph with even degrees.C.N.R.S., Paris with partial support of P.R.C. Mathématiques-Informatique.     

The asymptotic numbers of regular tournaments,Eulerian digraphs and Eulerian oriented graphs

LetRT(n), ED(n) andEOG(n) be the number of labelled regular tournaments, labelled loop-free simple Eulerian digraphs, and labelled Eulerian oriented simple graphs, respectively, onn vertices. Then, asn,, for any>0. The last two families of graphs are also enumerated by their numbers of edges. The proofs use the saddle point method applied to appropriaten-dimensional integrals.     

The Number Of Orientations Having No Fixed Tournament

Let T be a fixed tournament on k vertices. Let D(n,T ) denote the maximum number of orientations of an n-vertex graph that have no copy of T. We prove that for all sufficiently (very) large n, where t_k−1(n) is the maximum possible number of edges of a graphon n vertices with no K_k, (determined by Turán’s Theorem). The proof is based on a directed version of Szemerédi’s regularity lemma together with some additional ideas and tools from Extremal Graph Theory, and provides an example of a precise result proved by applying this lemma. For the two possible tournaments with three vertices we obtain separate proofs that avoid the use of the regularity lemma and therefore show that in these cases already holds for (relatively) small values of n. * Research supported in part by a USA Israeli BSF grant, by a grant from the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University.     

A modified Schwarz–Christoffel mapping for regions with piecewise smooth boundaries

A method where polygon corners in Schwarz–Christoffel mappings are rounded, is used to construct mappings from the upper half-plane to regions bounded by arbitrary piecewise smooth curves. From a given curve, a polygon is constructed by taking tangents to the curve in a number of carefully chosen so-called tangent points. The Schwarz–Christoffel mapping for that polygon is then constructed and modified to round the corners.     

Forests and score vectors

Thescore vector of a labeled digraph is the vector of out-degrees of its vertices. LetG be a finite labeled undirected graph without loops, and let σ(G) be the set of distinct score vectors arising from all possible orientations ofG. Let ϕ(G) be the set of subgraphs ofG which are forests of labeled trees. We display a bijection between σ(G) and ϕ(G). Supported in part by ONR Contract N00014-76-C-0366.     

Nilpotent sign patterns of a given index

A sign pattern is said to be nilpotent of index k if all real matrices in its qualitative class are nilpotent and their maximum nilpotent index equals k. In this paper, we characterize sign patterns that are nilpotent of a given index k. The maximum number of nonzero entries in such sign patterns of a given order is determined as well as the sign patterns with this maximum number of nonzero entries.     

Noncommutative symmetric functions and an amazing matrix

We present a simple way to derive the results of Diaconis and Fulman [P. Diaconis, J. Fulman, Foulkes characters, Eulerian idempotents, and an amazing matrix, arXiv:1102.5159] in terms of noncommutative symmetric functions.     

Character theory of symmetric groups, subgroup growth of Fuchsian groups, and random walks

We develop a number of statistical aspects of symmetric groups (mostly dealing with the distribution of cycles in various subsets of Sn), asymptotic properties of (ordinary) characters of symmetric groups, and estimates for the multiplicities of root number functions of these groups. As main applications, we present an estimate for the subgroup growth of an arbitrary Fuchsian group, a finiteness result for the number of Fuchsian presentations of such a group (resolving a long-standing problem of Roger Lyndon), as well as a proof of a well-known conjecture of Roichman concerning the mixing time of random walks on symmetric groups.     

Multipartite Moore digraphs

We derive some Moore-like bounds for multipartite digraphs, which extend those of bipartite digraphs, under the assumption that every vertex of a given partite set is adjacent to the same number δ of vertices in each of the other independent sets. We determine when a multipartite Moore digraph is weakly distance-regular. Within this framework, some necessary conditions for the existence of a r-partite Moore digraph with interpartite outdegree δ > 1 and diameter k = 2m are obtained. In the case δ = 1, which corresponds to almost Moore digraphs, a necessary condition in terms of the permutation cycle structure is derived. Additionally, we present some constructions of dense multipartite digraphs of diameter two that are vertex-transitive.     

Conjugation in Brauer algebras and applications to character theory

The Brauer algebra has a basis of diagrams and these generate a monoid H consisting of scalar multiples of diagrams. Following a recent paper by Kudryavtseva and Mazorchuk, we define and completely determine three types of conjugation in H. We are thus able to define Brauer characters for Brauer algebras which share many of the properties of Brauer characters defined for finite groups over a field of prime characteristic. Furthermore, we reformulate and extend the theory of characters for Brauer algebras as introduced by Ram to the case when the Brauer algebra is not semisimple.     

On the asymptotic convergence of sequences of analytic functions

We consider sequences {f _n } of analytic self mappings of a domain and the associated sequence {Θ _n } of inner compositions given by . The case of interest in this paper concerns sequences {f _n } that converge assymptotically to a function f, in the sense that for any sequence of integers {n _k } with n ₁ < n ₂ < ... one has that locally uniformly in Ω. Most of the discussion concerns the case where the asymptotic limit f is the identity function in Ω. Received: 16 December 2006     

Minimal Bar Tableaux

Motivated by recent results of Stanley, we generalize the rank of a partition λ to the rank of a shifted partition S(λ). We show that the number of bars required in a minimal bar tableau of S(λ) is max(o, e + (ℓ(λ) mod 2)), where o and e are the number of odd and even rows of λ. As a consequence we show that the irreducible projective characters of S_n vanish on certain conjugacy classes. Another corollary is a lower bound on the degree of the terms in the expansion of Schur’s Q_λ symmetric functions in terms of the power sum symmetric functions. Received November 20, 2003     

On a property ofn-edge-connected digraphs

It is proved that for every pair of verticesx, y in a finiten-edge-connected digraphD there is such a pathP fromx toy that the digraphD′ arising fromD by deleting the edges ofP is (n−1)-edge-connected.     

Coincidences among skew Schur functions

New sufficient conditions and necessary conditions are developed for two skew diagrams to give rise to the same skew Schur function. The sufficient conditions come from a variety of new operations related to ribbons (also known as border strips or rim hooks). The necessary conditions relate to the extent of overlap among the rows or among the columns of the skew diagram.     

On a subalgebra of the centre of a group ring II

Let p be a prime, G a finite group with p | |G| and F a field of characteristic p. By we denote the F-subspace of the centre of the group ring FG spanned by the p-regular conjugacy class sums. J. Murray proved that is an algebra, if G is a symmetric or alternating group. This can be used for the computation of the block idempotents of FG. We proved that is an algebra if the Sylow-p-subgroups of G are abelian. Recently, Y. Fan and B. Külshammer generalized this result to blocks with abelian defect groups. Here, we show that is an algebra if the Sylow-2-subgroups of G are dihedral. Therefore and are algebras for all primes p and all prime powers q. Furthermore we prove that is an algebra for the simple Suzuki-groups Sz(q), where q is a certain power of 2 and p is an arbitrary prime dividing |Sz(q)|. Received: 18 May 2007