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).     

The deformation theory of representations of fundamental groups of compact Kähler manifolds

Let Γ be the fundamental group of a compact Kähler manifold M and let G be a real algebraic Lie group. Let ?(Γ, G) denote the variety of representations Γ → G. Under various conditions on ρ ∈ ?(Γ, G) it is shown that there exists a neighborhood of ρ in ?(Γ, G) which is analytically equivalent to a cone defined by homogeneous quadratic equations. Furthermore this cone may be identified with the quadratic cone in the space \(Z^1 (\Gamma ,g_{Ad\rho } )\) of Lie algebra-valued l-cocycles on Γ comprising cocyclesu such that the cohomology class of the cup/Lie product square [u, u] is zero in \(H^2 (\Gamma ,g_{Ad\rho } )\) . We prove that ?(Γ, G) is quadratic at ρ if either (i) G is compact, (ii) ρ is the monodromy of a variation of Hodge structure over M, or (iii) G is the group of automorphisms of a Hermitian symmetric space X and the associated flat X-bundle over M possesses a holomorphic section. Examples are given where singularities of ?(Γ, G) are not quadratic, and are quadratic but not reduced. These results can be applied to construct deformations of discrete subgroups of Lie groups.     

Homogeneous almost normal Riemannian manifolds

In this article, we introduce a newclass of compact homogeneous Riemannian manifolds (M = G/H, µ) almost normal with respect to a transitive Lie group G of isometries for which by definition there exists a G-left-invariant and an H-right-invariant inner product ν such that the canonical projection p: (G, ν) → (G/H, µ) is a Riemannian submersion and the norm | · | of the product ν is at least the bi-invariant Chebyshev normon G defined by the space (M,µ).We prove the following results: Every homogeneous Riemannian manifold is almost normal homogeneous. Every homogeneous almost normal Riemannian manifold is naturally reductive and generalized normal homogeneous. For a homogeneous G-normal Riemannian manifold with simple Lie group G, the unit ball of the norm | · | is a Löwner-John ellipsoid with respect to the unit ball of the Chebyshev norm; an analogous assertion holds for the restrictions of these norms to a Cartan subgroup of the Lie group G. Some unsolved problems are posed.     

Stability of Discontinuous Groups Acting on Homogeneous Spaces

Suppose given a nilpotent connected simply connected Lie group G, a connected Lie subgroup H of G, and a discontinuous group Γ for the homogeneous space M = G/H. In this work we study the topological stability of the parameter space R(Γ,G,H) in the case where G is three-step. We prove a stability theorem for certain particular pairs (Γ,H). We also introduce the notion of strong stability on layers making use of an explicit layering of Hom(Γ,G) and study the case of Heisenberg groups.     

Globalization of Holomorphic Actions on Principal Bundles

Suppose G is a Lie group acting as a group of holomorphic automorphisms on a holomorphic principal bundle P → X. We show that if there is a holomorphic action of the complexification G^C of G on. X, this lifts to a holomorphic action of G^C on the bundle P → X. Two applications are presented. We prove that given any connected homogeneous complex manifold G/H with more than one end, the complexification G^C of G acts holomorphically and transitively on G/H. We also show that the ends of a homogeneous complex manifold G/H with more than two ends essentially come from a space of the form S/Γ, where Γ is a Zariski dense discrete subgroup of a semisimple complex Lie group S with S and Γ being explicitly constructed in terms of G and H.     

Tetravalent Edge-transitive Cayley Graphs of PGL （2, p）

t Let F = Cay（G, S）, R（G） be the right regular representation of G. The graph Г is called normal with respect to G, if R（G） is normal in the full automorphism group Aut（F） of F. Г is called a bi-normal with respect to G if R（G） is not normal in Aut（Г）, but R（G） contains a subgroup of index 2 which is normal in Aut（F）. In this paper, we prove that connected tetravalent edge-transitive Cayley graphs on PGL（2,p） are either normal or bi-normal when p ≠ 11 is a prime.     

