The continuum limit of critical random graphs

We consider the Erd?s–Rényi random graph G(n, p) inside the critical window, that is when p?=?1/n?+?λn ^?4/3, for some fixed ${\lambda \in \mathbb{R}}$ . We prove that the sequence of connected components of G(n, p), considered as metric spaces using the graph distance rescaled by n ^?1/3, converges towards a sequence of continuous compact metric spaces. The result relies on a bijection between graphs and certain marked random walks, and the theory of continuum random trees. Our result gives access to the answers to a great many questions about distances in critical random graphs. In particular, we deduce that the diameter of G(n, p) rescaled by n ^?1/3 converges in distribution to an absolutely continuous random variable with finite mean.     

On the tensor square of non-abelian nilpotent finite-dimensional Lie algebras

For every finite p-group G of order p ⁿ with derived subgroup of order p ^m , Rocco [N.R. Rocco, On a construction related to the nonabelian tensor square of a group, Bol. Soc. Brasil. Mat. 1 (1991), pp. 63–79] proved that the order of tensor square of G is at most p ^n(n?m). This upper bound has been improved recently by the author [P. Niroomand, On the order of tensor square of non abelian prime power groups (submitted)]. The aim of this article is to obtain a similar result for a non-abelian nilpotent Lie algebra of finite dimension. More precisely, for any given n-dimensional non-abelian nilpotent Lie algebra L with derived subalgebra of dimension m we have dim(L???L)?≤?(n???m)(n???1)?+?2. Furthermore for m?=?1, the explicit structure of L is given when the equality holds.     

On varieties arising from the solution of the Restricted Burnside Problem

For a family of group-words w we prove that the class of all groups G satisfying the identity wⁿ≡1 and having the verbal subgroup w(G) locally nilpotent is a variety.     

Isomorphisms,automorphisms, and generalized involution models of projective reflection groups

We investigate the generalized involution models of the projective reflection groups G(r, p, q, n). This family of groups parametrizes all quotients of the complex reflection groups G(r, p, n) by scalar subgroups. Our classification is ultimately incomplete, but we provide several necessary and sufficient conditions for generalized involution models to exist in various cases. In the process we solve several intermediate problems concerning the structure of projective reflection groups. We derive a simple criterion for determining whether two groups G(r, p, q, n) and G(r, p′, q′, n) are isomorphic. We also describe explicitly the form of all automorphisms of G(r, p, q, n), outside a finite list of exceptional cases. Building on prior work, this allows us to prove that G(r, p, 1, n) has a generalized involution model if and only if G(r, p, 1, n) ≌ G(r, 1, p, n). We also classify which groups G(r, p, q, n) have generalized involution models when n = 2, or q is odd, or n is odd.     

Relatively Free Nilpotent Torsion-Free Groups and Their Lie Algebras

Let K be a field of characteristic zero. For a torsion-free finitely generated nilpotent group G, we naturally associate four finite dimensional nilpotent Lie algebras over K, ? _K (G), grad^(?)(? _K (G)), grad^(g)(exp ? _K (G)), and L _K (G). Let 𝔗 _c be a torsion-free variety of nilpotent groups of class at most c. For a positive integer n, with n ≥ 2, let F _n (𝔗 _c ) be the relatively free group of rank n in 𝔗 _c . We prove that ? _K (F _n (𝔗 _c )) is relatively free in some variety of nilpotent Lie algebras, and ? _K (F _n (𝔗 _c )) ? L _K (F _n (𝔗 _c )) ? grad^(?)(? _K (F _n (𝔗 _c ))) ? grad^(g)(exp ? _K (F _n (𝔗 _c ))) as Lie algebras in a natural way. Furthermore, F _n (𝔗 _c ) is a Magnus nilpotent group. Let G ₁ and G ₂ be torsion-free finitely generated nilpotent groups which are quasi-isometric. We prove that if G ₁ and G ₂ are relatively free of finite rank, then they are isomorphic. Let L be a relatively free nilpotent Lie algebra over ? of finite rank freely generated by a set X. Give on L the structure of a group R, say, by means of the Baker–Campbell–Hausdorff formula, and let H be the subgroup of R generated by the set X. We show that H is relatively free in some variety of nilpotent groups; freely generated by the set X, H is Magnus and L ? ?_?(H) ? L _?(H) as Lie algebras. For relatively free residually torsion-free nilpotent groups, we prove that ? _K and L _K are isomorphic as Lie algebras. We also give an example of a finitely generated Magnus nilpotent group G, not relatively free, such that ?_?(G) is not isomorphic to L _?(G) as Lie algebras.     

