On the chromatic polynomial of a graph

Let P(G,λ) be the chromatic polynomial of a graph G with n vertices, independence number α and clique number ω. We show that for every λ≥n, ()^α≤≤ () ^{n −ω}. We characterize the graphs that yield the lower bound or the upper bound.?These results give new bounds on the mean colour number μ(G) of G: n− (n−ω)() ^{n −ω}≤μ(G)≤n−α() ^α. Received: December 12, 2000 / Accepted: October 18, 2001?Published online February 14, 2002     

On a class of spaces of analytic functions

The spacesb (p, q, λ) (0<p<q⩽∞, 0<λ⩽∞) of functions, analytic in the circle |z|< 1, are introduced, and an unimprovable estimate is obtained for the Taylor coefficients of a functionf∃ b (p, q, λ). It is shown that B(p, q, λ) is the space of fractional derivatives f(α) of order α (−∞<α<1/p−1/q) of a function f of B(s, q, λ), where s=p/(1−αp). Translated from Matematicheskie Zametki, Vol. 21, No. 2, pp. 141–150, February, 1977.     

Precise asymptotic formulas for variational eigencurves of semilinear two-parameter elliptic eigenvalue problems

We consider the two-parameter nonlinear eigenvalue problem?−Δu = μu − λ(u + u ^p + f(u)), u > 0 in Ω, u = 0 on ∂Ω,?where p>1 is a constant and μ,λ>0 are parameters. We establish the asymptotic formulas for the variational eigencurves λ=λ(μ,α) as μ→∞, where α>0 is a normalizing parameter. We emphasize that the critical case from a viewpoint of the two-term asymptotics of the eigencurve is p=3. Moreover, it is shown that p=5/3 is also a critical exponent from a view point of the three-term asymptotics when Ω is a ball or an annulus. This sort of criticality for two-parameter problems seems to be new. Received: February 9, 2002; in final form: April 3, 2002?Published online: April 14, 2003     

BMO-scale of distribution on ℝ n

Let S′ be the class of tempered distributions. For ƒ ∈ S′ we denote by J ^−α ƒ the Bessel potential of ƒ of order α. We prove that if J ^−α ƒ ∈ BMO, then for any λ ∈ (0, 1), J ^−α (f)_λ ∈ BMO, where (f)_λ = λ⁻ⁿ f(φ(λ⁻¹)), φ ∈ S. Also, we give necessary and sufficient conditions in order that the Bessel potential of a tempered distribution of order α > 0 belongs to the VMO space.     

The asymptotic behavior of Chern-Simons Higgs model on a compact Riemann surface with boundary

We study the self-dual Chern-Simons Higgs equation on a compact Riemann surface with the Neumann boundary condition.In the previous paper,we show that the Chern-Simons Higgs equation with parameter λ0 has at least two solutions(uλ1,uλ2) for λ sufficiently large,which satisfy that uλ1→u0 almost everywhere as λ→∞,and that uλ2→∞ almost everywhere as λ→∞,where u 0 is a(negative) Green function on M.In this paper,we study the asymptotic behavior of the solutions as λ→∞,and prove that uλ2-uλ2 converges to a solution of the Kazdan-Warner equation if the geodesic curvature of the boundary M is negative,or the geodesic curvature is nonpositive and the Gauss curvature is negative where the geodesic curvature is zero.     

A remark on absolutely continuous functions in ℝ n

We introduce the notion ofα, λ-absolute continuity for functions of several variables and we compare it with the Hencl’s definition. We obtain that eachα, λ-absolutely continuous function isn, λ-absolutely continuous in the sense of Hencl and hence is continuous, differentiable almost everywhere and satisfies change of variables results based on a coarea formula and an area formula.     

Anisotropic young diagrams and jack symmetric functions

We study the Young lattice with the edge multiplicitiesϰ _α (λ, ⋏) arising in the simplest Pieri formula for Jack symmetric polynomialsP _λ (x; α) with parameter α. A new proof of Stanley’s α-version of the hook formula is given. We also prove the formula whereϕ(λ) = ∏ _b∈λ (a(b)α +l(b) + 1)⁻¹ andc _α(b) is the α-contents of the new boxb=⋏/λ. Partially supported by the Federal Grant Program “Integration,” No. 326.53, and by MSRI at Berkeley. St. Petersburg Division of the V. A. Steklov Mathematical Institute. Translated from Funksional’nyi Analiz i Ego Prilozheniya, Vol. 34, No. 1, pp. 51–64, January–March, 200. Translated by S. V. Kerov     

