On Equivalence of Moduli of Smoothness

It is known that iffW^k_p, thenω_m(f, t)_ptω_m−1(f′, t)_p…. Its inverse with any constants independent offis not true in general. Hu and Yu proved that the inverse holds true for splinesSwith equally spaced knots, thusω_m(S, t)_ptω_m−1(S′, t)_pt²ω_m−2(S″, t)_p…. In this paper, we extend their results to splines with any given knot sequence, and further to principal shift-invariant spaces and wavelets under certain conditions. Applications are given at the end of the paper.     

Primitive permutation groups with a regular subgroup

This paper starts the classification of the primitive permutation groups (G,Ω) such that G contains a regular subgroup X. We determine all the triples (G,Ω,X) with soc(G) an alternating, or a sporadic or an exceptional group of Lie type. Further, we construct all the examples (G,Ω,X) with G a classical group which are known to us. Our particular interest is in the 8-dimensional orthogonal groups of Witt index 4. We determine all the triples (G,Ω,X) with . In order to obtain all these triples, we also study the almost simple groups G with GPΩ_2n+1(q). The case GU_n(q) is started in this paper and finished in [B. Baumeister, Primitive permutation groups of unitary type with a regular subgroup, Bull. Belg. Math. Soc. 112 (5) (2006) 657–673]. A group X is called a Burnside-group (or short a B-group) if each primitive permutation group which contains a regular subgroup isomorphic to X is necessarily 2-transitive. In the end of the paper we discuss B-groups.     

On some d-dimensional dual hyperovals in

Let d≥3. Let H be a d+1-dimensional vector space over GF(2) and {e₀,…,e_d} be a specified basis of H. We define Supp(t){e_t1,…,e_tl}, a subset of a specified base for a non-zero vector t=e_t1++e_tl of H, and Supp(0)0/. We also define J(t)Supp(t) if |Supp(t)| is odd, and J(t)Supp(t){0} if |Supp(t)| is even.For s,tH, let {a(s,t)} be elements of H(HH) which satisfy the following conditions: (1) a(s,s)=(0,0), (2) a(s,t)=a(t,s), (3) a(s,t)≠(0,0) if s≠t, (4) a(s,t)=a(s^′,t^′) if and only if {s,t}={s^′,t^′}, (5) {a(s,t)|tH} is a vector space over GF(2), (6) {a(s,t)|s,tH} generate H(HH). Then, it is known that S{X(s)|sH}, where X(s){a(s,t)|tH{s}}, is a dual hyperoval in PG(d(d+3)/2,2)=(H(HH)){(0,0)}.In this note, we assume that, for s,tH, there exists some x_s,t in GF(2) such that a(s,t) satisfies the following equation: Then, we prove that the dual hyperoval constructed by {a(s,t)} is isomorphic to either the Huybrechts’ dual hyperoval, or the Buratti and Del Fra’s dual hyperoval.     

On improved estimators of the generalized variance

Treated in this paper is the problem of estimating with squared error loss the generalized variance | Σ | from a Wishart random matrix S: p × p W_p(n, Σ) and an independent normal random matrix X: p × k N(ξ, Σ I_k) with ξ(p × k) unknown. Denote the columns of X by X₍₁₎ ,…, X_(k) and set ψ⁽⁰⁾(S, X) = {(n − p + 2)!/(n + 2)!} | S |, ψ⁽ⁱ⁾(X, X) = min[ψ⁽ⁱ⁻¹⁾(S, X), {(n − p + i + 2)!/(n + i + 2)!} | S + X₍₁₎ X′₍₁₎ + + X_(i) X′_(i) |] and Ψ⁽ⁱ⁾(S, X) = min[ψ⁽⁰⁾(S, X), {(n − p + i + 2)!/(n + i + 2)!}| S + X₍₁₎ X′₍₁₎ + + X_(i) X′_(i) |], i = 1,…,k. Our result is that the minimax, best affine equivariant estimator ψ⁽⁰⁾(S, X) is dominated by each of Ψ⁽ⁱ⁾(S, X), i = 1,…,k and for every i, ψ⁽ⁱ⁾(S, X) is better than ψ⁽ⁱ⁻¹⁾(S, X). In particular, ψ^(k)(S, X) = min[{(n − p + 2)!/(n + 2)!} | S |, {(n − p + 2)!/(n + 2)!} | S + X₍₁₎X′₍₁₎|,…,| {(n − p + k + 2)!/(n + k + 2)!} | S + X₍₁₎X′₍₁₎ + + X_(k)X′_(k)|] dominates all other ψ's. It is obtained by considering a multivariate extension of Stein's result (Ann. Inst. Statist. Math. 16, 155–160 (1964)) on the estimation of the normal variance.     