Lie properties of symmetric elements in group rings II

Let F be a field of characteristic different from 2, and G a group with involution ∗. Write (FG)⁺ for the set of elements in the group ring FG that are symmetric with respect to the induced involution. Recently, Giambruno, Polcino Milies and Sehgal showed that if G has no 2-elements, and (FG)⁺ is Lie nilpotent (resp. Lie n-Engel), then FG is Lie nilpotent (resp. Lie m-Engel, for some m). Here, we classify the groups containing 2-elements such that (FG)⁺ is Lie nilpotent or Lie n-Engel.     

On Groups Generated by Elements of Pirme Order

In the first part of the paper we give a characterization of groups generated by elements of fixed prime order p. In the second part we study the group G _n ^(p) of n × n matrices with the pth power of the determinant equal to 1 over a field F containing a primitive pth root of 1. It is known that the group G _n ⁽²⁾ of n × n matrices of determinant ± 1 over a field F and the group SL _n (F) are generated by their involutions and that each element in these groups is a product of four involutions. We consider some subgroups G of G _n ^(p) and study the following problems: Is G generated by its elements of order p? If so, is every element of G a product of k elements of order p for some fixed integer k? We show that G _n ^(p) and SL _n (F) are generated by their elements of order p and that the bound k exists and is equal to 4. We show that every universal p-Coxeter group has faithful two-dimensional representations over many fields F (including ? and ?). For a universal p-Coxeter group of rank ≥ 2 for p ≥ 3 or of rank ≥ 3 for p = 2 there is no bound k.     

Lower bounds for the clique and the chromatic numbers of a graph

G is any simple graph with m edges and n vertices where these vertices have vertex degrees d(1)≥d(2)≥?≥d(n), respectively. General algorithms for the exact calculation of χ(G), the chromatic number of G, are almost always of ‘branch and bound’ type; this type of algorithm requires an easily constructed lower bound for χ(G). In this paper it is shown that, for a number of such bounds (many of which are described here for the first time), the bound does not exceed cl(G) where cl(G) is the clique number of G.In 1972 Myers and Liu showed that cl(G)≥n?(n?2m?n). Here we show that cl(G)≥ n?[n?(2m?n)(1+c²_v)^{$\text{1}\text{2}$}], where c_v is the vertex degree coefficient of variation in G, that cl(G)≥ Bondy's constructive lower bound for χ(G), and that cl(G)≥n?(n?W(G)), where W(G) is the largest positive integer such that W(G)≤d(W(G)+1) [W(G)+1 is the Welsh and Powell upper bound for χ(G)]. It is also shown that cl(G)+$\text{1}\text{3}$>n?(n?L(G))≥n?(n?λ₁) and that χ(G)≥ n?(n?λ₁); λ₁ is the largest eigenvalue of A, the adjacency matrix of G, and L(G) is a newly defined single-valued function of G similar to W(G) in its construction from the vertex degree sequence of G [L(G)≥W(G)].Finally, a ‘greedy’ lower bound for cl(G) is constructed from A and it is shown that this lower bound is never less than Bondy's bound; thereafter, for 150 random graphs with varying numbers of vertices and edge densities, the values of lower bounds given in this paper are listed, thereby illustrating that this last greedily obtained lower bound is almost always better than each of the other bounds.     

Generalized congruence properties of the restricted partition function p(n,m)

Ramanujan-type congruences for the unrestricted partition function p(n) are well known and have been studied in great detail. The existence of Ramanujan-type congruences are virtually unknown for p(n,m), the closely related restricted partition function that enumerates the number of partitions of n into exactly m parts. Let ? be any odd prime. In this paper we establish explicit Ramanujan-type congruences for p(n,?) modulo any power of that prime ? ^α . In addition, we establish general congruence relations for p(n,?) modulo ? ^α for any n.     

Classifying Hilbert bundles

