On the Positivity of the Fundamental Polynomials for Generalized Hermite–Fejér Interpolation on the Chebyshev Nodes

It is shown that the fundamental polynomials for (0, 1, …, 2m+1) Hermite–Fejér interpolation on the zeros of the Chebyshev polynomials of the first kind are non-negative for −1x1, thereby generalising a well-known property of the original Hermite–Fejér interpolation method. As an application of the result, Korovkin's 10theorem on monotone operators is used to present a new proof that the (0, 1, …, 2m+1) Hermite–Fejér interpolation polynomials offC[−1, 1], based onnChebyshev nodes, converge uniformly tofasn→∞.     

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.     

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.     

Ratewise-optimal non-sequential search strategies under constraints on the tests

Already in his Lectures on Search [A. Rényi, Lectures on the theory of search, University of North Carolina, Chapel Hill, Institute of Statistics, Mimeo Series No. 6007, 1969. [11]] Renyi suggested to consider a search problem, where an unknown is to be found by asking for containment in a minimal number m(n,k) of subsets A₁,…,A_m with the restrictions |A_i|k<n/2 for i=1,2,…,m.Katona gave in 1966 the lower bound m(n,k)logn/h(k/n) in terms of binary entropy and the upper bound m(n,k)(logn+1)/logn/k·n/k, which was improved by Wegener in 1979 to m(n,k)logn/logn/k(n/k-1).We prove here for k=pn that m(n,k)=logn+o(logn)/h(p), that is, ratewise optimality of the entropy bound: .Actually this work was motivated by a more recent study of Karpovsky, Chakrabarty, Levitin and Avresky of a problem on fault diagnosis in hypercubes, which amounts to finding the minimal number M(n,r) of Hamming balls of radius r=ρn with in the Hamming space , which separate the vertices. Their bounds on M(n,r) are far from being optimal. We establish bounds implying

However, it must be emphasized that the methods of prove for our two upper bounds are quite different.     

On linearly related sequences of derivatives of orthogonal polynomials

We discuss an inverse problem in the theory of (standard) orthogonal polynomials involving two orthogonal polynomial families (P_n)_n and (Q_n)_n whose derivatives of higher orders m and k (resp.) are connected by a linear algebraic structure relation such as

for all n=0,1,2,…, where M and N are fixed nonnegative integer numbers, and r_i,n and s_i,n are given complex parameters satisfying some natural conditions. Let u and v be the moment regular functionals associated with (P_n)_n and (Q_n)_n (resp.). Assuming 0mk, we prove the existence of four polynomials Φ_M+m+i and Ψ_N+k+i, of degrees M+m+i and N+k+i (resp.), such that

the (k−m)th-derivative, as well as the left-product of a functional by a polynomial, being defined in the usual sense of the theory of distributions. If k=m, then u and v are connected by a rational modification. If k=m+1, then both u and v are semiclassical linear functionals, which are also connected by a rational modification. When k>m, the Stieltjes transform associated with u satisfies a non-homogeneous linear ordinary differential equation of order k−m with polynomial coefficients.     

Generating random correlation matrices based on partial correlations

A d-dimensional positive definite correlation matrix R=(ρ_ij) can be parametrized in terms of the correlations ρ_i,i+1 for i=1,…,d-1, and the partial correlations ρ_{ij|i+1,…j-1} for j-i2. These parameters can independently take values in the interval (-1,1). Hence we can generate a random positive definite correlation matrix by choosing independent distributions F_ij, 1i<jd, for these parameters. We obtain conditions on the F_ij so that the joint density of (ρ_ij) is proportional to a power of det(R) and hence independent of the order of indices defining the sequence of partial correlations. As a special case, we have a simple construction for generating R that is uniform over the space of positive definite correlation matrices. As a byproduct, we determine the volume of the set of correlation matrices in -dimensional space. To prove our results, we obtain a simple remarkable identity which expresses det(R) as a function of ρ_i,i+1 for i=1,…,d-1, and ρ_{ij|i+1,…j-1} for j-i2.     

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.     

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.     

A pointwise convergence for Sobolev space functions

Let 1<p<∞, and k,m be positive integers such that 0(k−2m)pn. Suppose ΩRⁿ is an open set, and Δ is the Laplacian operator. We will show that there is a sequence of positive constants c_j such that for every f in the Sobolev space W^k,p(Ω), for all xΩ except on a set whose Bessel capacity B_k−2m,p is zero.     

Rook-by-rook rook theory: Bijective proofs of rook and hit equivalences

Suppose μ and ν are integer partitions of n, and N>n. It is well known that the Ferrers boards associated to μ and ν are rook-equivalent iff the multisets [μ_i+i:1iN] and [ν_i+i:1iN] are equal. We use the Garsia–Milne involution principle to produce a bijective proof of this theorem in which non-attacking rook placements for μ are explicitly matched with corresponding placements for ν. One byproduct is a direct combinatorial proof that the matrix of Stirling numbers of the first kind is the inverse of the matrix of Stirling numbers of the second kind. We also prove q-analogues and p,q-analogues of these results. We also use the Garsia–Milne involution principle to show that for any two rook boards B and B^′, if B and B^′ are bijectively rook-equivalent, then B and B^′ are bijectively hit-equivalent.     

