The tree number of a graph with a given girth

A family of subtrees of a graphG whose edge sets form a partition of the edge set ofG is called atree decomposition ofG. The minimum number of trees in a tree decomposition ofG is called thetree number ofG and is denoted by(G). It is known that ifG is connected then(G) |G|/2. In this paper we show that ifG is connected and has girthg 5 then(G) |G|/g + 1. Surprisingly, the case wheng = 4 seems to be more difficult. We conjecture that in this case(G) |G|/4 + 1 and show a wide class of graphs that satisfy it. Also, some special graphs like complete bipartite graphs andn-dimensional cubes, for which we determine their tree numbers, satisfy it. In the general case we prove the weaker inequality(G) (|G| – 1)/3 + 1.     

Some functionals over a compact Minkovskii space

In this paper we obtain estimates which are order-exact for the projection and Macphail constants of an arbitrary n-dimensional Banach space: 1(X)n, 1/n₁(X)1/n.Translated from Matematicheskii Zametki, Vol. 10, No. 4, pp. 453–457, 1971.     

Function Spaces of Posets with Projections

This paper investigates function spaces of structures consisting of a partially ordered set together with some directed family of projections.More precisely, given a fixed directed index set (I,), we consider triples (D,,(p _i ) _iI ) with (D,) a poset and (p _i ) _iI a monotone net of projections of D. We call them (I,)-pop's (posets with projections). Our main purpose is to study structure preserving maps between (I,)-pop's. Such homomorphisms respect both order and projections.Any (I,)-pop is known to induce a uniformity and thus a topology. The set of all homomorphisms between two (I,)-pop's turns out to form an (I,)-pop itself. We show that its uniformity is the uniformity of uniform convergence. This enables us to prove that properties such as completeness and compactness transfer to function pop's.Concerning categorical properties of (I,)-pop's, we will see that we are in a lucky situation from a computer scientist's point of view: we obtain Cartesian closed categories. Moreover, by a D -construction we get (I,)-pop's that are isomorphic to their own exponent. This yields new models for the untyped -calculus.     

On elementary equivalence and isomorphism of clone segments

The principal application of a general theorem proved here shows that for any choice 1mnp of integers there exist metric spacesX andY such that the initialk-segments of their clones of continuous maps coincide exactly whenkm, are isomorphic exactly whenkn, and are elementarily equivalent exactly whenkp.Dedicated to Prof. László Fuchs on the occasion of his 70th birthday     

D λ -cycles in 3-cyclable graphs

Letk and be positive integers, andG a 2-connected graph of ordern with minimum degree and independence number. A cycleC ofG is called aD -cycle if every component ofG – V(C) has order smaller than. The graphG isk-cyclable if anyk vertices ofG lie on a common cycle. A previous result of the author is that if k 2, G isk-connected and every connected subgraphH ofG of order has at leastn +k ² + 1/k + 1 – vertices outsideH adjacent to at least one vertex ofH, thenG contains aD -cycle. Here it is conjectured that k-connected can be replaced by k-cyclable, and this is proved fork = 3. As a consequence it is shown that ifn 4 – 6, or ifG is triangle-free andn 8 – 10, thenG contains aD ₃-cycle orG , where denotes a well-known class of nonhamiltonian graphs of connectivity 2. As an analogue of a result of Nash-Williams it follows that ifn 4 – 6 and – 1, thenG is hamiltonian orG . The results are all best possible and compare favorably with recent results on hamiltonicity of graphs which are close to claw-free.     

Randomly Weighted Sums of Subexponential Random Variables with Application to Ruin Theory

Let {X _k , 1 k n} be n independent and real-valued random variables with common subexponential distribution function, and let {k, 1 k n} be other n random variables independent of {X _k , 1 k n} and satisfying a _k b for some 0 < a b < for all 1 k n. This paper proves that the asymptotic relations P (max_{1 m n k=1} ^m _k X _k > x) P (sum _k=1 ⁿ _k X _k > x) sum _k=1 ⁿ P ( _k X _k > x) hold as x . In doing so, no any assumption is made on the dependence structure of the sequence { _k , 1 k n}. An application to ruin theory is proposed.     

Asymptotic behavior of the dwell time distribution for a random walk on a positive semi-axis

Let ₁, ₂, ... be a sequence of independent identically distributed random variables with zero means. We consider the functional _n = _k=o ⁿ (S _k ) where S₁=0, S_k= _i=1 ^k _i (k1) and(x)=1 for x0,(x) = 0 for x<0. It is readily seen that _n is the time spent by the random walk S_n, n0, on the positive semi-axis after n steps. For the simplest walk the asymptotics of the distribution P (_n = k) for n and k, as well as for k = O(n) and k/n<1, was studied in [1]. In this paper we obtain the asymptotic expansions in powers of n^–1 of the probabilities P(h_n = nx) and P(nx_{1 n} nx₂) for 0<₁, x = k/n ₂<1, 0<₁x₁2₂<1.Translated from Matematicheskie Zametki, Vol. 15, No. 4, pp. 613–620, April, 1974.The author wishes to thank B. A. Rogozin for valuable discussions in the course of his work.     