A Hilbert bundle (p, B, X) is a type of fibre space p:B → X such that each fibre p^?1(x) is a Hilbert space. However, p^?1(x) may vary in dimension as x varies in X. We generalize the classical homotopy classification theory of vector bundles to a “homotopy” classification of certain Hilbert bundles. An (m, n)-bundle over the pair (X, A) is a Hilbert bundle (p, B, X) such that the dimension of p^?1(x) is m for x in A and n otherwise. The main result here is that if A is a compact set lying in the “edge” of the metric space X (e.g. if X is a topological manifold and A is a compact subset of the boundary of X), then the problem of classifying (m, n)-bundles over (X, A) reduces to a problem in the classical theory of vector bundles. In particular, we show there is a one-to-one correspondence between the members of the orbit set, [A, G_m($\text{C}$ⁿ)]/[X, U(n)] ¦ A, and the isomorphism classes of (m, n)-bundles over (X, A) which are trivial over X, A.     

Multicoloring and Mycielski construction

The generalized Mycielskians of graphs (also known as cones over graphs) are the natural generalization of the Mycielskians of graphs (which were first introduced by Mycielski in 1955). Given a graph G and any integer p?0, one can transform G into a new graph μ_p(G), the p-Mycielskian of G. In this paper, we study the kth chromatic numbers χ_k of Mycielskians and generalized Mycielskians of graphs. We show that χ_k(G)+1?χ_k(μ(G))?χ_k(G)+k, where both upper and lower bounds are attainable. We then investigate the kth chromatic number of Mycielskians of cycles and determine the kth chromatic number of p-Mycielskian of a complete graph K_n for any integers k?1, p?0 and n?2. Finally, we prove that if a graph G is a/b-colorable then the p-Mycielskian of G, μ_p(G), is (at+b^p+1)/bt-colorable, where . And thus obtain graphs G with m(G) grows exponentially with the order of G, where m(G) is the minimal denominator of a a/b-coloring of G with χ_f(G)=a/b.     

Topology of random clique complexes

In a seminal paper, Erd?s and Rényi identified a sharp threshold for connectivity of the random graph G(n,p). In particular, they showed that if p?logn/n then G(n,p) is almost always connected, and if p?logn/n then G(n,p) is almost always disconnected, as n→∞.The clique complexX(H) of a graph H is the simplicial complex with all complete subgraphs of H as its faces. In contrast to the zeroth homology group of X(H), which measures the number of connected components of H, the higher dimensional homology groups of X(H) do not correspond to monotone graph properties. There are nevertheless higher dimensional analogues of the Erd?s-Rényi Theorem.We study here the higher homology groups of X(G(n,p)). For k>0 we show the following. If p=n^α, with α<−1/k or α>−1/(2k+1), then the kth homology group of X(G(n,p)) is almost always vanishing, and if −1/k<α<−1/(k+1), then it is almost always nonvanishing.We also give estimates for the expected rank of homology, and exhibit explicit nontrivial classes in the nonvanishing regime. These estimates suggest that almost all d-dimensional clique complexes have only one nonvanishing dimension of homology, and we cannot rule out the possibility that they are homotopy equivalent to wedges of a spheres.     

Parity of the partition function

Although much is known about the partition function, little is known about its parity. For the polynomials D(x):=(Dx²+1)/24, where , we show that there are infinitely many m (resp. n) for which p(D(m)) is even (resp. p(D(n)) is odd) if there is at least one such m (resp. n). We bound the first m and n (if any) in terms of the class number h(−D). For prime D we show that there are indeed infinitely many even values. To this end we construct new modular generating functions using generalized Borcherds products, and we employ Galois representations and locally nilpotent Hecke algebras.     

Hopf Modules and Representations of Finite Wreath Products

For a finite group G and nonnegative integer n ≥ 0, one may consider the associated tower \(G \wr S_{n} := S_{n} \ltimes G^{n}\) of wreath product groups. Zelevinsky associated to such a tower the structure of a positive self-adjoint Hopf algebra (PSH-algebra) R(G) on the direct sum over integers n ≥ 0 of the Grothendieck groups K ₀(R e p?G?S _n ). In this paper, we study the interaction via induction and restriction of the PSH-algebras R(G) and R(H) associated to finite groups H ? G. A class of Hopf modules over PSH-algebras with a compatibility between the comultiplication and multiplication involving the Hopf k ^{t h} -power map arise naturally and are studied independently. We also give an explicit formula for the natural PSH-algebra morphisms R(H) → R(G) and R(G) → R(H) arising from induction and restriction. In an appendix, we consider a family of subgroups of wreath product groups analogous to the subgroups G(m, p, n) of the wreath product cyclotomic complex reflection groups G(m, 1, n).     

