A sufficient degree condition for a graph to contain all trees of size <Emphasis Type="Italic">k</Emphasis>

The Erdős-Sós conjecture says that a graph G on n vertices and number of edges e(G) > n(k− 1)/2 contains all trees of size k. In this paper we prove a sufficient condition for a graph to contain every tree of size k formulated in terms of the minimum edge degree ζ(G) of a graph G defined as ζ(G) = min{d(u) + d(v) − 2: uv ∈ E(G)}. More precisely, we show that a connected graph G with maximum degree Δ(G) ≥ k and minimum edge degree ζ(G) ≥ 2k − 4 contains every tree of k edges if d _G (x) + d _G (y) ≥ 2k − 4 for all pairs x, y of nonadjacent neighbors of a vertex u of d _G (u) ≥ k.     

Comonotone approximation of twice differentiable periodic functions

In the case where a 2π-periodic function f is twice continuously differentiable on the real axis ℝ and changes its monotonicity at different fixed points y _i ∈ [− π, π), i = 1,…, 2s, s ∈ ℕ (i.e., on ℝ, there exists a set Y := {y _i } _i∈ℤ of points y _i = y _i+2s + 2π such that the function f does not decrease on [y _i , y _i−1] if i is odd and does not increase if i is even), for any natural k and n, n ≥ N(Y, k) = const, we construct a trigonometric polynomial T _n of order ≤n that changes its monotonicity at the same points y _i ∈ Y as f and is such that

Bounding the number of connected components of a real algebraic set

For every polynomial mapf=(f ₁,…,f _k): ℝ ⁿ →ℝ ^k , we consider the number of connected components of its zero set,B(Z _f) and two natural “measures of the complexity off,” that is the triple(n, k, d), d being equal to max(degree off _i), and thek-tuple (Δ₁,...,Δ₄), Δ _k being the Newton polyhedron off _i respectively. Our aim is to boundB(Z _f) by recursive functions of these measures of complexity. In particular, with respect to (n, k, d) we shall improve the well-known Milnor-Thom’s bound μ _d (n)=d(2d−1) ⁿ⁻¹. Considered as a polynomial ind, μ _d (n) has leading coefficient equal to 2 ⁿ⁻¹. We obtain a bound depending onn, d, andk such that ifn is sufficiently larger thank, then it improves μ _d (n) for everyd. In particular, it is asymptotically equal to 1/2(k+1)n ^k−1 dⁿ, ifk is fixed andn tends to infinity. The two bounds are obtained by a similar technique involving a slight modification of Milnor-Thom's argument, Smith's theory, and information about the sum of Betti numbers of complex complete intersections.     

Piecewise Hereditary Nakayama Algebras

Let k be an algebraically closed field. Let Λ be the path algebra over k of the linearly oriented quiver \mathbb A_n\mathbb A_n for n ≥ 3. For r ≥ 2 and n > r we consider the finite dimensional k −algebra Λ(n,r) which is defined as the quotient algebra of Λ by the two sided ideal generated by all paths of length r. We will determine for which pairs (n,r) the algebra Λ(n,r) is piecewise hereditary, so the bounded derived category D ^b (Λ(n,r)) is equivalent to the bounded derived category of a hereditary abelian category H\mathcal H as triangulated category.     

On some characterization of probability distributions in Hilbert spaces

Summary The aim of this paper is to prove the following theorem about characterization of probability distributions in Hilbert spaces:Theorem. — Let x₁, x₂, …, x_n be n (n≥3) independent random variables in the Hilbert spaceH, having their characteristic functionals f_k(t) = E[e^i(t,x _k)], (k=1, 2, …, n): let y₁=x₁ + x_n, y₂=x₂ + x_n, …, y_n−1=x_n−1 + x_n. If the characteristic functional f(t₁, t₂, …, t_n−1) of the random variables (y₁, y₂, …, y_n−1) does not vanish, then the joint distribution of (y₁, y₂, …, y_n−1) determines all the distributions of x₁, x₂, …, x_n up to change of location.     

Immagini inverse dei gruppi di omotopia

Riassunto SeM edN sono varietà poliedriche chiuse connesse ed orientate di dimensioni rispettivem edn, conm≥n>2, edf∶M→N è una trasformazione continua, allora per ognir, minore din e non inferiore a 2, si definisce un omomorfismo indotto ϕ_rπ:_r (N)→H _m-n+r (M) dal quale si ricavano certi invarianti topologici.

---

