Grundy number and products of graphs

The Grundy number of a graph G, denoted by Γ(G), is the largest k such that G has a greedyk-colouring, that is a colouring with k colours obtained by applying the greedy algorithm according to some ordering of the vertices of G. In this paper, we study the Grundy number of the lexicographic and cartesian products of two graphs in terms of the Grundy numbers of these graphs.Regarding the lexicographic product, we show that Γ(G)×Γ(H)≤Γ(G[H])≤2^Γ(G)−1(Γ(H)−1)+Γ(G). In addition, we show that if G is a tree or Γ(G)=Δ(G)+1, then Γ(G[H])=Γ(G)×Γ(H). We then deduce that for every fixed c≥1, given a graph G, it is CoNP-Complete to decide if Γ(G)≤c×χ(G) and it is CoNP-Complete to decide if Γ(G)≤c×ω(G).Regarding the cartesian product, we show that there is no upper bound of Γ(G□H) as a function of Γ(G) and Γ(H). Nevertheless, we prove that Γ(G□H)≤Δ(G)⋅2^Γ(H)−1+Γ(H).     

On the ratios between packing and domination parameters of a graph

The relationship ρ_L(G)≤ρ(G)≤γ(G) between the lower packing number ρ_L(G), the packing number ρ(G) and the domination number γ(G) of a graph G is well known. In this paper we establish best possible bounds on the ratios of the packing numbers of any (connected) graph to its six domination-related parameters (the lower and upper irredundance numbers ir and IR, the lower and upper independence numbers i and β, and the lower and upper domination numbers γ and Γ). In particular, best possible constants a_θ, b_θ, c_θ and d_θ are found for which the inequalities and hold for any connected graph G and all θ∈{ir,γ,i,β,Γ,IR}. From our work it follows, for example, that and for any connected graph G, and that these inequalities are best possible.     

Bounds for the spectral abscissa of an element in a Banach algebra

For an arbitrary element x with spectrum sp(x) in a Banach algebra with identity e ≠ 0 we define the upper (lower) spectral abscissa \(\mathop {\sigma + (x)}\limits_{( - )} = \mathop {\max }\limits_{(\min )} \operatorname{Re} \lambda ,\lambda \in sp(x)\) . With the aid of the spectral radius \(\rho (x) = \mathop {\max }\limits_{\lambda \in sp(x)} \left| \lambda \right| = \mathop {\lim }\limits_{n \to + \infty } \parallel x^n {{1 - } \mathord{\left/ {\vphantom {{1 - } n}} \right. \kern-0em} n}\) we prove the following bounds: γ_?(x)?σ_?(x)?Γ_?(x)?₊(x)?σ₊(x)?γ₊(x), Γ_(±)(x)=(2δ_(±))^?1 (ρ _δ ² )_(±)?δ _(±) ² ?ρ ₀ ² )(δ_(±)≠0), γ_(±)(x)= (±)ρ_δ(±)?δ_(±), δ₊?0, δ_??0 ρ _(±) ^δ = ρ(x+eδ_(±)). We mention a case where equality is achieved, some corollaries,and discuss the sharpness of the bounds: for every ? > 0 there is a δ: ¦δ¦ ≥ρ ₀ ² /2?, such that Δ: = ¦γ_(±) x?Γ_(±) x¦?ε and conversely, if the bounds are computed for some δ ≠ 0, then △ ≤ρ ₀ ² /2 ¦δ¦. An example is considered.     

A generalization of amenability and inner amenability of groups

Let G be a locally compact group. We continue our work [A. Ghaffari: Γ-amenability of locally compact groups, Acta Math. Sinica, English Series, 26 (2010), 2313–2324] in the study of Γ-amenability of a locally compact group G defined with respect to a closed subgroup Γ of G × G. In this paper, among other things, we introduce and study a closed subspace A _Γ ^p (G) of L ^∞(Γ) and then characterize the Γ-amenability of G using A _Γ ^p (G). Various necessary and sufficient conditions are found for a locally compact group to possess a Γ-invariant mean.     

Primitives and central detection numbers in group cohomology