Some Extremal Functions in Fourier Analysis, III

We obtain the best approximation in L ¹(ℝ), by entire functions of exponential type, for a class of even functions that includes e ^−λ|x|, where λ>0, log |x| and |x| ^α , where −1<α<1. We also give periodic versions of these results where the approximating functions are trigonometric polynomials of bounded degree.     

On universality of the Lerch zeta-function

It is known that the Lerch zeta-function L(λ, α, s) with transcendental parameter α is universal in the Voronin sense; i.e., every analytic function can be approximated by shifts L(λ, α, s + iτ) uniformly on compact subsets of some region. In this paper, the universality for some classes of composite functions F(L(λ, α, s)) is obtained. In particular, general theorems imply the universality of the functions sin(L(λ, α, s)) and sinh(L(λ, α, s)).     

Further Results on the Existence of Splitting BIBDs and Application to Authentication Codes

Let (v,u×c,λ)-splitting BIBD denote a (v,u×c,λ)-splitting balanced incomplete block design of order v with block size u×c and index λ. Necessary conditions for the existence of a (v,u×c,λ)-splitting BIBD are v≥uc, λ(v−1)≡0 (mod c(u−1)) and λ v(v−1)≡0 (mod (c ² u(u−1))). We show in this paper that the necessary conditions for the existence of a (v,3×3,λ)-splitting BIBD are also sufficient with possible exceptions when (1) (v,λ)∈{(55,1),(39,9k):k=1,2,…}, (2) λ≡0 (mod 54) and v≡0 (mod 2). We also show that there exists a (v,3×4,1)-splitting BIBD when v≡1 (mod 96). As its application, we obtain a new infinite class of optimal 4-splitting authentication codes.     

The Ξ operator and its relation to Krein's spectral shift function

We explore connections between Krein's spectral shift function ζ(λ,H ₀, H) associated with the pair of self-adjoint operators (H ₀, H),H=H ₀+V, in a Hilbert spaceH and the recently introduced concept of a spectral shift operator Ξ(J+K ^*(H ₀−λ−i0)⁻¹ K) associated with the operator-valued Herglotz functionJ+K ^*(H ₀−z)⁻¹ K, Im(z)>0 inH, whereV=KJK ^* andJ=sgn(V). Our principal results include a new representation for ζ(λ,H ₀,H) in terms of an averaged index for the Fredholm pair of self-adjoint spectral projections (E J+A(λ)+tB(λ)(−∞, 0)),E _J((−∞, 0))), ℝ, whereA(λ)=Re(K ^*(H ₀−λ−i0⁻¹ K),B(λ)=Im(K ^*(H ₀−λ-i0)⁻¹ K) a.e. Moreover, introducing the new concept of a trindex for a pair of operators (A, P) inH, whereA is bounded andP is an orthogonal projection, we prove that ζ(λ,H ₀, H) coincides with the trindex associated with the pair (Ξ(J+K ^*(H ₀−λ−i0)K), Ξ(J)). In addition, we discuss a variant of the Birman-Krein formula relating the trindex of a pair of Ξ operators and the Fredholm determinant of the abstract scattering matrix. We also provide a generalization of the classical Birman—Schwinger principle, replacing the traditional eigenvalue counting functions by appropriate spectral shift functions.     

The convolution structure for Jacobi function expansions

The product ϕ _λ ^(α,β) (t₁)ϕ _λ ^(α,β) (t₂) of two Jacobi functions is expressed as an integral in terms of ϕ _λ ^(α,β) (t₃) with explicit non-negative kernel, when α≧β≧−1/2. The resulting convolution structure for Jacobi function expansions is studied. For special values of α and β the results are known from the theory of symmetric spaces.     

Asymptotic representations of solutions of nonautonomous ordinary differential equations with regularly varying nonlinearities

