Profinite groups with nonabelian crowns of bounded rank and their probabilistic zeta function

It has been conjectured by Mann that the infinite sum Σ _H μ(H,G)/|G:H| ^s , where H ranges over all open subgroups of a finitely generated profinite group G, converges absolutely in some half right plane if G is positively finitely generated. We prove that the conjecture is true if the nonabelian crowns of G have bounded rank. In particular Mann’s conjecture holds if G has polynomial subgroup growth or is an adelic profinite group.     

The Virtual Poincaré Polynomials of Homogeneous Spaces

We factor the virtual Poincaré polynomial of every homogeneous space G/H, where G is a complex connected linear algebraic group and H is an algebraic subgroup, as t^2u (t²–1)^r Q_G/H(t²) for a polynomial Q_G/H with nonnegative integer coefficients. Moreover, we show that Q_G/H(t²) divides the virtual Poincaré polynomial of every regular embedding of G/H, if H is connected.     

Riesz transforms on a solvable Lie group of polynomial growth

We study Riesz transforms associated with a sublaplacian H on a solvable Lie group G, where G has polynomial volume growth. It is known that the standard second order Riesz transforms corresponding to H are generally unbounded in L^p(G). In this paper, we establish boundedness in L^p for modified second order Riesz transforms, which are defined using derivatives on a nilpotent group G_N associated with G. Our method utilizes a new algebraic approach which associates a distinguished choice of Cartan subalgebra with the sublaplacian H. We also obtain estimates for higher derivatives of the heat kernel of H, and give a new proof (without the use of homogenization theory) of the boundedness of first order Riesz transforms. Our results can be generalized to an arbitrary (possibly non-solvable) Lie group of polynomial growth.     

NP-hardness of the recognition of coordinated graphs

A graph G is coordinated if the minimum number of colors that can be assigned to the cliques of H in such a way that no two cliques with non-empty intersection receive the same color is equal to the maximum number of cliques of H with a common vertex, for every induced subgraph H of G. In previous works, polynomial time algorithms were found for recognizing coordinated graphs within some classes of graphs. In this paper we prove that the recognition problem for coordinated graphs is NP-hard, and it is NP-complete even when restricted to the class of {gem, C ₄, odd hole}-free graphs with maximum degree four, maximum clique size three and at most three cliques sharing a common vertex. F.J. Soulignac is partially supported by UBACyT Grant X184, Argentina and CNPq under PROSUL project Proc. 490333/2004-4, Brazil.     

On growth,recurrence and the Choquet-Deny Theorem for <Emphasis Type="Italic">p</Emphasis>-adic Lie groups

We first study the growth properties of p-adic Lie groups and its connection with p-adic Lie groups of type R and prove that a non-type R p-adic Lie group has compact neighbourhoods of identity having exponential growth. This is applied to prove the growth dichotomy for a large class of p-adic Lie groups which includes p-adic algebraic groups. We next study p-adic Lie groups that admit recurrent random walks and prove the natural growth conjecture connecting growth and the existence of recurrent random walks, precisely we show that a p-adic Lie group admits a recurrent random walk if and only if it has polynomial growth of degree at most two. We prove this conjecture for some other classes of groups also. We also prove the Choquet-Deny Theorem for compactly generated p-adic Lie groups of polynomial growth and also show that polynomial growth is necessary and sufficient for the validity of the Choquet-Deny for all spread-out probabilities on Zariski-connected p-adic algebraic groups. Counter example is also given to show that certain assumptions made in the main results can not be relaxed.     

On reflecting diffusion processes and Skorokhod decompositions

