<Emphasis Type="Italic">K</Emphasis>-Radical classes and product radical classes of <Emphasis Type="Italic">MV</Emphasis>-algebras

For an MV-algebra let J ₀( ) be the system of all closed ideals of ; this system is partially ordered by the set-theoretical inclusion. A radical class X of MV-algebras will be called a K-radical class iff, whenever ∈ X and is an MV-algebra with J ₀( ) ≅ J ₀( ), then ∈ X. An analogous notation for lattice ordered groups was introduced and studied by Conrad. In the present paper we show that there is a one-to-one correspondence between K-radical classes of MV-algebras and K-radical classes of abelian lattice ordered groups. We also prove an analogous result for product radical classes of MV-algebras; product radical classes of lattice ordered groups were studied by Ton. This work has been partially supported by the Slovak Academy of Sciences via the project Center of Excellence-Physics of Information, Grant I/2/2005.     

On <Emphasis Type="Italic">S</Emphasis>-quasinormal and <Emphasis Type="Italic">c</Emphasis>-normal subgroups of a finite group

Let be a saturated formation containing the class of supersolvable groups and let G be a finite group. The following theorems are presented: (1) G ∈ if and only if there is a normal subgroup H such that G/H ∈ and every maximal subgroup of all Sylow subgroups of H is either c-normal or S-quasinormally embedded in G. (2) G ∈ if and only if there is a normal subgroup H such that G/H ∈ and every maximal subgroup of all Sylow subgroups of F*(H), the generalized Fitting subgroup of H, is either c-normal or S-quasinormally embedded in G. (3) G ∈ if and only if there is a normal subgroup H such that G/H ∈ and every cyclic subgroup of F*(H) of prime order or order 4 is either c-normal or S-quasinormally embedded in G. Supported by the Natural Science Foundation of China and the Natural Science Foundation of Guangxi Autonomous Region (No. 0249001). Corresponding author. Supported in part by the Natural Science Foundation of China (10571181), NSF of Guangdong Province (06023728) and ARF(GDEI).     

On a question of Sós about 3‐uniform friendship hypergraphs

The well‐known Friendship Theorem states that if G is a graph in which every pair of vertices has exactly one common neighbor, then G has a single vertex joined to all others (a “universal friend”). V. Sós defined an analogous friendship property for 3‐uniform hypergraphs, and gave a construction satisfying the friendship property that has a universal friend. We present new 3‐uniform hypergraphs on 8, 16, and 32 vertices that satisfy the friendship property without containing a universal friend. We also prove that if n ≤ 10 and n ≠ 8, then there are no friendship hypergraphs on n vertices without a universal friend. These results were obtained by computer search using integer programming. © 2008 Wiley Periodicals, Inc. J Combin Designs 16: 253–261, 2008     

A fast algorithm for computing the smallest eigenvalue of a symmetric positive‐definite Toeplitz matrix

Recent progress in signal processing and estimation has generated considerable interest in the problem of computing the smallest eigenvalue of a symmetric positive‐definite (SPD) Toeplitz matrix. An algorithm for computing upper and lower bounds to the smallest eigenvalue of a SPD Toeplitz matrix has been recently derived (Linear Algebra Appl. 2007; DOI: 10.1016/j.laa.2007.05.008 ). The algorithm relies on the computation of the R factor of the QR factorization of the Toeplitz matrix and the inverse of R. The simultaneous computation of R and R^?1 is efficiently accomplished by the generalized Schur algorithm. In this paper, exploiting the properties of the latter algorithm, a numerical method to compute the smallest eigenvalue and the corresponding eigenvector of SPD Toeplitz matrices in an accurate way is proposed. Copyright © 2008 John Wiley & Sons, Ltd.     

A conjecture of Borodin and a coloring of Grünbaum

In 1976, Borodin conjectured that every planar graph has a 5‐coloring such that the union of every k color classes with 1 ≤ k ≤ 4 induces a (k—1)‐degenerate graph. We prove the existence of such a coloring using 18 colors. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:139–147, 2008     

