Existence of HSOLSSOMs of type

In this paper we investigate the existence of holey self-orthogonal Latin squares with a symmetric orthogonal mate of type 2ⁿu¹ (HSOLSSOM(2ⁿu¹)). For u2, necessary conditions for existence of such an HSOLSSOM are that u must be even and n3u/2+1. Xu Yunqing and Hu Yuwang have shown that these HSOLSSOMs exist whenever either (1) n9 and n3u/2+1 or (2) n263 and n2(u-2). In this paper we show that in (1) the condition n9 can be extended to n30 and that in (2), the condition n263 can be improved to n4, except possibly for 19 pairs (n,u), the largest of which is (53,28).     

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.     

Arithmetic progressions consisting of unlike powers

In this paper we present some new results about unlike powers in arithmetic progression. We prove among other things that for given k 4 and L 3 there are only finitely many arithmetic progressions of the form with x_i , gcd(x₀, x_l) = 1 and 2 l_i L for i = 0, 1, …, k − 1. Furthermore, we show that, for L = 3, the progression (1, 1,…, 1) is the only such progression up to sign. Our proofs involve some well-known theorems of Faltings [9], Darmon and Granville [6] as well as Chabauty's method applied to superelliptic curves.     

The maximum spectral radius of -free graphs of given order and size

Suppose that G is a graph with n vertices and m edges, and let μ be the spectral radius of its adjacency matrix.Recently we showed that if G has no 4-cycle, then μ²-μn-1, with equality if and only if G is the friendship graph.Here we prove that if m9 and G has no 4-cycle, then μ²m, with equality if G is a star. For 4m8 this assertion fails.     

Hankel determinants and orthogonal polynomials

We develop a general context for the computation of the determinant of a Hankel matrix H_n = (α_i+j)0i,jn, assuming some suitable conditions for the exponential (or ordinary) generating function of the sequence (α_n)_n0. Several well-known particular cases are thus derived in a unified way.     

On triconnected and cubic plane graphs on given point sets

Let S be a set of n4 points in general position in the plane, and let h<n be the number of extreme points of S. We show how to construct a 3-connected plane graph with vertex set S, having max{3n/2,n+h−1} edges, and we prove that there is no 3-connected plane graph on top of S with a smaller number of edges. In particular, this implies that S admits a 3-connected cubic plane graph if and only if n4 is even and hn/2+1. The same bounds also hold when 3-edge-connectivity is considered. We also give a partial characterization of the point sets in the plane that can be the vertex set of a cubic plane graph.     

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.     

Vandermonde sets and super-Vandermonde sets

Given a set TGF(q), |T|=t, w_T is defined as the smallest positive integer k for which ∑_yTy^k≠0. It can be shown that w_Tt always and w_Tt−1 if the characteristic p divides t. T is called a Vandermonde set if w_Tt−1 and a super-Vandermonde set if w_T=t. This (extremal) algebraic property is interesting for its own right, but the original motivation comes from finite geometries. In this paper we classify small and large super-Vandermonde sets.     

On Mean Convergence of Lagrange Interpolation for General Arrays

For n1, let {x_jn}ⁿ_j=1 be n distinct points in a compact set K and letL_n[·] denote the corresponding Lagrange interpolation operator. Let v be a suitably restricted function on K. What conditions on the array {x_jn}_1jn, n1 ensure the existence of p>0 such that lim_n→∞ (f−L_n[f]) v_Lp(K)=0 for very continuous f: K→ ? We show that it is necessary and sufficient that there exists r>0 with sup_n1 π_nv_Lr(K) ∑ⁿ_j=1 (1/|π′_n| (x_jn))<∞. Here for n1, π_n is a polynomial of degree n having {x_jn}ⁿ_j=1 as zeros. The necessity of this condition is due to Ying Guang Shi.     

Polyhedral results on single node variable upper-bound flow models with allowed configurations