We obtain asymptotic representations as t ↑ ω, ω ≤ + ∞, for all possible types of P _ω(Y ₀, λ ₀)-solutions (where Y ₀ is zero or ±∞ and −∞ ≤ λ₀ ≤ +∞) of nonlinear differential equations y ⁽ⁿ⁾ = α ₀ p(t)φ(y), where α ₀ ∈ {−1, 1}, p: [a, ω[→]0,+∞[ is a continuous function, and φ is a continuous regularly varying function in a one-sided neighborhood of Y ₀.     

Discrete spectrum in the gaps of a perturbed pseudorelativistic hamiltonian

The pseudorelativistic Hamiltonian is considered under wide conditions on potentials A(x), W(x). It is assumed that a real point λ is regular for G_1/2. Let G_1/2(α)=G_1/2−αV, where α>0, V(x)≥0, and V ∈L _d(ℝ^d). Denote by N(λ, α) the number of eigenvalues of G_1/2(t) that cross the point λ as t increases from 0 to α. A Weyl-type asymptotics is obtained for N(λ, α) as α→∞. Bibliography: 5 titles. To O. A. Ladyzhenskaya Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 249, 1997. pp. 102–117. Translated by A. B. Pushnitskii.     

Sum of sequence spaces and matrix transformations mapping in s α 0 ((Δ ? λ I ) h ) + s β ( c ) ((Δ ? μ I ) l )

We deal with the sum of sequence spaces. Then we apply these results to characterize matrix transformations mapping between s ^h,l (λ, μ) = s _α ⁰((Δ − λI) ^h ) + s _β ^(c)((Δ − μI) ^l ) and s _γ . Among other things the aim of this paper is to reduce the set (s ^h,l (λ, μ), s _γ to a set of the form S _τ,γ .      

An operator approach to zero-sum repeated games

We consider two person zero-sum stochastic games. The recursive formula for the valuesvλ (resp.v _n) of the discounted (resp. finitely repeated) version can be written in terms of a single basic operator Φ(α,f) where α is the weight on the present payoff andf the future payoff. We give sufficient conditions in terms of Φ(α,f) and its derivative at 0 for limv _n and limvλ to exist and to be equal. We apply these results to obtain such convergence properties for absorbing games with compact action spaces and incomplete information games.     

A note on the Multiplier Conjecture

In order to identify multipliers of abelian (υ, k, λ)-difference sets the First and the Second Multiplier Theorem of Hall, Ryser and Chowla, resp. of Hall and Menon, need a divisor m of n = k − λ that is coprime to υ. Moreover, both theorems require that m > λ. The famous Multiplier Conjecture asserts that the restriction m > λ is not necessary. We present a generalization of the Second Multiplier Theorem where m is not necessarily coprime to υ. Here the requirement that m > λ generalizes to the condition m/(υ, m) > λ. This gives rise to a generalized Multiplier Conjecture which asserts that this condition is not necessary. We disprove this conjecture by showing that there exist counterexamples.     

On the non-existence of pair covering designs with at least as many points as blocks

We establish new lower bounds on the pair covering number C _λ (υ,k) for infinitely many values of υ, k and λ, including infinitely many values of υ and k for λ=1. Here, C _λ (υ,k) denotes the minimum number of k-subsets of a υ-set of points such that each pair of points occurs in at least λ of the k-subsets. We use these results to prove simple numerical conditions which are both necessary and sufficient for the existence of (K _k − e)-designs with more points than blocks.     

A Shy Invariant of Graphs

 Moving from a well known result of Hammer, Hansen, and Simeone, we introduce a new graph invariant, say λ(G) referring to any graph G. It is a non-negative integer which is non-zero whenever G contains particular induced odd cycles or, equivalently, admits a particular minimum clique-partition. We show that λ(G) can be efficiently evaluated and that its determination allows one to reduce the hard problem of computing a minimum clique-cover of a graph to an identical problem of smaller size and special structure. Furthermore, one has α(G)≤θ(G)−λ(G), where α(G) and θ(G) respectively denote the cardinality of a maximum stable set of G and of a minimum clique-partition of G. Received: April 12, 1999 Final version received: September 15, 2000     

Equality of multiplicity free skew characters

In this paper we show that two skew diagrams λ/μ and α/β can represent the same multiplicity free skew character [λ/μ]=[α/β] only in the the trivial cases when λ/μ and α/β are the same up to translation or rotation or if λ=α is a staircase partition λ=(l,l−1,…,2,1) and λ/μ and α/β are conjugate of each other.