Perturbation bounds for theLDL H andLU decompositions

LetA andA+A be Hermitian positive definite matrices. Suppose thatA=LDL ^H and (A+A)=(L+L)(D+D)(L+L)^H are theLDL ^H decompositons ofA andA+A, respectively. In this paper upper bounds on |D| _F and |L| _F are presented. Moreover, perturbation bounds are given for theLU decomposition of a complexn ×n matrix.     

Counting points in hypercubes and convolution measure algebras

It is shown that ifA andB are non-empty subsets of {0, 1} ⁿ (for somenεN) then |A+B|≧(|A||B|)^α where α=(1/2) log₂ 3 here and in what follows. In particular if |A|=2 ^n-1 then |A+A|≧3 ^n-1 which anwers a question of Brown and Moran. It is also shown that if |A| = 2 ^n-1 then |A+A|=3 ^n-1 if and only if the points ofA lie on a hyperplane inn-dimensions. Necessary and sufficient conditions are also given for |A +B|=(|A||B|)^α. The above results imply the following improvement of a result of Talagrand [7]: ifX andY are compact subsets ofK (the Cantor set) withm(X),m(Y)>0 then λ(X+Y)≧2(m(X)m(Y))^α wherem is the usual measure onK and λ is Lebesgue measure. This also answers a question of Moran (in more precise terms) showing thatm is not concentrated on any proper Raikov system.     

Eigenvalues of Finite Projective Planes with an Abelian Cartesian Group

Let M be an incidence matrix for a projective plane of order n. The eigenvalues of M are calculated in the Desarguesian case and a standard form for M is obtained under the hypothesis that the plane admits a (P,L)-transitivity G, |G| = n. The study of M is reduced to a principal submatrix A which is an incidence matrix for n ² lines of an associated affine plane. In this case, A is a generalized Hadamard matrix of order n for the Cayley permutation representation R(G). Under these conditions it is shown that G is a 2-group and n = 2^r when the eigenvalues of A are real. If G is abelian, the characteristic polynomial |xI – A| is the product of the n polynomials |x – (A)|, a linear character of G. This formula is used to prove n is a prime power under natural conditions on A and spectrum(A). It is conjectured that |xI – A| x ⁿ² mod p for each prime divisor p of n and the truth of the conjecture is shown to imply n = |G| is a prime power.     

A Canonical Ramsey Theorem

Say a graph H selects a graph G if given any coloring of H, there will be a monochromatic induced copy of G in H or a completely multicolored copy of G in H. Denote by s(G) the minimum order of a graph that selects G and set s(n) = max {s(G): |G| = n}. Upper and lower bounds are given for this function. Also, consider the Folkman function f_r(n) = max{min{|V(H)|: H → (G)¹_r}: |V(G)| = n}, where H → (G)¹_r indicates that H is vertex Ramsey to G, that is, any vertex coloring of H with r colors admits a monochromatic induced copy of G. The method used provides a better upper bound for this function than was previously known. As a tool, we establish a theorem for projective planes.     

A Parallel Algorithm for Computing Minimum Spanning Trees

present a simple and implementable algorithm that computes a minimum spanning tree of an undirected weighted graph G = (V, E) of n = |V| vertices and m = |E| edges on an EREW PRAM in O(log^3/2n) time using n + m processors. This represents a substantial improvement in the running time over the previous results for this problem using at the same time the weakest of the PRAM models. It also implies the existence of algorithms having the same complexity bounds for the EREW PRAM, for connectivity, ear decomposition, biconnectivity, strong orientation, st-numbering and Euler tours problems.     

On precover classes

Sunto LetG andH be abstract classes of modules. The classH is said to have theG-property if to each infinite cardinal λ there exists a cardinal κ>λ such that for everyF∈H with |F|≥κ and every its submoduleK with |F/K|≤λ there exists a submoduleL ofK such thatF/L/teG and |F/L|<κ. This condition is stronger than the condition (P) requiringL≠0 instead of |F/L|<κ, which was introduced and investigated in [8]. In this note we are going to study the relations of this more general condition to the existence of precovers with respect to some classes of modules. As an application we obtain some sufficient conditions for the existence of σ-torsionfree precovers related to a given hereditary torsion theory σ for the categoryR-mod. This result is closely related to and in some sense extends that of [5]. The research has been partially supported by the Grant Agency of the Czech Republic, grant #GAČR 201/03/0937 and also by the institutional grant MSM 113 200 007.     

On 2‐factors of a bipartite graph