On n-Hamiltonian line graphs

With each nonempty graph G one can associate a graph L(G), called the line graph of G, with the property that there exists a one-to-one correspondence between E(G) and V(L(G)) such that two vertices of L(G) are adjacent if and only if the corresponding edges of G are adjacent. For integers m ≥ 2, the mth iterated line graph L^m(G) of G is defined to be L(L^m-1(G)). A graph G of order p ≥ 3 is n-Hamiltonian, 0 ≤ n ≤ p ? 3, if the removal of any k vertices, 0 ≤ k ≤ n, results in a Hamiltonian graph. It is shown that if G is a connected graph with δ(G) ≥ 3, where δ(G) denotes the minimum degree of G, then L²(G) is (δ(G) ? 3)-Hamiltonian. Furthermore, if G is 2-connected and δ(G) ≥ 4, then L²(G) is (2δ(G) ? 4)-Hamiltonian. For a connected graph G which is neither a path, a cycle, nor the graph K(1, 3) and for any positive integer n, the existence of an integer k such that L^m(G) is n-Hamiltonian for every m ≥ k is exhibited. Then, for the special case n = 1, bounds on (and, in some cases, the exact value of) the smallest such integer k are determined for various classes of graphs.     

Rectangular arrays

In this paper we studied m×n arrays with row sums $\text{nr}\text{(n,m)}$ and column sums $\text{mr}\text{(n,m)}$ where (n,m) denotes the greatest common divisor of m and n. We were able to show that the function H_m,n(r), which enumerates m×n arrays with row sums and column sums $\text{nr}\text{(m,n)}$ and $\text{mr}\text{(n,m)}$ respectively, is a polynomial in r of degree (m?1)(n?1). We found simple formulas to evaluate these polynomials for negative values, ?r, and we show that certain small negative integers are roots of these polynomials. When we considered the generating function G_m,n(y) = Σ_r?0H_m,n(r)y^r, it was found to be rational of degree less than zero. The denominator of G_m,n(y) is of the form (1?y)^(m?1)(n?1)+3, and the coefficients of the numerator are non-negative integers which enjoy a certain symmetric relation.     

The circular dimension of a graph

A graph is a pair (V, I), V being the vertices and I being the relation of adjacency on V. Given a graph G, then a collection of functions {f_i}^m_n=1, each f_i mapping each vertex of V into anarc on a fixed circle, is said to define an m-arc intersection model for G if for all x,y ? V, xly ? (∨_i?m)(f_i(x)∩f_i(y)≠Ø). The circular dimension of a graph G is defined as the smallest integer m such that G has an m-arc intersection model. In this paper we establish that the maximum circular dimension of any complete partite graph having n vertices is the largest integer p such that 2^p+p?n+1.     

Classifying Hilbert bundles. II

A Hilbert bundle (p, B, X) is a type of fibre space p: B → X such that each fibre p^?1(x) is a Hilbert space. However, p^?1(x) may vary in dimension as x varies in X, even when X is connected. We give two “homotopy” type classification theorems for Hilbert bundles having primarily finite dimensional fibres. An (m, n)-bundle over the pair (X, A) is a Hilbert bundle over (p, B, X) such that the dimension of p^?1(x) is m for x in A and n otherwise. As a special case, we show that if X is a compact metric space, C₊X the upper cone of the suspension SX, then the isomorphism classes of (m, n)-bundles over (SX, C₊X) are in one-to-one correspondence with the members of [X, V_m($\text{C}$ⁿ)] where V_m($\text{C}$ⁿ) is the Stiefel manifold. The results are all applicable to the classification of separable, continuous trace C¹-algebras, with specific results given to illustrate.     

On the Genus of the Nilpotent Graphs of Finite Groups

The nilpotent graph of a group G is a simple graph whose vertex set is G?nil(G), where nil(G) = {y ∈ G | ? x, y ? is nilpotent ? x ∈ G}, and two distinct vertices x and y are adjacent if ? x, y ? is nilpotent. In this article, we show that the collection of finite non-nilpotent groups whose nilpotent graphs have the same genus is finite, derive explicit formulas for the genus of the nilpotent graphs of some well-known classes of finite non-nilpotent groups, and determine all finite non-nilpotent groups whose nilpotent graphs are planar or toroidal.