In this paper we investigate the convex hull of single node variable upper-bound flow models with allowed configurations. Such a model is defined by a set , where ρ is one of , = or , and Z{0,1}ⁿ consists of the allowed configurations. We consider the case when Z consists of affinely independent vectors. Under this assumption, a characterization of the non-trivial facets of the convex hull of X_ρ(Z) for each relation ρ is provided, along with polynomial time separation algorithms. Applications in scheduling and network design are also discussed.     

On Weighted Mean Convergence of Lagrange Interpolation for General Arrays

For n1, let {x_jn}_j=1ⁿ be n distinct points and let L_n[·] denote the corresponding Lagrange Interpolation operator. Let W : →[0,∞). What conditions on the array {x_jn}_{1jn, n1} ensure the existence of p>0 such

Full-size image

for every continuous f : → with suitably restricted growth, and some “weighting factor” φ^b? We obtain a necessary and sufficient condition for such a p to exist. The result is the weighted analogue of our earlier work for interpolation arrays contained in a compact set.     

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.     

A supplement to the Davis–Gut law

Let {X,X_n;n1} be a sequence of i.i.d. real-valued random variables and set , n1. Let h() be a positive nondecreasing function such that . Define Lt=log_emax{e,t} for t0. In this note we prove that

if and only if E(X)=0 and E(X²)=1, where , t1. When h(t)≡1, this result yields what is called the Davis–Gut law. Specializing our result to h(t)=(Lt)^r, 0<r1, we obtain an analog of the Davis–Gut law.     

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.     

Lattices generated by subspaces in d-bounded distance-regular graphs

Let Γ denote a d-bounded distance-regular graph with diameter d2. A regular strongly closed subgraph of Γ is said to be a subspace of Γ. Define the empty set to be the subspace with diameter -1 in Γ. For 0ii+sd-1, let denote the set of all subspaces in Γ with diameters i,i+1,…,i+s including Γ and . If we define the partial order on by ordinary inclusion (resp. reverse inclusion), then is a poset, denoted by (resp. ). In the present paper we show that both and are atomic lattices, and classify their geometricity.     

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.     

On groups with conjugacy classes of distinct sizes

A finite group G is called an ah-group if any two distinct conjugacy classes of G have distinct cardinality. We show that if G is an ah-group, then the non-abelian socle of G is isomorphic to one of the following:

1. , for 1a5, a≠2.

2. A₈.

3. PSL(3,4)^e, for 1e10.

4. A₅×PSL(3,4)^e, for 1e10.

Based on this result, we virtually show that if G is an ah-group with π(G) 2,3,5,7 , then F(G)≠1, or equivalently, that G has an abelian normal subgroup.In addition, we show that if G is an ah-group of minimal size which is not isomorphic to S₃, then the non-abelian socle of G is either trivial or isomorphic to one of the following:

1. , for 3a5.

2. PSL(3,4)^e, for 1e10.

Our research lead us to interesting results related to transitivity and homogeneousity in permutation groups, and to subgroups of wreath products of form Z₂S_n. These results are of independent interest and are located in appendices for greater autonomy.     

Hilbert's Tenth Problem for function fields of varieties over number fields and p-adic fields

Let k be a subfield of a p-adic field of odd residue characteristic, and let be the function field of a variety of dimension n1 over k. Then Hilbert's Tenth Problem for is undecidable. In particular, Hilbert's Tenth Problem for function fields of varieties over number fields of dimension 1 is undecidable.     

Turán type reverse Markov inequalities for compact convex sets

For a compact convex set the well-known general Markov inequality holds asserting that a polynomial p of degree n must have p^′c(K)n²p. On the other hand for polynomials in general, p^′ can be arbitrarily small as compared to p.The situation changes when we assume that the polynomials in question have all their zeroes in the convex set K. This was first investigated by Turán, who showed the lower bounds p^′(n/2)p for the unit disk D and for the unit interval I[-1,1]. Although partial results provided general lower estimates of order , as well as certain classes of domains with lower bounds of order n, it was not clear what order of magnitude the general convex domains may admit here.Here we show that for all bounded and convex domains K with nonempty interior and polynomials p with all their zeroes lying in K p^′c(K)np holds true, while p^′C(K)np occurs for any K. Actually, we determine c(K) and C(K) within a factor of absolute numerical constant.