<Emphasis Type="Italic">L</Emphasis><Superscript>2</Superscript>-Invariants of finite aspherical CW-complexes

Let X be a finite aspherical CW-complex whose fundamental group π ₁(X) possesses a subnormal series with a non-trivial elementary amenable group G ₀. We investigate the L ²-invariants of the universal covering of such a CW-complex X. The main result is the proof of the vanishing of the L ²-torsion under the condition that π ₁(X) has semi-integral determinant. We further show that the Novikov–Shubin invariants are positive.     

Cycles passing through k + 1 vertices in k‐connected graphs

In this article, we prove the following theorem. Let k ≥ 3 be an integer, G be a k‐connected graph with minimum degree d and X be a set of k + 1 vertices on a cycle. Then G has a cycle of length at least min {2d,|V(G)|} passing through X. This result gives the positive answer to the Question posed by Locke [8]. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:179–190, 2008     

Every longest circuit of a 3‐connected,K3,3‐minor free graph has a chord

Carsten Thomassen conjectured that every longest circuit in a 3‐connected graph has a chord. We prove the conjecture for graphs having no K_3,3 minor, and consequently for planar graphs. © 2008 Wiley Periodicals, Inc. J Graph Theory 58: 293–298, 2008     

On variants of the Johnson–Lindenstrauss lemma

The Johnson–Lindenstrauss lemma asserts that an n‐point set in any Euclidean space can be mapped to a Euclidean space of dimension k = O(ε^‐2 log n) so that all distances are preserved up to a multiplicative factor between 1 ? ε and 1 + ε. Known proofs obtain such a mapping as a linear map R ⁿ → R ^k with a suitable random matrix. We give a simple and self‐contained proof of a version of the Johnson–Lindenstrauss lemma that subsumes a basic versions by Indyk and Motwani and a version more suitable for efficient computations due to Achlioptas. (Another proof of this result, slightly different but in a similar spirit, was given independently by Indyk and Naor.) An even more general result was established by Klartag and Mendelson using considerably heavier machinery. Recently, Ailon and Chazelle showed, roughly speaking, that a good mapping can also be obtained by composing a suitable Fourier transform with a linear mapping that has a sparse random matrix M; a mapping of this form can be evaluated very fast. In their result, the nonzero entries of M are normally distributed. We show that the nonzero entries can be chosen as random ± 1, which further speeds up the computation. We also discuss the case of embeddings into R ^k with the ?₁ norm. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Norm of Berezin transformon <Emphasis Type="Italic">L</Emphasis><Superscript><Emphasis Type="Italic">p</Emphasis></Superscript> space

It is shown that the Berezin transform B on L ^p (D), where D is the unit disc, has norm . Furthermore, the norms of a family of operators (on L ^p (D)) whose kernels are moduli of Bergman type kernels are also calculated. Partially supported by MNZZS, Grant ON144010     

<Emphasis Type="Italic">L</Emphasis>-functions of symmetric products of the Kloosterman sheaf over Z

The classical n-variable Kloosterman sums over the finite field F _p give rise to a lisse -sheaf Kl _n+1 on , which we call the Kloosterman sheaf. Let L _p (G _{m, F p} , Sym ^k Kl _n+1, s) be the L-function of the k-fold symmetric product of Kl _n+1. We construct an explicit virtual scheme X of finite type over Spec Z such that the p-Euler factor of the zeta function of X coincides with L _p (G _{m, F p} , Sym ^k Kl _n+1, s). We also prove similar results for and . The research of L. Fu is supported by the NSFC (10525107).     

Hadwiger's conjecture for quasi‐line graphs

A graph G is a quasi‐line graph if for every vertex v ∈ V(G), the set of neighbors of v in G can be expressed as the union of two cliques. The class of quasi‐line graphs is a proper superset of the class of line graphs. Hadwiger's conjecture states that if a graph G is not t‐colorable then it contains K_{t + 1} as a minor. This conjecture has been proved for line graphs by Reed and Seymour. We extend their result to all quasi‐line graphs. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 17–33, 2008     