Stability of homogeneous principal bundles with a classical groupas the structure group

Let G be a connected semisimple linear algebraic group defined over an algebraically closed field k and P ⊂ G a parabolic subgroup without any simple factor. Let H be a connected reductive linear algebraic group defined over the field k such that all the simple quotients of H are of classical type. Take any homomorphism π : P → H such that the image of p is not contained in any proper parabolic subgroup of H. Consider the corresponding principal H-bundle E_P(H) = (G × H)/P over G/P. We prove that E_P (H) is strongly stable with respect to any polarization on G/P.     

CLASSIFICATION OF FINITE-MULTIPLICITY SYMMETRIC PAIRS

We give a complete classification of the reductive symmetric pairs (G, H) for which the homogeneous space (G × H)/ diag H is real spherical in the sense that a minimal parabolic subgroup has an open orbit. Combining with a criterion established in T. Kobayashi, T. Oshima, Adv. Math. 2013, we give a necessary and sufficient condition for a reductive symmetric pair (G, H) such that the multiplicities for the branching law of the restriction of any admissible smooth representation of G to H have finiteness/boundedness property.     

On a construction of critical graphs which are not sensitive

Let ?(G) be theclosed-set lattice of a graphG. G issensitive if the following implication is always true for any graphG′: ?(G)??(G′)?(G)?G′G iscritical if ?(G)??(G-e) for anye inE(G) and ?(G)??(G+e) for anye in \(\left( {\bar G} \right)\) where \(\bar G\) is the complement ofG. Every sensitive graph is, a fortiori, critical. Is every critical graph sensitive? A negative answer to this question is given in this note.     

On the lifting of elliptic cusp forms to cusp forms on quaternionic unitary groups

Let H be a definite quaternion algebra over Q with discriminant DH and R a maximal order of H. We denote by Gn a quaternionic unitary group and put Γn=Gn(Q)∩GL2n(R). Let Sκ(Γn) be the space of cusp forms of weight κ with respect to Γn on the quaternion half-space of degree n. We construct a lifting from primitive forms in Sk(SL₂(Z)) to Sk+2n−2(Γn) and a lifting from primitive forms in Sk(Γ₀(d)) to Sk+2(Γ₂), where d is a factor of DH. These liftings are generalizations of the Maass lifting investigated by Krieg.     

Mesures de Patterson-Sullivan dans les espaces symétriques

Let X = G/K be a symmetric space of noncompact type, Γ a Zariski-dense subgroup of G with critical exponent δ(Γ). We show that all Γ-invariant conformal densities of dimension δ(Γ) (e.g. Patterson-Sullivan densities) have their support contained in a same and single G-orbit on the geometric boundary of X. In the lattice case, we explicitly determine δ(Γ) and this G-orbit, and we establish the uniqueness of such densities.     

Results on the Grundy chromatic number of graphs

Given a graph G, by a Grundy k-coloring of G we mean any proper k-vertex coloring of G such that for each two colors i and j, i<j, every vertex of G colored by j has a neighbor with color i. The maximum k for which there exists a Grundy k-coloring is denoted by Γ(G) and called Grundy (chromatic) number of G. We first discuss the fixed-parameter complexity of determining Γ(G)?k, for any fixed integer k and show that it is a polynomial time problem. But in general, Grundy number is an NP-complete problem. We show that it is NP-complete even for the complement of bipartite graphs and describe the Grundy number of these graphs in terms of the minimum edge dominating number of their complements. Next we obtain some additive Nordhaus-Gaddum-type inequalities concerning Γ(G) and Γ(G^c), for a few family of graphs. We introduce well-colored graphs, which are graphs G for which applying every greedy coloring results in a coloring of G with χ(G) colors. Equivalently G is well colored if Γ(G)=χ(G). We prove that the recognition problem of well-colored graphs is a coNP-complete problem.     

