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.     

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 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.     

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.

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.     

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.     

Weak Copositive and Intertwining Approximation

It is known that shape preserving approximation has lower rates than unconstrained approximation. This is especially true for copositive and intertwining approximations. ForfL_p, 1p<∞, the former only has rateω(f, n⁻¹)_p, and the latter cannot even be bounded byC f_p. In this paper, we discuss various ways to relax the restrictions in these approximations and conclude that the most sensible way is the so-calledalmostcopositive/intertwining approximation in which one relaxes the restriction on the approximants in a neighborhood of radiusΔ_n(y_j) of each sign changey_j.     

Entropy numbers in sequence spaces with an application to weighted function spaces

We determine the exact asymptotic behaviour of entropy numbers of diagonal operators from ℓ_p to ℓ_q, 0<q<p∞, under mild regularity conditions on the generating diagonal sequence. On one hand, this is a quantitative version of Pitt's theorem for diagonal operators, and on the other hand it is a limiting case of results by Carl. An application to embeddings of weighted Besov and Triebel–Lizorkin spaces is also given.     

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.     

-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 the Norm of the Metric Projections

LetXbe a Banach space. GivenMa subspace ofXwe denote withP_Mthe metric projection ontoM. We defineπ(X) sup{P_M: Ma proximinal subspace ofX}. In this paper we give a bound forπ(X). In particular, whenX=L_p, we obtain the inequality P_M2^|2/p−1|, for every subspaceMofL_p. We also show thatπ(X)=π(X*).     

Radon, Cosine and Sine Transforms on Real Hyperbolic Space

New pointwise inversion formulae are obtained for the d-dimensional totally geodesic Radon transform on the n-dimensional real hyperbolic space, 1dn−1, in terms of polynomials of the Laplace–Beltrami operator and intertwining fractional integrals. Similar results are established for hyperbolic cosine and sine transforms.     

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→∞.     

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.     

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.     

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.     

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.     

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)