Mutually independent hamiltonian cycles for the pancake graphs and the star graphs

A hamiltonian cycle C of a graph G is an ordered set u₁,u₂,…,u_n(G),u₁ of vertices such that u_i≠u_j for i≠j and u_i is adjacent to u_i+1 for every i{1,2,…,n(G)−1} and u_n(G) is adjacent to u₁, where n(G) is the order of G. The vertex u₁ is the starting vertex and u_i is the ith vertex of C. Two hamiltonian cycles C₁=u₁,u₂,…,u_n(G),u₁ and C₂=v₁,v₂,…,v_n(G),v₁ of G are independent if u₁=v₁ and u_i≠v_i for every i{2,3,…,n(G)}. A set of hamiltonian cycles {C₁,C₂,…,C_k} of G is mutually independent if its elements are pairwise independent. The mutually independent hamiltonicity IHC(G) of a graph G is the maximum integer k such that for any vertex u of G there exist k mutually independent hamiltonian cycles of G starting at u.In this paper, the mutually independent hamiltonicity is considered for two families of Cayley graphs, the n-dimensional pancake graphs P_n and the n-dimensional star graphs S_n. It is proven that IHC(P₃)=1, IHC(P_n)=n−1 if n≥4, IHC(S_n)=n−2 if n{3,4} and IHC(S_n)=n−1 if n≥5.     

The rainbow number of matchings in regular bipartite graphs

Given a graph G and a subgraph H of G, let rb(G,H) be the minimum number r for which any edge-coloring of G with r colors has a rainbow subgraph H. The number rb(G,H) is called the rainbow number of H with respect to G. Denote as mK₂ a matching of size m and as B_n,k the set of all the k-regular bipartite graphs with bipartition (X,Y) such that X=Y=n and k≤n. Let k,m,n be given positive integers, where k≥3, m≥2 and n>3(m−1). We show that for every GB_n,k, rb(G,mK₂)=k(m−2)+2. We also determine the rainbow numbers of matchings in paths and cycles.     

The energy of unitary cayley graphs

A graph G of order n is called hyperenergetic if E(G)>2n-2, where E(G) denotes the energy of G. The unitary Cayley graph X_n has vertex set Z_n={0,1,2,…,n-1} and vertices a and b are adjacent, if gcd(a-b,n)=1. These graphs have integral spectrum and play an important role in modeling quantum spin networks supporting the perfect state transfer. We show that the unitary Cayley graph X_n is hyperenergetic if and only if n has at least two prime factors greater than 2 or at least three distinct prime factors. In addition, we calculate the energy of the complement of unitary Cayley graph and prove that is hyperenergetic if and only if n has at least two distinct prime factors and n≠2p, where p is a prime number. By extending this approach, for every fixed , we construct families of k hyperenergetic non-cospectral integral circulant n-vertex graphs with equal energy.     

Inscribing an axially symmetric polygon and other approximation algorithms for planar convex sets

Given a planar convex set C, we give sublinear approximation algorithms to determine approximations of the largest axially symmetric convex set S contained in C, and the smallest such set S^′ that contains C. More precisely, for any >0, we find an axially symmetric convex polygon QC with area |Q|>(1−)|S| and we find an axially symmetric convex polygon Q^′ containing C with area |Q^′|<(1+)|S^′|. We assume that C is given in a data structure that allows to answer the following two types of query in time T_C: given a direction u, find an extreme point of C in direction u, and given a line ℓ, find C∩ℓ. For instance, if C is a convex n-gon and its vertices are given in a sorted array, then T_C=O(logn). Then we can find Q and Q^′ in time O(^−1/2T_C+^−3/2). Using these techniques, we can also find approximations to the perimeter, area, diameter, width, smallest enclosing rectangle and smallest enclosing circle of C in time O(^−1/2T_C).     

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.     

Stochastic comparisons of order statistics from heterogeneous populations, with applications in reliability