Steiner minimal trees for regular polygons

Fifty years ago Jarnik and Kössler showed that a Steiner minimal tree for the vertices of a regularn-gon contains Steiner points for 3 n5 and contains no Steiner point forn=6 andn13. We complete the story by showing that the case for 7n12 is the same asn13. We also show that the set ofn equally spaced points yields the longest Steiner minimal tree among all sets ofn cocircular points on a given circle.     

On Large Values of the Divisor Function

Let d(n) denote the divisor function, and let D(X) denote the maximal value of d(n) for n X. For 0 < z 1, both lower and upper bounds are given for the number of integersn with n X, zD(X) d(n).     

On the Approximation of Functions on Locally Compact Abelian Groups

Questions of approximative nature are considered for a space of functions L ^p(G, ), 1 p , defined on a locally compact abelian Hausdorff group G with Haar measure . The approximating subspaces which are analogs of the space of exponential type entire functions are introduced.     

On context patterns associated with concept lattices

In this paper, we consider the following reconstruction problem: Given two ordered sets (G, ) and (M, ) representing join- and meet-irreducible elements, respectively together with three relationsJ,, onG×M modelling comparability (gm) and maximal noncomparability with respect tog (gm, butgm*) and with respect tom (gm, butgm*). We determine necessary and sufficient conditions for the existence of a finite latticeL and injections :GJ(L) and :MM(L) such that the given order relations and the abstract relations coincide with the one induced by the latticeL.     

On a Lower Bound of L p Norms in the Central Limit Theorem for ϕ-Mixing Random Variables

We derive lower bounds of the L _p norms _np for all p, 1p, in the central limit theorem for -mixing random variables with finite sixth-order moments in a strictly stationary case and finite eighth-order moments in a not necessarily stationary one.     

Approximation of differentiable functions by polynomial splines in domains with external peaks

For unbounded domains with external power-type peaks, we propose a method for the approximation of functionsf(x) w _p ^r () by polynomial splines in the metricw _p ^r (), 1pq, and present the corresponding estimates.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 46, No. 9, pp. 1224–1233, September, 1994.     

L r Estimates for Degenerate Elliptic Problems

We prove L ^r estimates for the Dirichlet problem –div(a(x,u,Du))=f with f in L ^q for 1q+, where the operator satisfies (|s|)|| ^p a(x,s,), with p>1. These estimates are obtained without symmetrization and are sharp in some cases.     

Conditions for non-oscillation of singular linear differential equations of second order

Conditions are found in the fulfillment of which each non-trivial solution of the equation u+ (t)u+(t)u=0, where(t) L(a, b) and (t–a)(t–b)(t) L(a, b) has not more than one zero on the interval atb.Translated from Matematicheskie Zametki, Vol. 6, No. 5, pp. 633–639, November, 1969.     

Kite-freeP- andQ-polynomial schemes

LetY = (X, {R _i } _oid) denote aP-polynomial association scheme. By a kite of lengthi (2 i d) inY, we mean a 4-tuplexyzu (x, y, z, u X) such that(x, y) R ₁,(x, z) R ₁,(y, z) R ₁,(u, y) R _i–1,(u, z) R _i–1,(u, x) R _i. Our main result in this paper is the following.     

On the rank of a spectral function

Let P(x), 0 x 1, be an absolutely continuous spectral function in the separable Hilbert spacesS. If the vectors h_j, j=1, 2, ..., s; s are such that the set P(x)h_j is complete inS, then the rank of the function P(x) equals the general rank of the matrix-function d/dxP(x)h_i,h_js₁.Translated from Matematicheskie Zametki, Vol. 5, No. 4, pp. 457–460, April, 1969.     

Some functional inequalities and their Baire category properties

Summary In the paper we consider, from a topological point of view, the set of all continuous functionsf:I I for which the unique continuous solution:I – [0, ) of(f(x)) (x, (x)) and(x, (x)) (f(x)) (x, (x)), respectively, is the zero function. We obtain also some corollaries on the qualitative theory of the functional equation(f(x)) = g(x, (x)). No assumption on the iterative behaviour off is imposed.     

Über Positive Resolventenwerte Positiver Operatoren

In this paper we study the positive resolvent values of positive operators respectively of positive elements in Banach lattice ordered algebras. In the matrix case these values are just the inverse M-matrices. One of the main results is the following: Let A be a Banach lattice ordered algebra. A positive invertible element xA is a resolvent value of a positive element yA if and only if the element x satisfies the negative principle: If aA, < 0 and xaa then xa 0.     

Vanishing of the costate in pontryagin’s maximum principle and singular time optimal controls

We provide examples of time and norm optimal controls that satisfy Pontryagins maximum principle in an interval 0 t T but with a costate that vanishes in 0 t T - with < T. A refinement of this construction produces time optimal controls which do not satisfy the maximum principle, even in weak form. On the positive side, we show that when we drive to zero the costate is nonzero in the whole control interval.