Pushing up point stabilizers, II

This paper is a continuation of the paper [G. Parmeggiani, Pushing up point stabilizers, I, J. Algebra 319 (9) (2008) 3854–3884]. Under the same hypotheses, we determine those amalgams which involve SL_n(q), n3, as factors.     

The perfect matching polytope and solid bricks

The perfect matching polytope of a graph G is the convex hull of the set of incidence vectors of perfect matchings of G. Edmonds (J. Res. Nat. Bur. Standards Sect. B 69B 1965 125) showed that a vector x in Q^E belongs to the perfect matching polytope of G if and only if it satisfies the inequalities: (i) x0 (non-negativity), (ii) x(∂(v))=1, for all vV (degree constraints) and (iii) x(∂(S))1, for all odd subsets S of V (odd set constraints). In this paper, we characterize graphs whose perfect matching polytopes are determined by non-negativity and the degree constraints. We also present a proof of a recent theorem of Reed and Wakabayashi.     

On the number of independent chorded cycles in a graph

Hajnal and Corrádi proved that any simple graph on at least 3k vertices with minimal degree at least 2k contains k independent cycles. We prove the analogous result for chorded cycles. Let G be a simple graph with |V(G)|4k and minimal degree δ(G)3k. Then G contains k independent chorded cycles. This result is sharp.     

Universal Polynomial Majorants on Convex Bodies

Let K be a convex body in ^d (d2), and denote by B_n(K) the set of all polynomials p_n in ^d of total degree n such that |p_n|1 on K. In this paper we consider the following question: does there exist a p*_nB_n(K) which majorates every element of B_n(K) outside of K? In other words can we find a minimal γ1 and p*_nB_n(K) so that |p_n(x)|γ |p*_n(x)| for every p_nB_n(K) and x ^d\K? We discuss the magnitude of γ and construct the universal majorants p*_n for evenn. It is shown that γ can be 1 only on ellipsoids. Moreover, γ=O(1) on polytopes and has at most polynomial growth with respect to n, in general, for every convex body K.     

disjoint cycles containing specified independent vertices

Let k1 be an integer and G be a graph of order n3k satisfying the condition that σ₂(G)n+k-1. Let v₁,…,v_k be k independent vertices of G, and suppose that G has k vertex-disjoint triangles C₁,…,C_k with v_iV(C_i) for all 1ik.Then G has k vertex-disjoint cycles such that

(i) for all 1ik.

(ii) , and

(iii) At least k-1 of the k cycles are triangles.

The condition of degree sum σ₂(G)n+k-1 is sharp.

Steiner centers and Steiner medians of graphs

Let G be a connected graph and S a set of vertices of G. The Steiner distance of S is the smallest number of edges in a connected subgraph of G that contains S and is denoted by d_G(S) or d(S). The Steiner n-eccentricity e_n(v) and Steiner n-distance d_n(v) of a vertex v in G are defined as e_n(v)=max{d(S)| SV(G), |S|=n and vS} and d_n(v)=∑{d(S)| SV(G), |S|=n and vS}, respectively. The Steiner n-center C_n(G) of G is the subgraph induced by the vertices of minimum n-eccentricity. The Steiner n-median M_n(G) of G is the subgraph induced by those vertices with minimum Steiner n-distance. Let T be a tree. Oellermann and Tian [O.R. Oellermann, S. Tian, Steiner centers in graphs, J. Graph Theory 14 (1990) 585–597] showed that C_n(T) is contained in C_n+1(T) for all n2. Beineke et al. [L.W. Beineke, O.R. Oellermann, R.E. Pippert, On the Steiner median of a tree, Discrete Appl. Math. 68 (1996) 249–258] showed that M_n(T) is contained in M_n+1(T) for all n2. Then, Oellermann [O.R. Oellermann, On Steiner centers and Steiner medians of graphs, Networks 34 (1999) 258–263] asked whether these containment relationships hold for general graphs. In this note we show that for every n2 there is an infinite family of block graphs G for which C_n(G)C_n+1(G). We also show that for each n2 there is a distance–hereditary graph G such that M_n(G)M_n+1(G). Despite these negative examples, we prove that if G is a block graph then M_n(G) is contained in M_n+1(G) for all n2. Further, a linear time algorithm for finding the Steiner n-median of a block graph is presented and an efficient algorithm for finding the Steiner n-distances of all vertices in a block graph is described.     

