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

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.     

A characterization of Q-polynomial distance-regular graphs

Let Γ denote a distance-regular graph with diameter D3. Let θ denote a nontrivial eigenvalue of Γ and let denote the corresponding dual eigenvalue sequence. In this paper we prove that Γ is Q-polynomial with respect to θ if and only if the following (i)–(iii) hold:

(i) There exist such that

(1)

(ii) There exist such that the intersection numbers a_i satisfy

for 0iD, where and are the scalars which satisfy Eq. (1) for i=0, i=D, respectively.

(iii) for 1iD.

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.     

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.     

Optimal Sobolev Imbeddings Involving Rearrangement-Invariant Quasinorms

Let m and n be positive integers with n2 and 1mn−1. We study rearrangement-invariant quasinorms _R and _D on functions f: (0, 1)→ such that to each bounded domain Ω in ⁿ, with Lebesgue measure |Ω|, there corresponds C=C(|Ω|)>0 for which one has the Sobolev imbedding inequality _R(u*(|Ω| t))C_D(|^mu|* (|Ω| t)), uC^m₀(Ω), involving the nonincreasing rearrangements of u and a certain mth order gradient of u. When m=1 we deal, in fact, with a closely related imbedding inequality of Talenti, in which _D need not be rearrangement-invariant, _R(u*(|Ω| t))C_D((d/dt) ∫_{{x ⁿ : |u(x)|>u*(|Ω| t)}} |(u)(x)| dx), uC¹₀(Ω). In both cases we are especially interested in when the quasinorms are optimal, in the sense that _R cannot be replaced by an essentially larger quasinorm and _D cannot be replaced by an essentially smaller one. Our results yield best possible refinements of such (limiting) Sobolev inequalities as those of Trudinger, Strichartz, Hansson, Brézis, and Wainger.     

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.     

The Approximation Functional and Interpolation with Perturbed Continuity

The continuity conditions at the endpoints of interpolation theorems, Ta_BjM_j a_Aj for j=0, 1, can be written with the help of the approximation functional: E(t, Ta; B₁, B₀)_L^∞M₀ a_A0 and E(t, Ta; B₀, B₁)_L^∞M₁ a_A1. As a special case of the results we present here we show that in the hypotheses of the interpolation theorem the L^∞ norms can be replaced by BMO( ₊) norms. This leads to a strong version of the Stein-Weiss theorem on interpolation with change of measure. Another application of our results is that the condition fL⁰, i.e., f*L^∞, where f*(γ)=μ{|f|>γ} is the distribution function of f, can be replaced in interpolation with L(p, q) spaces by the weaker f*BMO( ₊).     

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.     

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.     

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.

Widths and shape-preserving widths of Sobolev-type classes of s-monotone functions

Let I be a finite interval, , and 1p∞. Given a set M, of functions defined on I, denote by the subset of all functions yM such that the s-difference is nonnegative on I, τ>0. Further, denote by the Sobolev class of functions x on I with the seminorm x^(r)_Lp1. We obtain the exact orders of the Kolmogorov and the linear widths, and of the shape-preserving widths of the classes in L_q for s>r+1 and (r,p,q)≠(1,1,∞). We show that while the widths of the classes depend in an essential way on the parameter s, which characterizes the shape of functions, the shape-preserving widths of these classes remain asymptotically ≈n^-2.     

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

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.     

Best constants of harmonic approximation on classes associated with the Laplace operator

We compute the best constants of approximation by entire functions of spherical type and by trigonometric polynomials of spherical degree on classes of functions f satisfying the condition Δ^kf_Lp1, where p=1 or 2 and Δ is the Laplace operator.     

Histopolating splines

Given an integrable function f, we are concerned with the construction of a spline H_n(f) of degree n with prescribed knots that satisfies the histopolation conditions

for some fixed . Additionally, the resulting spline operator should be local and reproduce all polynomials of degree n. Our approach of generating such a histospline is based on a local spline interpolation operator that is exact for all polynomials of degree n.     

On the pullback equation

We discuss the existence of a diffeomorphism such that

φ^*(g)=f