-Linked planar graphs

A graph G is (m,n)-linked if for any two disjoint subsets R,BV(G) with |R|m and |B|n, G has two disjoint connected subgraphs containing R and B, respectively. We shall prove that a planar graph with at least six vertices is (3,3)-linked if and only if G is 4-connected and maximal.     

On constants in some inequalities for intermediate derivatives on a finite interval

Let L_q (1q<∞) be the space of functions f measurable on I=[−1,1] and integrable to the power q, with normL_∞ is the space of functions measurable on I with normWe denote by AC the set of all functions absolutely continuous on I. For nN, q[1,∞] we setW_n,q={f:f⁽ⁿ⁻¹⁾AC, f⁽ⁿ⁾L_q}.In this paper, we consider the problem of accuracy of constants A, B in the inequalities (1)|| f^(m)||_qA|| f||_p+B|| f^(m+k+1)||_r, mN, kW; p,q,r[1,∞], fW_m+k+1,r.     

On a problem of H. Shapiro

Let μ be a real measure on the line such that its Poisson integral M(z) converges and satisfies|M(x+iy)|Ae^−cyα, y→+∞,for some constants A,c>0 and 0<α1. We show that for 1/2<α1 the measure μ must have many sign changes on both positive and negative rays. For 0<α1/2 this is true for at least one of the rays, and not always true for both rays. Asymptotical bounds for the number of sign changes are given which are sharp in some sense.     

On the chromatic number of random graphs

In this paper we consider the classical Erdős–Rényi model of random graphs G_n,p. We show that for p=p(n)n^−3/4−δ, for any fixed δ>0, the chromatic number χ(G_n,p) is a.a.s. ℓ, ℓ+1, or ℓ+2, where ℓ is the maximum integer satisfying 2(ℓ−1)log(ℓ−1)p(n−1).     

Constructing set systems with prescribed intersection sizes

Let f be an n-variable polynomial with positive integer coefficients, and let be a set system on the n-element universe. We define a set system and prove that f(H_i1∩H_i2∩∩H_ik)=|G_i1∩G_i2∩∩G_ik|, for any 1km, where f(H_i1∩H_i2∩∩H_ik) denotes the value of f on the characteristic vector of H_i1∩H_i2∩∩H_ik. The construction of is a straightforward polynomial-time algorithm from the set system and the polynomial f. In this paper we use this algorithm for constructing set systems with prescribed intersection sizes modulo an integer. As a by-product of our method, some upper bounds on the number of sets in set systems with prescribed intersection sizes are extended.     

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.

On sharp Burkholder–Rosenthal-type inequalities for infinite-degree U-statistics

In this paper, we present a method that allows one to obtain a number of sharp inequalities for expectations of functions of infinite-degree U-statistics. Using the approach, we prove, in particular, the following result: Let D be the class of functions f :R₊→R₊ such that the function f(x+z)−f(x) is concave in xR₊ for all zR₊. Then the following estimate holds: for all fD and all U-statistics ∑_1i1<<ilnY_i1,…,il(X_i1,…,X_il) with nonnegative kernels Y_i1,…,il :R^l→R₊, 1i_kn; i_r≠i_s, r≠s; k,r,s=1,…,l; l=0,…,m, in independent r.v.'s X₁,…,X_n. Similar inequality holds for sums of decoupled U-statistics. The class D is quite wide and includes all nonnegative twice differentiable functions f such that the function f″(x) is nonincreasing in x>0, and, in particular, the power functions f(x)=x^t, 1<t2; the power functions multiplied by logarithm f(x)= (x+x₀)^t ln(x+x₀), 1<t<2, x₀max(e^{(3t2−6t+2)/(t(t−1)(2−t))},1); and the entropy-type functions f(x)=(x+x₀)ln(x+x₀), x₀1. As an application of the results, we determine the best constants in Burkholder–Rosenthal-type inequalities for sums of U-statistics and prove new decoupling inequalities for those objects. The results obtained in the paper are, to our knowledge, the first known results on the best constants in sharp moment estimates for U-statistics of a general type.     

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.     

Delay optimization of linear depth boolean circuits with prescribed input arrival times

We consider boolean circuits C over the basis Ω={,} with inputs x₁, x₂,…,x_n for which arrival times are given. For 1in we define the delay of x_i in C as the sum of t_i and the number of gates on a longest directed path in C starting at x_i. The delay of C is defined as the maximum delay of an input.Given a function of the form

f(x₁,x₂,…,x_n)=g_n−1(g_n−2(…g₃(g₂(g₁(x₁,x₂),x₃),x₄)…,x_n−1),x_n)