In this article, we consider the following problem: Given a bipartite graph G and a positive integer k, when does G have a 2‐factor with exactly k components? We will prove that if G = (V₁, V₂, E) is a bipartite graph with |V₁| = |V₂| = n ≥ 2k + 1 and δ (G) ≥ ⌈n/2⌉ + 1, then G contains a 2‐factor with exactly k components. We conjecture that if G = (V₁, V₂; E) is a bipartite graph such that |V₁| = |V₂| = n ≥ 2 and δ (G) ≥ ⌈n/2⌉ + 1, then, for any bipartite graph H = (U₁, U₂; F) with |U₁| ≤ n, |U₂| ≤ n and Δ (H) ≤ 2, G contains a subgraph isomorphic to H. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 101–106, 1999     

On weakly τ-quasinormal subgroups of finite groups

Let G be a finite group and H a subgroup of G. We say that: (1) H is τ-quasinormal in G if H permutes with all Sylow subgroups Q of G such that (|Q|, |H|) = 1 and (|H|, |Q ^G |) ≠ 1; (2) H is weakly τ-quasinormal in G if G has a subnormal subgroup T such that HT = G and T ∩ H ≦ H _τG , where H _τG is the subgroup generated by all those subgroups of H which are τ-quasinormal in G. Our main result here is the following. Let ℱ be a saturated formation containing all supersoluble groups and let X ≦ E be normal subgroups of a group G such that G/E ∈ ℱ. Suppose that every non-cyclic Sylow subgroup P of X has a subgroup D such that 1 < |D| < |P| and every subgroup H of P with order |H| = |D| and every cyclic subgroup of P with order 4 (if |D| = 2 and P is non-Abelian) not having a supersoluble supplement in G is weakly τ-quasinormal in G. If X is either E or F* (E), then G ∈ ℱ.     

On B(5, 18) Groups

A group G is said to be a B(n, k) group if for any n-element subset A of G, |A²| ≤k. In this paper, a characterization of B(5, 18) groups is given. It is shown that G is a B(5, 18) group if and only if one of the following statements holds: (1) G is abelian; (2) |G| ≤18; (3) G ? ? a, b | a⁵ = b⁴ = 1, a^b = a^?1 ?.     

Component factors and induced subgraphs

Let G and K be connected graphs such that | G| = n|K| (n ≥ 2) and let p be a fixed integer satisfying 1 < p < n. We prove that if G \ A has a K-factor for every connected subgraph A with |A| = p|K|, then G also has a K-factor. © 1996 John Wiley & Sons, Inc.     

Covering times of random walks on bounded degree trees and other graphs

The motivating problem for this paper is to find the expected covering time of a random walk on a balanced binary tree withn vertices. Previous upper bounds for general graphs ofO(|V| |E|)⁽¹⁾ andO(|V| |E|/d _min)⁽²⁾ imply an upper bound ofO(n ²). We show an upper bound on general graphs ofO( |E| log |V|), which implies an upper bound ofO(n log² n). The previous lower bound was (|V| log |V|) for trees.⁽²⁾ In our main result, we show a lower bound of (|V| (log _{d max} |V|)²) for trees, which yields a lower bound of (n log² n). We also extend our techniques to show an upper bound for general graphs ofO(max{E T_i} log |V|).     

Maximum matchings in random bipartite graphs and the space utilization of Cuckoo Hash tables

We study the the following question in Random Graphs. We are given two disjoint sets L,R with |L| = n and |R| = m. We construct a random graph G by allowing each x∈L to choose d random neighbours in R. The question discussed is as to the size μ(G) of the largest matching in G. When considered in the context of Cuckoo Hashing, one key question is as to when is μ(G) = n whp? We answer this question exactly when d is at least three. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

The number of meets between two subsets of a lattice

Let L be a lattice of divisors of an integer (isomorphically, a direct product of chains). We prove |A| |B| ? |L| |A ∧ B| for any A, B ? L, where |·| denotes cardinality and A ∧ B = {a ∧ b: a?A, b?B}. |A ∧ B| attains its minimum for fixed |A|, |B| when A and B are ideals. |·| can be replaced by certain other weight functions. When the n chains are of equal size k, the elements may be viewed as n-digit k-ary numbers. Then for fixed |A|, |B|, |A ∧ B| is minimized when A and B are the |A| and |B| smallest n-digit k-ary numbers written backwards and forwards, respectively. |A ∧ B| for these sets is determined and bounded. Related results are given, and conjectures are made.     

A note on the perturbation bound of the Drazin inverse

