A new result on Davenport constant

Let G be a finite abelian group of order n and Davenport constant D(G). Let S=⁰h(S)_∏g∈Ggvg(S)∈F(G) be a sequence with a maximal multiplicity h(S) attained by 0 and t=|S|?n+D(G)−1. Then 0∈k_∑(S) for every 1?k?t+1−D(G). This is a refinement of the fundamental result of Gao [W.D. Gao, A combinatorial problem on finite abelian groups, J. Number Theory 58 (1996) 100-103].     

The convexity spectra of graphs

Let D be a connected oriented graph. A set S⊆V(D) is convex in D if, for every pair of vertices x,y∈S, the vertex set of every x-y geodesic (x-y shortest dipath) and y-x geodesic in D is contained in S. The convexity numbercon(D) of a nontrivial oriented graph D is the maximum cardinality of a proper convex set of D. Let G be a graph. We define that S_C(G)={con(D):D is an orientation of G} and S_SC(G)={con(D):D is a strongly connected orientation of G}. In the paper, we show that, for any n?4, 1?a?n-2, and a≠2, there exists a 2-connected graph G with n vertices such that S_C(G)=S_SC(G)={a,n-1} and there is no connected graph G of order n?3 with S_SC(G)={n-1}. Then, we determine that S_C(K₃)={1,2}, S_C(K₄)={1,3}, S_SC(K₃)=S_SC(K₄)={1}, S_C(K₅)={1,3,4}, S_C(K₆)={1,3,4,5}, S_SC(K₅)=S_SC(K₆)={1,3}, S_C(K_n)={1,3,5,6,…,n-1}, S_SC(K_n)={1,3,5,6,…,n-2} for n?7. Finally, we prove that, for any integers n, m, and k with , 1?k?n-1, and k≠2,4, there exists a strongly connected oriented graph D with n vertices, m edges, and convexity number k.     

Homology of iterated loop spaces of homogeneous spaces associated with exceptional Lie groups

We study the mod 2 homology of the double and triple loop spaces of homogeneous spaces associated with exceptional Lie groups. The main computational tools are the Serre spectral sequence for fibrations Ωⁿ⁺¹G→Ωⁿ⁺¹(G/H)→ΩⁿH for n=1,2, and the Eilenberg-Moore spectral sequence associated with related fiber squares, which both converge to the same destination space H_∗(Ωⁿ(G/H);F₂). We also develop the generalized Bockstein lemma to determine the higher Bockstein actions.     

On the multiplicity and the Cohen-Macaulayness of fiber cones of graded algebras

Let A be a Noetherian local ring with the maximal ideal m and an m-primary ideal J. Let S=?_n≥0S_n be a finitely generated standard graded algebra over A. Set S⁺=?_n>0S_n. Denote by F_J(S)=?_n≥0→(S_n/JS_n) the fiber cone of S with respect to J. The paper characterizes the multiplicity and the Cohen-Macaulayness of F_J(S) in terms of minimal reductions of S⁺.     

Hamiltonian cycles and dominating cycles passing through a linear forest

Let G be an (m+2)-graph on n vertices, and F be a linear forest in G with |E(F)|=m and ω₁(F)=s, where ω₁(F) is the number of components of order one in F. We denote by σ₃(G) the minimum value of the degree sum of three vertices which are pairwise non-adjacent. In this paper, we give several σ₃ conditions for a dominating cycle or a hamiltonian cycle passing through a linear forest. We first prove that if σ₃(G)≥n+2m+2+max{s−3,0}, then every longest cycle passing through F is dominating. Using this result, we prove that if σ₃(G)≥n+κ(G)+2m−1 then G contains a hamiltonian cycle passing through F. As a corollary, we obtain a result that if G is a 3-connected graph and σ₃(G)≥n+κ(G)+2, then G is hamiltonian-connected.     

Dimension and lower central subgroups

In [7] Passi proved that for a finite p-group, p ≠ 2, one has G₄ = D₄. We generalize this to say that G_n = D_n as long as n?p + 1. We also generalize a theorem of Quillen [8], using entirely different methods from his, and give his result as a corollary. In order to do this, we construct natural algorithms (spectral sequences) which compute the graded Lie algebra ?_iG_i/G_i+1 and the graded algebra ? Iⁱ(G)/Iⁱ⁺¹(G) respectively, for any group G, in terms of a presentation. A natural transformation between these spectral sequences exists, and analysing its properties by some new combinatorial methods yields the results.     