Fix a prime p. Given a finite group G, let H^∗(G) denote its mod p cohomology. In the early 1990s, Henn, Lannes, and Schwartz introduced two invariants d₀(G) and d₁(G) of H^∗(G) viewed as a module over the mod p Steenrod algebra. They showed that, in a precise sense, H^∗(G) is respectively detected and determined by Hd(CG(V)) for d?d₀(G) and d?d₁(G), with V running through the elementary abelian p-subgroups of G.The main goal of this paper is to study how to calculate these invariants. We find that a critical role is played by the image of the restriction of H^∗(G) to H^∗(C), where C is the maximal central elementary abelian p-subgroup of G. A measure of this is the top degree e(G) of the finite dimensional Hopf algebra H^∗(C)_⊗H^∗(G)Fp, a number that tends to be quite easy to calculate.Our results are complete when G has a p-Sylow subgroup P in which every element of order p is central. Using the Benson-Carlson duality, we show that in this case, d₀(G)=d₀(P)=e(P), and a similar exact formula holds for d₁. As a bonus, we learn that He(G)(P) contains nontrivial essential cohomology, reproving and sharpening a theorem of Adem and Karagueuzian.In general, we are able to show that d₀(G)?max{e(CG(V))|V<G} if certain cases of Benson's Regularity Conjecture hold. In particular, this inequality holds for all groups such that the difference between the p-rank of G and the depth of H^∗(G) is at most 2. When we look at examples with p=2, we learn that d₀(G)?14 for all groups with 2-Sylow subgroup of order up to 64, with equality realized when G=SU(3,4).En route we study two objects of independent interest. If C is any central elementary abelian p-subgroup of G, then H^∗(G) is an H^∗(C)-comodule, and we prove that the subalgebra of H^∗(C)-primitives is always Noetherian of Krull dimension equal to the p-rank of G minus the p-rank of C. If the depth of H^∗(G) equals the rank of Z(G), we show that the depth essential cohomology of G is nonzero (reproving and extending a theorem of Green), and Cohen-Macauley in a certain sense, and prove related structural results.     

Rieffel deformation of homogeneous spaces

Let G₁⊂G be a closed subgroup of a locally compact group G and let X=G/G₁ be the quotient space of left cosets. Let X=(C₀(X),ΔX) be the corresponding G-C^∗-algebra where G=(C₀(G),Δ). Suppose that Γ is a closed abelian subgroup of G₁ and let Ψ be a 2-cocycle on the dual group . Let GΨ be the Rieffel deformation of G. Using the results of the previous paper of the author we may construct GΨ-C^∗-algebra XΨ - the Rieffel deformation of X. On the other hand we may perform the Rieffel deformation of the subgroup G₁ obtaining the closed quantum subgroup , which in turn, by the results of S. Vaes, leads to the GΨ-C^∗-algebra . In this paper we show that . We also consider the case where Γ⊂G is not a subgroup of G₁, for which we cannot construct the subgroup . Then generically XΨ cannot be identified with a quantum quotient. What may be shown is that it is a GΨ-simple object in the category of GΨ-C^∗-algebras.     

The trace class conjecture without the K-finiteness assumption

Let G be the group of real points of a reductive algebraic ℚ-group satisfying the same assumptions as in [5], Chapter I, and let Γ be a discrete subgroup of G. Let R_Γ be the right regular representation of G in L²(Γ\G). We prove in this Note that, for any integrable rapidly decreasing function ƒ on G, the restriction of R_Γ(ƒ) to the discrete spectrum of R_Γ is a trace class operator.     

The non-isolated vertices in the generating graph of a direct powers of simple groups

For a finite group G let Γ(G) denote the graph defined on the non-identity elements of G in such a way that two distinct vertices are connected by an edge if and only if they generate G. Many deep results on the generation of the finite simple groups G can be equivalently stated as theorems that ensure that Γ(G) is a rich graph, with several good properties. In this paper we want to consider Γ(G ^δ ) where G is a finite non-abelian simple group and G ^δ is the largest 2-generated power of G, with the aim to investigate whether the good generation properties of G still affect the behaviour of Γ(G ^δ ). In particular we prove that the graph obtained from Γ(G ^δ ) by removing the isolated vertices is 1-arc transitive and connected and we investigate the diameter of this graph. Moreover, some intriguing open questions will be introduced and their solutions will be exemplified for $G=\operatorname{Alt}(5)$ .     

On an approximation property for nondiscrete inequivalent representations of finitely generated groups

Let R(Γ, G) be the variety of representations of a finitely generated group Γ in a simple complex algebraic group G. We establish some sufficient conditions for the image of the diagonal representation ϱ = (ϱ₁, …, ϱ_t), ϱ_i ε R(Γ, G), to be dense in G^f in the complex topology (“weak approximation”).     