A perturbation bound for the Drazin inverse A^D with Ind(A+E)=1 has recently been developed. However, those upper bounds are not satisfied since it is not tight enough. In this paper, a sharper upper bounds for ||(A+E)^#−A^D|| with weaker conditions is derived. That new bound is also a generalization of a new general upper bound of the group inverse. We also derive a new expression of the Drazin inverse (A+E)^D with Ind(A+E)>1 and the corresponding upper bound of ||(A+E)^D−A^D|| in a special case. Numerical examples are given to illustrate the sharpness of the new bounds.     

Restricted sumsets and a conjecture of Lev

LetA, B, S be finite subsets of an abelian groupG. Suppose that the restricted sumsetC={α+b: α ∈A, b ∈B, and α − b ∉S} is nonempty and somec∈C can be written asa+b witha∈A andb∈B in at mostm ways. We show that ifG is torsion-free or elementary abelian, then |C|≥|A|+|B|−|S|−m. We also prove that |C|≥|A|+|B|−2|S|−m if the torsion subgroup ofG is cyclic. In the caseS={0} this provides an advance on a conjecture of Lev. This author is responsible for communications, and supported by the National Science Fund for Distinguished Young Scholars (No. 10425103) and the Key Program of NSF (No. 10331020) in China.     

On the Schur multipliers of finite p-groups of given coclass

In this paper we obtain bounds for the order and exponent of the Schur multiplier of a p-group of given coclass. These are further improved for p-groups of maximal class. In particular, we prove that if G is p-group of maximal class, then |H ₂(G, ℤ)| < |G| and expH ₂(G, ℤ) ≤ expG. The bound for the order can be improved asymptotically.     

Large centralizers in finite solvable groups

In 1955 R. Brauer and K. A. Fowler showed that ifG is a group of even order >2, and the order |Z(G)| of the center ofG is odd, then there exists a strongly real) elementx∈G−Z whose centralizer satisfies|C _G(x)|>|G|^1/3. In Theorem 1 we show that every non-abeliansolvable groupG contains an elementx∈G−Z such that|C _G(x)|>[G:G′∩Z]^1/2 (and thus|C _G(x)|>|G|^1/3). We also note that if non-abelianG is either metabelian, nilpotent or (more generally) supersolvable, or anA-group, or any Frobenius group, then|C _G(x)|>|G|^1/2 for somex∈G−Z. In Theorem 2 we prove that every non-abelian groupG of orderp ^mqⁿ (p, q primes) contains a proper centralizer of order >|G|^1/2. Finally, in Theorem 3 we show that theaverage |C(x)|, x∈G, is ≧c|G| ^1/3 for metabelian groups, wherec is constant and the exponent 1/3 is best possible.     

On semigroups generated by restrictions of elliptic operators to invariant subspaces

Let A be the closed unbounded operator inL _p(G) that is associated with an elliptic boundary value problem for a bounded domainG. We prove the existence of a spectral projectionE determined by the set Γ = {λ;θ ₁≦argλ≦θ ₂} and show thatAE is the infinitesimal generator of an analytic semigroup provided that the following conditions hold: 1<p<∞; the boundary ϖΓ of Γ is contained in the resolvent setp(A) ofA;π/2≦θ<θ ₂≦3π/2 ; and there exists a constantc such that (I)││(λ-A)^-1││≦c/│λ│ for λ∈ϖΓ. The following consequence is obtained: Suppose that there exist constantsM andc such that λ∈p(A) and estimate (I) holds provided that |λ|≧M and Re λ=0. Then there exist bounded projectionE ⁻ andE ⁺ such thatA is completely reduced by the direct sum decompositionL _p(G)=E⁻L_p (G) ⊕E⁺L_p (G) and each of the operatorsAE ⁻ and—AE ⁺ is the infinitestimal generator of an analytic semigroup.     

Complete hypersurfaces with constant scalar curvature in spheres

To a given immersion i:Mⁿ? \mathbb Sⁿ⁺¹{i:M^n\to \mathbb S^{n+1}} with constant scalar curvature R, we associate the supremum of the squared norm of the second fundamental form sup |A|². We prove the existence of a constant C _n (R) depending on R and n so that R ≥ 1 and sup |A|² = C _n (R) imply that the hypersurface is a H(r)-torus \mathbb S¹(?{1-r²})×\mathbb S^n-1 (r){\mathbb S^1(\sqrt{1-r^2})\times\mathbb S^{n-1} (r)}. For R > (n − 2)/n we use rotation hypersurfaces to show that for each value C > C _n (R) there is a complete hypersurface in \mathbb Sⁿ⁺¹{\mathbb S^{n+1}} with constant scalar curvature R and sup |A|² = C, answering questions raised by Q. M. Cheng.