The Independence Number for De Bruijn networks and Kautz networks

Let D be a directed graph; the (l,ω)-Independence Number of graph D, denoted by α_l,ω(D), is an important performance parameter for interconnection networks. De Bruijn networks and Kautz networks, denoted by B(d,n) and K(d,n) respectively, are versatile and efficient topological structures of interconnection networks. For l=1,2,…,n, this paper shows that α_l,d−1(B(d,n))=dⁿ,α_l,d−1(K(d,n))=α_l,d(K(d,n))=dⁿ+dⁿ⁻¹ if d≥3 and n≤d−2. In particular, the paper shows the exact value of the Independence Number for B(d,1) and B(d,2) for any d. For the generalized situation, the paper obtains a lower bound α_l,d−1(B(d,n))≥d² if n≥3 and d≥5.     

The hull and geodetic numbers of orientations of graphs

For an oriented graph D, let I_D[u,v] denote the set of all vertices lying on a u-v geodesic or a v-u geodesic. For S⊆V(D), let I_D[S] denote the union of all I_D[u,v] for all u,v∈S. Let [S]_D denote the smallest convex set containing S. The geodetic number g(D) of an oriented graph D is the minimum cardinality of a set S with I_D[S]=V(D) and the hull number h(D) of an oriented graph D is the minimum cardinality of a set S with [S]_D=V(D). For a connected graph G, let O(G) be the set of all orientations of G, define g⁻(G)=min{g(D):D∈O(G)}, g⁺(G)=max{g(D):D∈O(G)}, h⁻(G)=min{h(D):D∈O(G)}, and h⁺(G)=max{h(D):D∈O(G)}. By the above definitions, h⁻(G)≤g⁻(G) and h⁺(G)≤g⁺(G). In the paper, we prove that g⁻(G)<h⁺(G) for a connected graph G of order at least 3, and for any nonnegative integers a and b, there exists a connected graph G such that g⁻(G)−h⁻(G)=a and g⁺(G)−h⁺(G)=b. These results answer a problem of Farrugia in [A. Farrugia, Orientable convexity, geodetic and hull numbers in graphs, Discrete Appl. Math. 148 (2005) 256-262].     

Totally geodesic submanifolds in Lie groups

Summary We study minimal and totally geodesic submanifolds in Lie groups and related problems. We show that: (1) The imbedding of the Grassmann manifold G_F(n,N) in the Lie group G_F(N) defined naturally makes G_F(n,N) a totally geodesic submanifold; (2) The imbedding S⁷→SO(8) defined by octonians makes S⁷a totally geodesic submanifold inSO(8); (3) The natural inclusion of the Lie group G_F(N) in the sphere S^{cN^2-1}(√N) of gl(N,F)is minimal. Therefore the natural imbedding G_F(N)<span style='font-size:10.0pt;font-family:"Lucida Sans Unicode"'>→gl(N,F)is formed by the eigenfunctions of the Laplacian on G_F(N).     

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.     

Graphical properties related to minimal imperfection

Say that graph G is partitionable if there exist integers α?2, ω? 2, such that |V(G)| ≡ αω + 1 and for every υ?V(G) there exist partitions of V(G)\ υ into stable sets of size α and into eliques of size ω. An immediate consequence of Lovász' characterization of perfect graphs is that every minimal imperfect graph G is partitionable with α ≡ α (G) andω ≡ ω(G).Padberg has shown that in every minimal imperfect graph G the cliques and stable sets of maximum size satisfy a series of conditions that reflect extraordinary symmetry G. Among these conditions are: the number of cliques of size ω(G) is exactly |V(G)|; the number of stable sets of size α(G) is exactly |V(G)|: every vertex of G is contained in exactly ω(G) cliques of size ω(G) and α(G) stable sets of size α(G): for every clique Q (respectively, stable set S) of maximum size there is a unique stable set S (clique O) of maximum size such that Q∩S ≡ Ø.Let C_n^k denote the graph whose vertices can be enumerated as υ₁,…,υ_n in such a way that υ₁ and υ₁ are adjacent in G if and only if i and j differ by at most k, modulo n. Chvátal has shown that Berge's Strong Perfect graph Conjecture is equivalent to the conjecture that if G is minimal imperfect with α(G) ≡ αandω(G) ≡ ω, then G has a spanning subgraph isomorphic to C_αω+1^ω. Padberg's conditions are sufficiently restrictive to suggest the possibility of establishing the Strong Perfect Graph Conjecture by proving that any graph G satisfying these conditions must contain a spanning subgraph isomorphic to C_αω+1^ω, whereα(G) ≡ αandω(G) ≡ ω. It is shown here, using only elementary linear algebra, that all partitionable graphs satisfy Padberg's conditions, as well as additional properties of the same spirit. Then examples are provided of partitionable graphs which contain no spanning subgraph isomorphic to C_αω+1^ω, whereα(G) ≡ α and ω(G) ≡ ω.     