A lower bound for the packing chromatic number of the Cartesian product of cycles

Let G = (V, E) be a simple graph of order n and i be an integer with i ≥ 1. The set X _i ? V(G) is called an i-packing if each two distinct vertices in X _i are more than i apart. A packing colouring of G is a partition X = {X ₁, X ₂, …, X _k } of V(G) such that each colour class X _i is an i-packing. The minimum order k of a packing colouring is called the packing chromatic number of G, denoted by χ_ρ(G). In this paper we show, using a theoretical proof, that if q = 4t, for some integer t ≥ 3, then 9 ≤ χ_ρ(C ₄ □ C _q ). We will also show that if t is a multiple of four, then χ_ρ(C ₄ □ C _q ) = 9.     

Submodules of the groupoidC-algebra

Given an r-discrete, principal and amenable groupoid, the bijective correspondence between the family c the closedC _o(G ⁰)-bimodules ofC(G) and the family of the open subsets of the groupoidG is established. More over they are rigidity.     

Complementation and decompositions in some weakly Lindelöf Banach spaces

Let Γ denote an uncountable set. We consider the questions if a Banach space X of the form C(K) of a given class (1) has a complemented copy of c₀(Γ) or (2) for every c₀(Γ)⊆X has a complemented c₀(E) for an uncountable E⊆Γ or (3) has a decomposition X=A⊕B where both A and B are nonseparable. The results concern a superclass of the class of nonmetrizable Eberlein compacts, namely Ks such that C(K) is Lindelöf in the weak topology and we restrict our attention to Ks scattered of countable height. We show that the answers to all these questions for these C(K)s depend on additional combinatorial axioms which are independent of ZFC ± CH. If we assume the P-ideal dichotomy, for every c₀(Γ)⊆C(K) there is a complemented c₀(E) for an uncountable E⊆Γ, which yields the positive answer to the remaining questions. If we assume ♣, then we construct a nonseparable weakly Lindelöf C(K) for K of height ω+1 where every operator is of the form cI+S for c∈R and S with separable range and conclude from this that there are no decompositions as above which yields the negative answer to all the above questions. Since, in the case of a scattered compact K, the weak topology on C(K) and the pointwise convergence topology coincide on bounded sets, and so the Lindelöf properties of these two topologies are equivalent, many results concern also the space Cp(K).     

Transformation de Fourier des distributions de type positif sur un groupe de Lie unimodulaire

Call a locally compact group G, C¹-unique, if L¹(G) has exactly one (separating) C¹-norm. It is easy to see that a ¹-regular group G is C¹-unique and that a C¹-unique group is amenable. For connected groups G it is proved that G is C¹-unique, if the interior R(G)⁰ of a certain part R(G) of Prim(G), called the regular part of Prim(G), is dense in Prim(G), and that C¹-uniqueness of G implies the density of R(G) in Prim(G). From this it is derived that a connected group of type I is C¹-unique if and only if R(G)⁰ is dense in Prim(G). For exponential G, a quite explicit version of this result in terms of the Lie algebra of G is given. As an easy consequence, examples of amenable groups, which are not C¹-unique, and C¹-unique groups, which are not ¹-regular are obtained. Furthermore it is shown that a connected locally compact group G is amenable if and only if L¹(G) has exactly one C¹-norm, which is invariant under the isometric ¹-automorphisms of L¹(G).     

Krull’s theory for the double gamma function

The Barnes’ G-function G(x) = 1/Γ₂, satisfies the functional equation logG(x + 1) − logG(x) = logΓ(x). We complement W. Krull’s work in Bemerkungen zur Differenzengleichung g(x + 1) − g(x) = φ(x), Math. Nachrichten 1 (1948), 365-376 with additional results that yield a different characterization of the function G, new expansions and sharp bounds for G on x > 0 in terms of Gamma and Digamma functions, a new expansion for the Gamma function and summation formulae with Polygamma functions.     

The E-theoretic descent functor for groupoids

The paper establishes, for a wide class of locally compact groupoids Γ, the E-theoretic descent functor at the C^∗-algebra level, in a way parallel to that established for locally compact groups by Guentner, Higson and Trout. Section 2 shows that Γ-actions on a C₀(X)-algebra B, where X is the unit space of Γ, can be usefully formulated in terms of an action on the associated bundle B^?. Section 3 shows that the functor B→C^∗(Γ,B) is continuous and exact, and uses the disintegration theory of J. Renault. Section 4 establishes the existence of the descent functor under a very mild condition on Γ, the main technical difficulty involved being that of finding a Γ-algebra that plays the role of Cbcont(T,B) in the group case.     