Summary LetG be ad-dimensional bounded Euclidean domain, H¹ (G) the set off in L²(G) such that f (defined in the distribution sense) is in L²(G). Reflecting diffusion processes associated with the Dirichlet spaces (H¹(G), ) on L²(G, dx) are considered in this paper, where A=(a^ij is a symmetric, bounded, uniformly ellipticd×d matrix-valued function such thata ^ij H¹(G) for eachi,j, and H¹(G) is a positive bounded function onG which is bounded away from zero. A Skorokhod decomposition is derived for the continuous reflecting Markov processes associated with (H¹(G), ) having starting points inG under a mild condition which is satisfied when G has finite (d–1)-dimensional lower Minkowski content.     

Contracting planar graphs to contractions of triangulations

For every graph H, there exists a polynomial-time algorithm deciding if a planar input graph G can be contracted to H. However, the degree of the polynomial depends on the size of H. We identify a class of graphs C such that for every fixed H∈C, there exists a linear-time algorithm deciding whether a given planar graph G can be contracted to H. The class C is the closure of planar triangulated graphs under taking of contractions. In fact, we prove that a graph H∈C if and only if there exists a constant cH such that if the treewidth of a graph is at least cH, it contains H as a contraction. We also provide a characterization of C in terms of minimal forbidden contractions.     

Packing and covering dense graphs

Let d be a positive integer. A graph G is called d-divisible if d divides the degree of each vertex of G. G is called nowhere d-divisible if no degree of a vertex of G is divisible by d. For a graph H, gcd(H) denotes the greatest common divisor of the degrees of the vertices of H. The H-packing number of G is the maximum number of pairwise edge disjoint copies of H in G. The H-covering number of G is the minimum number of copies of H in G whose union covers all edges of G. Our main result is the following: For every fixed graph H with gcd(H) = d, there exist positive constants ϵ(H) and N(H) such that if G is a graph with at least N(H) vertices and has minimum degree at least (1 − ϵ(H))|G|, then the H-packing number of G and the H-covering number of G can be computed in polynomial time. Furthermore, if G is either d-divisible or nowhere d-divisible, then there is a closed formula for the H-packing number of G, and the H-covering number of G. Further extensions and solutions to related problems are also given. © 1998 John Wiley & Sons, Inc. J Combin Designs 6: 451–472, 1998     

On the b-Coloring of Cographs and <Emphasis Type="Italic">P</Emphasis><Subscript>4</Subscript>-Sparse Graphs

A b-coloring of a graph is a coloring such that every color class admits a vertex adjacent to at least one vertex receiving each of the colors not assigned to it. The b-chromatic number of a graph G, denoted by χ _b (G), is the maximum number t such that G admits a b-coloring with t colors. A graph G is b-continuous if it admits a b-coloring with t colors, for every . We define a graph G to be b-monotonic if χ _b (H ₁) ≥ χ _b (H ₂) for every induced subgraph H ₁ of G, and every induced subgraph H ₂ of H ₁. In this work, we prove that P ₄-sparse graphs (and, in particular, cographs) are b-continuous and b-monotonic. Besides, we describe a dynamic programming algorithm to compute the b-chromatic number in polynomial time within these graph classes. Flavia Bonomo: Partially supported by ANPCyT PICT-2007-00533 and PICT-2007-00518, and UBACyT Grants X069 and X606 (Argentina). Guillermo Durán: Partially supported by FONDECyT Grant 1080286 and Millennium Science Institute “Complex Engineering Systems” (Chile), and ANPCyT PICT-2007-00518 and UBACyT Grant X069 (Argentina). Javier Marenco: Partially supported by ANPCyT PICT-2007-00518 and UBACyT Grant X069 (Argentina).     

On solubility and supersolubility of some classes of finite groups

Let G be a finite group and H a subgroup of G. Then H is said to be S-permutable in G if HP = PH for all Sylow subgroups P of G. Let HsG be the subgroup of H generated by all those subgroups of H which are S-permutable in G. Then we say that H is S-embedded in G if G has a normal subgroup T and an S-permutable subgroup C such that T ∩ H HsG and HT = C. Our main result is the following Theorem A. A group G is supersoluble if and only if for every non-cyclic Sylow subgroup P of the generalized Fitting subgrou...     

On s-quasinormal and c-normal subgroups of a finite group

Let F be a saturated formation containing the class of supersolvable groups and let G be a finite group. The following theorems are shown： （1） G ∈ F if and only if there is a normal subgroup H such that G/H ∈ F and every maximal subgroup of all Sylow subgroups of H is either c-normal or s-quasinormally embedded in G; （2） G ∈F if and only if there is a soluble normal subgroup H such that G/H∈F and every maximal subgroup of all Sylow subgroups of F（H）, the Fitting subgroup of H, is either e-normally or s-quasinormally embedded in G.     

Metric properties on Lie groups of polynomial volume growth

It is well known that we have an algebraic characterization of connected Lie groups of polynomial volume growth: a Lie group G has polynomial volume growth if and only if it is of type R. In this paper, we shall give a geometric characterization of connected Lie groups of polynomial volume growth in terms of the distance distortion of the subgroups. More precisely, we prove that a connected Lie group G has polynomial volume growth if and only if every closed subgroup has a polynomial distortion in G.     

Bi‐arc graphs and the complexity of list homomorphisms

Given graphs G, H, and lists L(v) ? V(H), v ε V(G), a list homomorphism of G to H with respect to the lists L is a mapping f : V(G) → V(H) such that uv ε E(G) implies f(u)f(v) ε E(H), and f(v) ε L(v) for all v ε V(G). The list homomorphism problem for a fixed graph H asks whether or not an input graph G, together with lists L(v) ? V(H), v ε V(G), admits a list homomorphism with respect to L. In two earlier papers, we classified the complexity of the list homomorphism problem in two important special cases: When H is a reflexive graph (every vertex has a loop), the problem is polynomial time solvable if H is an interval graph, and is NP‐complete otherwise. When H is an irreflexive graph (no vertex has a loop), the problem is polynomial time solvable if H is bipartite and H is a circular arc graph, and is NP‐complete otherwise. In this paper, we extend these classifications to arbitrary graphs H (each vertex may or may not have a loop). We introduce a new class of graphs, called bi‐arc graphs, which contains both reflexive interval graphs (and no other reflexive graphs), and bipartite graphs with circular arc complements (and no other irreflexive graphs). We show that the problem is polynomial time solvable when H is a bi‐arc graph, and is NP‐complete otherwise. In the case when H is a tree (with loops allowed), we give a simpler algorithm based on a structural characterization. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 61–80, 2003     

On capability of finite abelian groups

Baer characterized capable finite abelian groups (a group is capable if it is isomorphic to the group of inner automorphisms of some group) by a condition on the size of the factors in the invariant factor decomposition (the group must be noncyclic and the top two invariant factors must be equal). We provide a different characterization, given in terms of a condition on the lattice of subgroups. Namely, a finite abelian group G is capable if and only if there exists a family {H _i } of subgroups of G with trivial intersection, such that the union generates G and all quotients G/H _i have the same exponent. Other variations of this condition are also provided (for instance, the condition that the union generates G can be replaced by the condition that it is equal to G). The work presented here is partially supported by NSF/DMS-0805932.     

On the chromatic spectrum of acyclic decompositions of graphs

If G is any graph, a G‐decomposition of a host graph H = (V, E) is a partition of the edge set of H into subgraphs of H which are isomorphic to G. The chromatic index of a G‐decomposition is the minimum number of colors required to color the parts of the decomposition so that two parts which share a node get different colors. The G‐spectrum of H is the set of all chromatic indices taken on by G‐decompositions of H. If both S and T are trees, then the S‐spectrum of T consists of a single value which can be computed in polynomial time. On the other hand, for any fixed tree S, not a single edge, there is a unicyclic host whose S‐spectrum has two values, and if the host is allowed to be arbitrary, the S‐spectrum can take on arbitrarily many values. Moreover, deciding if an integer k is in the S‐spectrum of a general bipartite graph is NP‐hard. We show that if G has c > 1 components, then there is a host H whose G‐spectrum contains both 3 and 2c + 1. If G is a forest, then there is a tree T whose G‐spectrum contains both 2 and 2c. Furthermore, we determine the complete spectra of both paths and cycles with respect to matchings. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 83–104, 2007     

On complemented subgroups of finite groups

A subgroup H of a group G is said to be complemented in G if there exists a subgroup K of G such that G = HK and H ⋂ K = 1. In this paper we determine the structure of finite groups with some complemented primary subgroups, and obtain some new results about p-nilpotent groups.     

Properties of random walks on discrete groups: Time regularity and off-diagonal estimates

In this paper we study some properties of the convolution powers K(n)=K∗K∗?∗K of a probability density K on a discrete group G, where K is not assumed to be symmetric. If K is centered, we show that the Markov operator T associated with K is analytic in Lp(G) for 1<p<∞, and prove Davies-Gaffney estimates in L² for the iterated operators Tn. This enables us to obtain Gaussian upper bounds for the convolution powers K(n). In case the group G is amenable, we discover that the analyticity and Davies-Gaffney estimates hold if and only if K is centered. We also estimate time and space differences, and use these to obtain a new proof of the Gaussian estimates with precise time decay in case G has polynomial volume growth.     

List Homomorphisms and Circular Arc Graphs

G , H, and lists , a list homomorphism of G to H with respect to the lists L is a mapping , such that for all , and for all . The list homomorphism problem for a fixed graph H asks whether or not an input graph G together with lists , , admits a list homomorphism with respect to L. We have introduced the list homomorphism problem in an earlier paper, and proved there that for reflexive graphs H (that is, for graphs H in which every vertex has a loop), the problem is polynomial time solvable if H is an interval graph, and is NP-complete otherwise. Here we consider graphs H without loops, and find that the problem is closely related to circular arc graphs. We show that the list homomorphism problem is polynomial time solvable if the complement of H is a circular arc graph of clique covering number two, and is NP-complete otherwise. For the purposes of the proof we give a new characterization of circular arc graphs of clique covering number two, by the absence of a structure analogous to Gallai's asteroids. Both results point to a surprising similarity between interval graphs and the complements of circular arc graphs of clique covering number two. Received: July 22, 1996/Revised: Revised June 10, 1998     

Variations on polynomial subgroup growth

A groupG hasweak polynomial subgroup growth (wPSG) of degree ≤α if each finite quotient Ḡ ofG contains at most │Ḡ│ ^a subgroups. The main result is that wPSG of degree α implies polynomial subgroup growth (PSG) of degree at mostf(α). It follows that wPSG is equivalent to PSG. A corollary is that if, in a profinite groupG, thek-generator subgroups have positive “density” δ, thenG is finitely generated (the number of generators being bounded by a function ofk and δ).     

Cancellation and absorption of lexicographic powers of totally ordered Abelian groups

Let G and H be totally ordered Abelian groups such that, for some integer k, the lexicographic powers G ^k and H ^k are isomorphic (as ordered groups). It was proved by F. Oger that G and H need not be isomorphic. We show here that they are whenever G is either divisible or ₁ -saturated (and in a few more cases). Our proof relies on a general technique which we also use to prove that G and H must be elementary equivalent as ordered groups (a fact also proved by F. Delon and F. Lucas) and isomorphic as chains. The same technique applies to the question of whether G and H should be isomorphic as groups, but, in this last case, no hint about a possible negative answer seems available.