Résumé Soientm≥n>r≥2 des entiers etM, N des variétés polyédrales closes connexes orientées satisfaisant dimM=m et dimN=n, de plusH _i(M) le groupe de Betti à i dimensions deM,M,π _i (N) le groupe de Hurewicz ài dimensions deN, etf∶M→N une application continue. Alorsf définit, pour,r=2, 3, …n−1, un homomorphisme réciproque ϕ_rπ:_r (N)→H _m-n+r (M) comme il suit. Etant donné un élément α du groupe π_r (N) et uner-sphère continue orientéeS de α, on peut supposer quef ⁻¹(S) soit un polyèdre finiA àm−n+r dimensions. Parf est induit dansA un (m−n+r)-cyclez à coefficients entiers, et la classe d'homologie dez est justement l'image ϕr(α) de α par ϕr. Pourr=1, on obtient un homomorphisme réciproque ϕ_rπ:_r (N)→H _m-n+r (M) du groupe fondamentalF(N) deN dans le groupe d'homologie àm−n+1 dimensions deM. A l'aide des homomorphismes ϕ,,ϕ2,ϕ,3...,ϕn-i, on parvient à certaines expressions caractéristiques dépendantes seulement de la classe d'homotopie def, en particulier on obtient des constantes pour les images des bases de Betti deM, pour Fimage du groupe de torsion deM, et pour l'image réciproque du groupe fondamental deN.

     

On Optimal Orientations of Cartesian Products of Trees

. Let d(D) (resp., d(G)) denote the diameter and r(D) (resp., r(G)) the radius of a digraph D (resp., graph G). Let G×H denote the cartesian product of two graphs G and H. An orientation D of G is said to be (r, d)-invariant if r(D)=r(G) and d(D)=d(G). Let {T _i }, i=1,…,n, where n≥2, be a family of trees. In this paper, we show that the graph ∏ _{i =1} ⁿ T _i admits an (r, d)-invariant orientation provided that d(T ₁)≥d(T ₂)≥4 for n=2, and d(T ₁)≥5 and d(T ₂)≥4 for n≥3. Received: July 30, 1997 Final version received: April 20, 1998     

The smallest degree sum that yields potentially Kr,r-graphic sequences

We consider a variation of a classical Turán-type extremal problem as follows: Determine the smallest even integer σ(K_r,r,n) such that every n-term graphic sequence π = (d₁,d₂,...,d_n) with term sum σ(π) = d₁ + d₂ + ... + d_n ≥ σ(K_r,r,n) is potentially K_r,r-graphic, where K_r,r is an r × r complete bipartite graph, i.e. π has a realization G containing K_r,r as its subgraph. In this paper, the values σ(K_r,r,n) for even r and n ≥ 4r² - r - 6 and for odd r and n ≥ 4r² + 3r - 8 are determined.     

The signed <Emphasis Type="Italic">k</Emphasis>-domination number of directed graphs