The completeness of systems of functions of the Mittag-Leffler type for weighted uniform approximation in a complex domain

For a givenρ(1/2 <ρ < + ∞) let us set L _ρ = {z: |arg z| = π/(2ρ)} and assume that a real valued measurable function ?(t) such that ?(t) ≥ 1(t ∈ L _ρ ) and \(\mathop {\lim }\limits_{|t| \to + \infty } \varphi (t) = + \infty (t \in L_\rho )\) is defined on L _ρ . Let C _? (L _ρ ) denote the space of continuous functionsf(t) on L _ρ such that \(\lim \tfrac{{f(t)}}{{\varphi (t)}} = 0\) , where the norm of an elementf is defined as: \(\parallel f\parallel = \mathop {\sup }\limits_{t \in L_\rho } \tfrac{{|f(t)|}}{{\varphi (t)}}\) . In this note we pose the question about the completeness of the system of functions of the Mittag-Leffler type {Eρ(ut; μ)} (μ ≥ 1, 0 ≤ u ≤a) or, what is the same thing, of the system of functions \(p(t) = \int_0^a {E_\rho (ut;\mu )d\sigma (u)} \) in C _? (L _ρ ). The following theorem is proved: The system of functions of the Mittag-Leffler type is complete in C _? (L _ρ ) if and only if sup |p(z)| ≡ +∞, z ∈ L _ρ , where the supremum is taken over the set of functions p(t) such that ∥p(t) (t + 1)^?1 ∥ ≤ 1.     

Root Sublattices and Torus-Restriction of Prehomogeneous Vector Spaces Associated with Dynkin Quivers

For a Dynkin quiver Γ with r vertices, a subset S of the vertices of Γ, and an r-tuple d = (d⁽¹⁾, d⁽²⁾,…, d^(r)) of positive integers, we define a “torus-restricted” representation (G_S, R _d (Γ)) in natural way. Here we put G_S = G₁ × G₂ × … ×G_r, where each G_i is either SL(d⁽ⁱ⁾) or GL(d⁽ⁱ⁾) according to S containing i or not. In this paper, for a prescribed torus-restriction S, we give a necessary and sufficient condition on d that R _d (Γ) has only finitely many G_S-orbits. This can be paraphrased as a condition whether or not d is contained in a certain lattice spanned by positive roots of Γ. We also discuss the prehomogeneity of (G_S, R _d (Γ)).     

Invariant subspaces of some function spaces on a locally compact group

Let G be a σ-compact and locally compact group. If f?L^∞(G) let U_f be the closed subspace of L^∞(G) generated by the left translations of f. Conditions are given which ensure that each function in U_f may be expanded in an essentially unique way as an absolutely convergent series of translations of f. In this case U_f contains subspaces which are isometrically isomorphic to l¹. If G is metrizable and nondiscrete there is a continuum Γ in L^∞(G) such that, for each f?Γ, U_f contains no non-zero continuous function, and for f, g?Γ with f ≠ g, U_f ∩ U_g = {0}. If G is non-compact, metrizable, and non-discrete there is a continuum Γ of bounded continuous functions on G such that, for each f?Γ, U_f contains no non-zero left uniformly continuous function, and for f, g?Γ with f ≠ g, U_f ∩ U_g = {0}. The subspaces U_f above are translation invariant but are not convolution invariant.     

Zero-divisor semigroups and refinements of a star graph

Let G be a refinement of a star graph with center c. Let be the subgraph of G induced on the vertex set V(G)?{c or end vertices adjacent to c}. In this paper, we completely determine the structure of commutative zero-divisor semigroups S whose zero-divisor graph G=Γ(S) and S satisfy one of the following properties: (1) has at least two connected components, (2) is a cycle graph C_n of length n≥5, (3) is a path graph P_n with n≥6, (4) S is nilpotent and Γ(S) is a finite or an infinite star graph. For any finite or infinite cardinal number n≥2, we prove that for any nilpotent semigroup S with zero element 0, S⁴=0 if Γ(S) is a star graph K_1,n. We prove that there is exactly one nilpotent semigroup S such that S³≠0 and Γ(S)≅K_1,n. For several classes of finite graphs G which are refinements of a star graph, we also obtain formulas to count the number of non-isomorphic corresponding semigroups.