On shredders and vertex connectivity augmentation

We consider the following problem: given a k-(node) connected graph G find a smallest set F of new edges so that the graph G+F is (k+1)-connected. The complexity status of this problem is an open question. The problem admits a 2-approximation algorithm. Another algorithm due to Jordán computes an augmenting edge set with at most (k−1)/2 edges over the optimum. CV(G) is a k-separator (k-shredder) of G if |C|=k and the number b(C) of connected components of G−C is at least two (at least three). We will show that the problem is polynomially solvable for graphs that have a k-separator C with b(C)k+1. This leads to a new splitting-off theorem for node connectivity. We also prove that in a k-connected graph G on n nodes the number of k-shredders with at least p components (p3) is less than 2n/(2p−3), and that this bound is asymptotically tight.     

Typical primitive polynomials over integer residue rings

Let N be a product of distinct prime numbers and Z/(N) be the integer residue ring modulo N. In this paper, a primitive polynomial f(x) over Z/(N) such that f(x) divides x^s−c for some positive integer s and some primitive element c in Z/(N) is called a typical primitive polynomial. Recently typical primitive polynomials over Z/(N) were shown to be very useful, but the existence of typical primitive polynomials has not been fully studied. In this paper, for any integer m1, a necessary and sufficient condition for the existence of typical primitive polynomials of degree m over Z/(N) is proved.     

An iterative approximation procedure for the distribution of the maximum of a random walk

Let I(F) be the distribution function (d.f.) of the maximum of a random walk whose i.i.d. increments have the common d.f. F and a negative mean. We derive a recursive sequence of embedded random walks whose underlying d.f.'s F_k converge to the d.f. of the first ladder variable and satisfy FF₁F₂ on [0,∞) and I(F)=I(F₁)=I(F₂)=. Using these random walks we obtain improved upper bounds for the difference of I(F) and the d.f. of the maximum of the random walk after finitely many steps.     

On the code generated by the incidence matrix of points and k-spaces in and its dual

In this paper, we study the p-ary linear code C_k(n,q), q=p^h, p prime, h1, generated by the incidence matrix of points and k-dimensional spaces in PG(n,q). For kn/2, we link codewords of C_k(n,q)C_k(n,q) of weight smaller than 2q^k to k-blocking sets. We first prove that such a k-blocking set is uniquely reducible to a minimal k-blocking set, and exclude all codewords arising from small linear k-blocking sets. For k<n/2, we present counterexamples to lemmas valid for kn/2. Next, we study the dual code of C_k(n,q) and present a lower bound on the weight of the codewords, hence extending the results of Sachar [H. Sachar, The F_p span of the incidence matrix of a finite projective plane, Geom. Dedicata 8 (1979) 407–415] to general dimension.     

Positive solutions for logistic type quasilinear elliptic equations on R

In this paper, we consider positive solutions of the logistic type p-Laplacian equation −Δ_pu=a(x)|u|^p−2u−b(x)|u|^q−1u, xR^N (N2). We show that under rather general conditions on a(x) and b(x) for large |x|, the behavior of the positive solutions for large |x| can be determined. This is then used to show that there is a unique positive solution. Our results improve the corresponding ones in J. London Math. Soc. (2) 64 (2001) 107–124 and J. Anal. Math., in press.     

Group actions and invariants in algebras of generic matrices

We show that the fixed elements for the natural GL_m-action on the universal division algebra UD(m,n) of m generic n×n-matrices form a division subalgebra of degree n, assuming n3 and 2mn²−2. This allows us to describe the asymptotic behavior of the dimension of the space of SL_m-invariant homogeneous central polynomials p(X₁,…,X_m) for n×n-matrices. Here the base field is assumed to be of characteristic zero.     