o-Boundedness of free topological groups

Assuming the absence of Q-points (which is consistent with ZFC) we prove that the free topological group F(X) over a Tychonov space X is o-bounded if and only if every continuous metrizable image T of X satisfies the selection principle fin_?(O,Ω) (the latter means that for every sequence 〈un〉_n∈ω of open covers of T there exists a sequence 〈vn〉_n∈ω such that vn∈[un]^<ω and for every F∈[X]^<ω there exists n∈ω with F⊂?vn). This characterization gives a consistent answer to a problem posed by C. Hernándes, D. Robbie, and M. Tkachenko in 2000.     

Irreducible Specht modules for Hecke algebras of type A

Let F be a field, n a non-negative integer, λ a partition of n and S^λ the corresponding Specht module for the Iwahori-Hecke algebra H_F,q(S_n). James and Mathas conjecture a necessary and sufficient condition on λ for S^λ to be irreducible. We prove the sufficiency of this condition in the case where F has infinite characteristic and also in the case where q=1.     

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.     

A Criterion for the Triviality of G(D) and Its Applications to the Multiplicative Structure of D

Let D be an F-central division algebra of index n. Here we present a criterion for the triviality of the group G(D) = D*/Nrd _D/F (D*)D′ and thus generalizing various related results published recently. To be more precise, it is shown that G(D) = 1 if and only if SK ₁(D) = 1 and F ^*2 = F ^*2n . Using this, we investigate the role of some particular subgroups of D* in the algebraic structure of D. In this direction, it is proved that a division algebra D of prime index is a symbol algebra if and only if D* contains a non-abelian nilpotent subgroup. More applications of this criterion including the computation of G(D) and the structure of maximal subgroups of D* are also investigated     

The maximum corank of graphs with a 2-separation

For a graph G=(V,E) with vertex-set V={1,2,…,n}, which is allowed to have parallel edges, and for a field F, let S(G;F) be the set of all F-valued symmetric n×n matrices A which represent G. The maximum corank of a graph G is the maximum possible corank over all A∈S(G;F). If (G₁,G₂) is a (?2)-separation, we give a formula which relates the maximum corank of G to the maximum corank of some small variations of G₁ and G₂.     

On the dimension of global sections of adjoint bundles for polarized 3-folds and 4-folds

Let (X,L) be a polarized manifold of dimension n defined over the field of complex numbers. In this paper, we treat the case where n=3 and 4. First we study the case of n=3 and we give an explicit lower bound for h⁰(K_X+L) if κ(X)≥0. Moreover, we show the following: if κ(K_X+L)≥0, then h⁰(K_X+L)>0 unless κ(X)=−∞ and h¹(O_X)=0. This gives us a partial answer of Effective Non-vanishing Conjecture for polarized 3-folds. Next for n=4 we investigate the dimension of H⁰(K_X+mL) for m≥2. If n=4 and κ(X)≥0, then a lower bound for h⁰(K_X+mL) is obtained. We also consider a conjecture of Beltrametti-Sommese for 4-folds and we can prove that this conjecture is true unless κ(X)=−∞ and h¹(O_X)=0. Furthermore we prove the following: if (X,L) is a polarized 4-fold with κ(X)≥0 and h¹(O_X)>0, then h⁰(K_X+L)>0.     

The chromatic number of the product of two 4-chromatic graphs is 4

For any graphG and numbern≧1 two functionsf, g fromV(G) into {1, 2, ...,n} are adjacent if for all edges (a, b) ofG, f(a) ≠g(b). The graph of all such functions is the colouring graph ℒ(G) ofG. We establish first that χ(G)=n+1 implies χ(ℒ(G))=n iff χ(G ×H)=n+1 for all graphsH with χ(H)≧n+1. Then we will prove that indeed for all 4-chromatic graphsG χ(ℒ(G))=3 which establishes Hedetniemi’s [3] conjecture for 4-chromatic graphs. This research was supported by NSERC grant A7213