The basic result of the paper states: Let F₁, …, F_n, F₁^′,…, F_n^′ have proportional hazard functions with λ₁ ,…, λ_n , λ₁^′ ,…, λ_n^′ as the constants of proportionality. Let X₍₁₎ ≤ … ≤ X_(n) (X₍₁₎^′ ≤ … ≤ X_(n)^′) be the order statistics in a sample of size n from the heterogeneous populations {F₁ ,…, F_n}({F₁^′ ,…, F_n^′}). Then (λ₁ ,…, λ_n) majorizes (λ₁^′ ,…, λ_n^′) implies that (X₍₁₎ ,…, X_(n)) is stochastically larger than (X₍₁₎^′ ,…, X_(n)^′). Earlier results stochastically comparing individual order statistics are shown to be special cases. Applications of the main result are made in the study of the robustness of standard estimates of the failure rate of the exponential distribution, when observations actually come from a set of heterogeneous exponential distributions. Further applications are made to the comparisons of linear combinations of Weibull random variables and of binomial random variables.     

Pattern Matching with Swaps

Let a text string T of n symbols and a pattern string P of m symbols from alphabet Σ be given. A swapped version T′ of T is a length n string derived from T by a series of local swaps (i.e., t′_ℓ ← t_ℓ + 1 and t′_ℓ + 1 ← t_ℓ), where each element can participate in no more than one swap. The pattern matching with swaps problem is that of finding all locations i for which there exists a swapped version T′ of T with an exact matching of P in location i of T′. It has been an open problem whether swapped matching can be done in less than O(nm) time. In this paper we show the first algorithm that solves the pattern matching with swaps problem in time o(nm). We present an algorithm whose time complexity is O(nm^1/3 log m log σ) for a general alphabet Σ, where σ = min(m,Σ).     

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.     

p-Group actions on homology spheres

When an arbitraryp-groupG acts on a _n -homologyn-sphereX, it is proved here that the dimension functionn:S(G)(S(G) is the set of subgroups ofG), defined byn(H)=dimX ^H, (dim here is cohomological dimension) is realised by a real representation ofG, and that there is an equivariant map fromX to the sphere of this representation. A converse is also established.     

On integral Cayley sum graphs

Let S be a subset of a finite abelian group G. The Cayley sum graph Cay⁺(G, S) of G with respect to S is a graph whose vertex set is G and two vertices g and h are joined by an edge if and only if g + h ∈ S. We call a finite abelian group G a Cayley sum integral group if for every subset S of G, Cay⁺(G, S) is integral i.e., all eigenvalues of its adjacency matrix are integers. In this paper, we prove that all Cayley sum integral groups are represented by Z₃ and Zn₂ ⁿ, n ≥ 1, where Z_k is the group of integers modulo k. Also, we classify simple connected cubic integral Cayley sum graphs.     

Optimal Recovery of the Derivative of Periodic Analytic Functions from Hardy Classes

LetS_β{z : |Im z|<β}. For 2π-periodic functions which are analytic inS_βwithp-integrable boundary values, we construct an optimal method of recovery off′(ξ), ξS_β, using information about the valuesf(x₁), mldr;, f(x_n), x_j[0, 2π).     

Transformation graph

The transformation graph G^-+- of a graph G is the graph with vertex set V(G)E(G), in which two vertices u and v are joined by an edge if one of the following conditions holds: (i) u,vV(G) and they are not adjacent in G, (ii) u,vE(G) and they are adjacent in G, (iii) one of u and v is in V(G) while the other is in E(G), and they are not incident in G. In this paper, for any graph G, we determine the connectivity and the independence number of G^-+-. Furthermore, for a graph G of order n4, we show that G^-+- is hamiltonian if and only if G is not isomorphic to any graph in {2K₁+K₂,K₁+K₃}{K_1,n-1,K_1,n-1+e,K_1,n-2+K₁}.     

A distance approximating trees

A 1-approximation of connected graph G=(V,E) is a tree T=(V,E^′) with the same vertex set such that for every two vertices |d_G(u,v)−d_T(u,v)|1. A polynomial time algorithm is designed for finding such a tree.     

Enumeration and limit laws for series–parallel graphs

We show that the number g_n of labelled series–parallel graphs on n vertices is asymptotically g_ngn^−5/2γⁿn!, where γ and g are explicit computable constants. We show that the number of edges in random series–parallel graphs is asymptotically normal with linear mean and variance, and that it is sharply concentrated around its expected value. Similar results are proved for labelled outerplanar graphs and for graphs not containing K_2,3 as a minor.