F-Sets in graphs

A subset S of the vertex set of a graph G is called an F-set if every α?Γ(G), the automorphism group of G, is completely specified by specifying the images under α of all the points of S, and S has a minimum number of points. The number of points, k(G), in an F-set is an invariant of G, whose properties are studied in this paper. For a finite group Γ we define k(Γ) = max{k(G) | Γ(G) = Γ}. Graphs with a given Abelian group and given k-value (k ≤ k(Γ)) have been constructed. Graphs with a given group and k-value 1 are constructed which give simple proofs to the theorems of Frucht and Bouwer on the existence of graphs with given abstract/permutation groups.     

Graphs admitting transitive commutative group actions

Let X be a compact metric space, and Homeo(X) be the group consisting of all homeomorphisms from X to X. A subgroup H of Homeo(X) is said to be transitive if there exists a point x∈X such that {k(x):k∈H} is dense in X. In this paper we show that, if X=G is a connected graph, then the following five conditions are equivalent: (1) Homeo(G) has a transitive commutative subgroup; (2) G admits a transitive Z²-action; (3) G admits an edge-transitive commutative group action; (4) G admits an edge-transitive Z²-action; (5) G is a circle, or a k-fold loop with k?2, or a k-fold polygon with k?2, or a k-fold complete bigraph with k?1. As a corollary of this result, we show that a finite connected simple graph whose automorphism group contains an edge-transitive commutative subgroup is either a cycle or a complete bigraph.     

Linear arboricity for graphs with multiple edges

Akiyama, Exoo, and Harary conjectured that for any simple graph G with maximum degree Δ(G), the linear arboricity la(G) satisfies ?Δ(G)/2? ≦ la(G) ≦ ?(Δ(G) + 1)/2?. Here it is proved that if G is a loopless graph with maximum degree Δ(G) ≦ k and maximum edge multiplicity μ(G) ≦ k ? 2ⁿ⁺¹ + 1, where k ≧ 2^n?2, then la(G) ≦ k ? 2ⁿ. It is also conjectured that for any loopless graph G, ?Δ(G)/2? ≦ la(G) ≦ ?(Δ(G) + μ(G))/2?.     

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.     

On the maximum number of diagonals of a circuit in a graph

For a graph G, let ?(G) denote the maximum number k such that G contains a circuit with k diagonals.Theorem. For any graph G with minimum valency$\text{n? 3, ?(G) ?}\text{1}\text{2}\text{(n+1)(n-2)}$.If the equality holds and G is connected, then either G is isomorphic to K_n+1 or G is separable and each of its terminal blocks is isomorphic to K_n+1, or K_n+1 with one edge subdivided.     

About noncommuting graphs

The noncommuting graph ?(G) of a nonabelian finite group G is defined as follows: The vertices of ?(G) are represented by the noncentral elements of G, and two distinct vertices x and y are joined by an edge if xy ≠ yx. In [1], the following was conjectured: Let G and H be two nonabelian finite groups such that ?(G) ? ?(H); then ¦G¦ = ¦H¦. Here we give some counterexamples to this conjecture.     

Metric characterization of apartments in dual polar spaces

Let Π be a polar space of rank n and let Gk(Π), k∈{0,…,n−1} be the polar Grassmannian formed by k-dimensional singular subspaces of Π. The corresponding Grassmann graph will be denoted by Γk(Π). We consider the polar Grassmannian Gn−1(Π) formed by maximal singular subspaces of Π and show that the image of every isometric embedding of the n-dimensional hypercube graph Hn in Γn−1(Π) is an apartment of Gn−1(Π). This follows from a more general result concerning isometric embeddings of Hm, m?n in Γn−1(Π). As an application, we classify all isometric embeddings of Γn−1(Π) in Γn^′−1(Π^′), where Π^′ is a polar space of rank n^′?n.