Let k ≥ 1 be an integer, and let D = (V; A) be a finite simple digraph, for which d _D ⁻ ≥ k − 1 for all v ɛ V. A function f: V → {−1; 1} is called a signed k-dominating function (SkDF) if f(N ⁻[v]) ≥ k for each vertex v ɛ V. The weight w(f) of f is defined by $ \sum\nolimits_{v \in V} {f(v)} $ \sum\nolimits_{v \in V} {f(v)} . The signed k-domination number for a digraph D is γ _kS (D) = min {w(f|f) is an SkDF of D. In this paper, we initiate the study of signed k-domination in digraphs. In particular, we present some sharp lower bounds for γ _kS (D) in terms of the order, the maximum and minimum outdegree and indegree, and the chromatic number. Some of our results are extensions of well-known lower bounds of the classical signed domination numbers of graphs and digraphs.     

Propertyf −1(S) =g −1(S) for entire and meromorphicP-adic functions

LetW be an algebraically closed filed of characteristic zero, letK be an algebraically closed field of characteristic zero, complete for an ultrametric absolute value, and letA(K) (resp. ℳ(K)) be the set of entire (resp. meromorphic) functions inK. For everyn≥7, we show that the setS _n(b) of zeros of the polynomialx ⁿ−b (b≠0) is such that, iff, g ∈W[x] or iff, g ∈A(K), satisfyf ⁻¹(S _n(b))=g ⁻¹(S _n(b)), thenf ⁿ=g ⁿ. For everyn≥14, we show thatS _n(b) is such that iff, g ∈W({tx}) or iff, g ∈ ℳ(K) satisfyf ⁻¹(S _n(b))=g ⁻¹(S _n(b)), then eitherf ⁿ=g ⁿ, orfg is a constant. Analogous properties are true for complex entire and meromorphic functions withn≥8 andn≥15, respectively. For everyn≥9, we show that the setY _n(c) of zeros of the polynomial , (withc≠0 and 1) is an ursim ofn points forW[x], and forA(K). For everyn≥16, we show thatY _n(c) is an ursim ofn points forW(x), and for ℳ(K). We follow a method based on thep-adic Nevanlinna Theory and use certain improvement of a lemma obtained by Frank and Reinders.     

One sufficient condition for Hamiltonian graphs involving distances

In 1990 G. T. Chen proved that if G is a 2-connected graph of order n and 2|N(x) ∪ N(y)| + d(x) + d(y) ≥ 2n − 1 for each pair of nonadjacent vertices x, y ∈ V (G), then G is Hamiltonian. In this paper we prove that if G is a 2-connected graph of order n and 2|N(x) ∪ N(y)| + d(x)+d(y) ≥ 2n−1 for each pair of nonadjacent vertices x, y ∈ V (G) such that d(x, y) = 2, then G is Hamiltonian.     

The Smallest Degree Sum That Yields Potentially Kr＋1 - K3-Graphic Sequences

Let a（Kr,＋1 - K3,n） be the smallest even integer such that each n-term graphic sequence п= （d1,d2,…dn） with term sum σ（п） = d1 ＋ d2 ＋…＋ dn 〉 σ（Kr＋1 -K3,n） has a realization containing Kr＋1 - K3 as a subgraph, where Kr＋1 -K3 is a graph obtained from a complete graph Kr＋1 by deleting three edges which form a triangle. In this paper, we determine the value σ（Kr＋1 - K3,n） for r ≥ 3 and n ≥ 3r＋ 5.     

Distributions of Points in <Emphasis Type="Italic">d</Emphasis> Dimensions and Large <Emphasis Type="Italic">k</Emphasis>-Point Simplices

We consider a variant of Heilbronn’s triangle problem by investigating for a fixed dimension d≥2 and for integers k≥2 with k≤d distributions of n points in the d-dimensional unit cube [0,1] ^d , such that the minimum volume of the simplices, which are determined by (k+1) of these n points is as large as possible. Denoting by Δ _k,d (n), the supremum of this minimum volume over all distributions of n points in [0,1] ^d , we show that c _k,d ⋅(log n)^1/(d−k+1)/n ^k/(d−k+1)≤Δ _k,d (n)≤c _k,d ′/n ^k/d for fixed 2≤k≤d, and, moreover, for odd integers k≥1, we show the upper bound Δ _k,d (n)≤c _k,d ″/n ^{k/d+(k−1)/(2d(d−1))}, where c _k,d ,c _k,d ′,c _k,d ″>0 are constants. A preliminary version of this paper appeared in COCOON ’05.     

On the Proximal Point Algorithm

Let A be a maximal monotone operator in a real Hilbert space H and let {u _n } be the sequence in H given by the proximal point algorithm, defined by u _n =(I+c _n A)⁻¹(u _n−1−f _n ), ∀ n≥1, with u ₀=z, where c _n >0 and f _n ∈H. We show, among other things, that under suitable conditions, u _n converges weakly or strongly to a zero of A if and only if lim inf  _n→+∞|w _n |<+∞, where w _n =(∑ _k=1 ⁿ c _k )⁻¹∑ _k=1 ⁿ c _k u _k . Our results extend previous results by several authors who obtained similar results by assuming A ⁻¹(0)≠φ.     

Asymptotic Upper Bounds for Ramsey Functions

 We show that for any graph G with N vertices and average degree d, if the average degree of any neighborhood induced subgraph is at most a, then the independence number of G is at least Nf _{a +1}(d), where f _{a +1}(d)=∫₀ ¹(((1−t)^{1/( a +1)})/(a+1+(d−a−1)t))dt. Based on this result, we prove that for any fixed k and l, there holds r(K _k + _l ,K _n )≤ (l+o(1))n ^k /(logn) ^{k −1}. In particular, r(K _k , K _n )≤(1+o(1))n ^{k −1}/(log n) ^{k −2}. Received: May 11, 1998 Final version received: March 24, 1999     

Negative result in pointwise 3-convex polynomial approximation

Let Δ³ be the set of functions three times continuously differentiable on [−1, 1] and such that f″′(x) ≥ 0, x ∈ [−1, 1]. We prove that, for any n ∈ ℕ and r ≥ 5, there exists a function f ∈ C ^r [−1, 1] ⋂ Δ³ [−1, 1] such that ∥f ^(r)∥ _{C[−1, 1]} ≤ 1 and, for an arbitrary algebraic polynomial P ∈ Δ³ [−1, 1], there exists x such that

On simultaneous approximation to a differentiable function and its derivative by inverse Pal-Type interpolation polynomials

Let ξ_{n −1} < ξ_{n −2} < ξ_{n − 2} < ... < ξ₁ be the zeros of the the (n−1)-th Legendre polynomial P_n−1(x) and −1=x_n<x_n−1<...<x₁=1, the zeros of the polynomial . By the theory of the inverse Pal-Type interpolation, for a function f(x)∈C _[−1,1] ¹ , there exists a unique polynomial R_n(x) of degree 2n−2 (if n is even) satisfying conditions R_n(f, ξ_k) = f (ε_k) (1 ⩽ k ⩽ n −1); R¹ _n(f,x_k)=f¹(x_k)(1≤k≤n). This paper discusses the simultaneous approximation to a differentiable function f by inverse Pal-Type interpolation polynomial {R_n(f, x)} (n is even) and the main result of this paper is that if f∈C _[1,1] ^r , r≥2, n≥r+2, and n is even then |R¹ _n(f,x)−f¹(x)|=0(1)|W_n(x)|h(x)·n^3−r·E_2n−r−3(f^(r)) holds uniformly for all x∈[−1,1], where .     

Accuracy of several multidimensional refinable distributions

Compactly supported distributions f₁,..., f_r on ℝ^d are fefinable if each f_i is a finite linear combination of the rescaled and translated distributions f_j(Ax−k), where the translates k are taken along a lattice Γ ⊂ ∝^d and A is a dilation matrix that expansively maps Γ into itself. Refinable distributions satisfy a refinement equation f(x)=Σ_k∈Λ c_k f(Ax−k), where Λ is a finite subset of Γ, the c_k are r×r matrices, and f=(f₁,...,f_r)^T. The accuracy of f is the highest degree p such that all multivariate polynomials q with degree(q)<p are exactly reproduced from linear combinations of translates of f₁,...,f_r along the lattice Γ. We determine the accuracy p from the matrices c_k. Moreover, we determine explicitly the coefficients y_α,i(k) such that x^α=Σ _i=1 ^r Σ_k∈Γy_α,i(k) fi(x+k). These coefficients are multivariate polynomials y_α,i(x) of degree |α| evaluated at lattice points k∈Γ.     

On the general additive divisor problem

We obtain a new upper bound for the sum Σ _h≤H Δ _k (N, h) when 1 ≤ H ≤ N, k ∈ ℕ, k ≥ 3, where Δ _k (N, h) is the (expected) error term in the asymptotic formula for Σ _N<n≤2N d _k (n)d _k (n + h), and d _k (n) is the divisor function generated by ζ(s) ^k . When k = 3, the result improves, for H ≥ N ^1/2, the bound given in a recent work of Baier, Browning, Marasingha and Zhao, who dealt with the case k = 3.     

Nonvanishing derivatives and normal families

We consider the differential operators Ψ _k , defined by Ψ₁(y) =y and Ψ _k+1(y)=yΨ _k y+d/dz(Ψ _k (y)) fork ∈ ℕ fork∈ ℕ. We show that ifF is meromorphic in ℂ and Ψ _k F has no zeros for somek≥3, and if the residues at the simple poles ofF are not positive integers, thenF has the formF(z)=((k-1)z+a)/(z ²+β z+γ) orF(z)=1/(az+β) where α, β, γ ∈ ℂ. If the residues at the simple poles ofF are bounded away from zero, then this also holds fork=2. We further show that, under suitable additional conditions, a family of meromorphic functionsF is normal if each Ψ _k (F) has no zeros. These conditions are satisfied, in particular, if there exists δ>0 such that Re (Res(F, a)) <−δ for all polea of eachF in the family. Using the fact that Ψ _k (f ^′/f) =f ^(k)/f, we deduce in particular that iff andf ^(k) have no zeros for allf in some familyF of meromorphic functions, wherek≥2, then {f ^′/f :f ∈F} is normal. The first author is supported by the German-Israeli Foundation for Scientific Research and Development G.I.F., G-643-117.6/1999, and INTAS-99-00089. The second author thanks the DAAD for supporting a visit to Kiel in June–July 2002. Both authors thank Günter Frank for helpful discussions.