Efficient <Emphasis Type="Italic">p</Emphasis>th root computations in finite fields of characteristic <Emphasis Type="Italic">p</Emphasis>

We present a method for computing pth roots using a polynomial basis over finite fields of odd characteristic p, p ≥ 5, by taking advantage of a binomial reduction polynomial. For a finite field extension of our method requires p − 1 scalar multiplications of elements in by elements in . In addition, our method requires at most additions in the extension field. In certain cases, these additions are not required. If z is a root of the irreducible reduction polynomial, then the number of terms in the polynomial basis expansion of z ^1/p , defined as the Hamming weight of z ^1/p or , is directly related to the computational cost of the pth root computation. Using trinomials in characteristic 3, Ahmadi et al. (Discrete Appl Math 155:260–270, 2007) give is greater than 1 in nearly all cases. Using a binomial reduction polynomial over odd characteristic p, p ≥ 5, we find always.      

A Characterization of the degree sequences of 2‐trees

A graph G is a 2‐tree if G = K₃, or G has a vertex v of degree 2, whose neighbors are adjacent, and G/ v is a 2‐ tree. A characterization of the degree sequences of 2‐trees is given. This characterization yields a linear‐time algorithm for recognizing and realizing degree sequences of 2‐trees. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:191‐209, 2008     

Nonvertex‐Balanced Factors in Random Graphs

We prove part of a conjecture by Johansson, Kahn, and Vu (Factors in random graphs, Random Struct. Algorithms 33 (2008), 1, 1–28.) regarding threshold functions for the existence of an H‐factor in a random graph . We prove that the conjectured threshold function is correct for any graph H which is not covered by its densest subgraphs. We also demonstrate that the main result of Johansson, Kahn, and Vu (Factors in random graphs, Random Struct. Algorithms 33 (2008), 1, 1–28) generalizes to multigraphs, digraphs, and a multipartite model.     

The simple random walk and max‐degree walk on a directed graph

We bound total variation and L^∞ mixing times, spectral gap and magnitudes of the complex valued eigenvalues of general (nonreversible nonlazy) Markov chains with a minor expansion property. The resulting bounds for the (nonlazy) simple and max‐degree walks on a (directed) graph are of the optimal order. It follows that, within a factor of two or four, the worst case of each of these mixing time and eigenvalue quantities is a walk on a cycle with clockwise drift. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Pointwise convergence for semigroups in vector-valued <Emphasis Type="Italic">L</Emphasis><Superscript><Emphasis Type="Italic">p</Emphasis></Superscript> spaces

Suppose that {T _t  : t  ≥  0} is a symmetric diffusion semigroup on L ²(X) and denote by its tensor product extension to the Bochner space , where belongs to a certain broad class of UMD spaces. We prove a vector-valued version of the Hopf–Dunford–Schwartz ergodic theorem and show that this extends to a maximal theorem for analytic continuations of on . As an application, we show that such continuations exhibit pointwise convergence.     

Existence of global attractors for the three‐dimensional Brinkman–Forchheimer equation

In this paper, we investigate the asymptotic behavior of solutions of the three‐dimensional Brinkman–Forchheimer equation. We first prove the existence and uniqueness of solutions of the equation in L², and then show that the equation has a global attractor in H² when the external forcing term belongs to L². Copyright © 2008 John Wiley & Sons, Ltd.     

<Emphasis Type="Italic">K</Emphasis><Subscript>0</Subscript>-group and approximate similarity invariants of strongly irreducible operators

Let H olenote a complex separable Hilbert space and L(H) denote the collection of bounded linear operators on H. An operator T ∈ L(H) is said to be strongly irreducible if T does not commute with any nontrivial idempotent. Herrero and Jiang showed that the norm-closure of the class of all strongly irreducible operators is the class of all operators with connected spectrum. This result can be considered as an approximate inverse of the Riesz decomposition theorem. In the paper, we give a more precise charact...