Asymptotic behavior of solutions of semilinear elliptic equations near an isolated singularity

We consider the semilinear elliptic equation Δu=h(u) in Ω{0}, where Ω is an open subset of (N2) containing the origin and h is locally Lipschitz continuous on [0,∞), positive in (0,∞). We give a complete classification of isolated singularities of positive solutions when h varies regularly at infinity of index q(1,C_N) (that is, lim_u→∞h(λu)/h(u)=λ^q, for every λ>0), where C_N denotes either N/(N−2) if N3 or ∞ if N=2. Our result extends a well-known theorem of Véron for the case h(u)=u^q.     

Uniform Kazhdan constant for some families of linear groups

Let R be a ring generated by l elements with stable range r. Assume that the group EL_d(R) has Kazhdan constant ₀>0 for some dr+1. We prove that there exist (₀,l)>0 and , s.t. for every nd, EL_n(R) has a generating set of order k and a Kazhdan constant larger than . As a consequence, we obtain for where n3, a Kazhdan constant which is independent of n w.r.t. generating set of a fixed size.     

One-sided tests for independence of seemingly unrelated regression equations

In a seemingly unrelated regression model with p(2) equations, this paper considers the problem of testing independence of equations against a one-sided alternative hypothesis. The power functions of invariant tests are evaluated and the locally most mean powerful invariant test is obtained.     

On a Conjecture of Ditzian and Runovskii

Let M_θ be the mean operator on the unit sphere in ⁿ, n3, which is an analogue of the Steklov operator for functions of single variable. Denote by D the Laplace–Beltrami operator on the sphere which is an analogue of second derivative for functions of single variable. Ditzian and Runovskii have a conjecture on the norm of the operator θ²D(M_θ)^m, m2 from X=L^p (1p∞) to itself which can be expressed as

Full-size image

. We give a proof of this conjecture.     

Orthogonal graphs of odd characteristic and their automorphisms

The (isotropic) orthogonal graph O(2ν+δ,q) over of odd characteristic, where ν1 and δ=0,1 or 2 is introduced. When ν=1, O(21+δ,q) is a complete graph. When ν2, O(2ν+δ,q) is strongly regular and its parameters are computed, as well as its chromatic number. The automorphism groups of orthogonal graphs are also determined.     

Characterization of A5 and SL(2,5) by the number of conjugacy classes of non-cyclic subgroups

For a finite group G, let ν_c(G) denote the number of conjugacy classes of non-normal non-cyclic subgroups of G. We show that for every finite non-solvable group G, ν_c(G) = |π(G)|+1 if and only if G?A₅, the alternating group on 5 letters, or SL(2,5).     

Viscosity approximation to common fixed points of a nonexpansive semigroup with a generalized contraction mapping

The purpose of this paper is to introduce and construct the implicit and explicit viscosity iterative processes by a generalized contraction mapping f and a nonexpansive semigroup {T(t):t0}, and to prove that under suitable conditions these iterative processes converge strongly to a unique common fixed point of {T(t):t0} in reflexive Banach spaces which admits a weakly sequentially continuous duality mapping.     

Algorithms for extracting motifs from biological weighted sequences

In this paper we present three algorithms for the Motif Identification Problem in Biological Weighted Sequences. The first algorithm extracts repeated motifs from a biological weighted sequence. The motifs correspond to repetitive words which are approximately equal, under a Hamming distance, with probability of occurrence 1/k, where k is a small constant. The second algorithm extracts common motifs from a set of N2 weighted sequences. In this case, the motifs consists of words that must occur with probability 1/k, in 1qN distinct sequences of the set. The third algorithm extracts maximal pairs from a biological weighted sequence. A pair in a sequence is the occurrence of the same word twice. In addition, the algorithms presented in this paper improve previous work on these problems.