共查询到20条相似文献,搜索用时 31 毫秒
1.
I. P. Chukhrov 《Journal of Applied and Industrial Mathematics》2012,6(1):42-55
Studying the extreme kernel face complexes of a given dimension, we obtain some lower estimates of the number of shortest
face complexes in the n-dimensional unit cube. The number of shortest complexes of k-dimensional faces is shown to be of the same logarithm order as the number of complexes consisting of at most 2
n−1 different k-dimensional faces if 1 ≤ k ≤ c · n and c < 0.5. This implies similar lower bounds for the maximum length of the kernel DNFs and the number of the shortest DNFs of
Boolean functions. 相似文献
2.
Clear effects criterion is one of the important rules for selecting optimal fractional factorial designs, and it has become
an active research issue in recent years. Tang et al. derived upper and lower bounds on the maximum number of clear two-factor
interactions (2fi’s) in 2
n−(n−k) fractional factorial designs of resolutions III and IV by constructing a 2
n−(n−k) design for given k, which are only restricted for the symmetrical case. This paper proposes and studies the clear effects problem for the asymmetrical
case. It improves the construction method of Tang et al. for 2
n−(n−k) designs with resolution III and derives the upper and lower bounds on the maximum number of clear two-factor interaction
components (2fic’s) in 4
m
2
n
designs with resolutions III and IV. The lower bounds are achieved by constructing specific designs. Comparisons show that
the number of clear 2fic’s in the resulting design attains its maximum number in many cases, which reveals that the construction
methods are satisfactory when they are used to construct 4
m
2
n
designs under the clear effects criterion.
This work was supported by the National Natural Science Foundation of China (Grant Nos. 10571093, 10671099 and 10771123),
the Research Foundation for Doctor Programme (Grant No. 20050055038) and the Natural Science Foundation of Shandong Province
of China (Grant No. Q2007A05). Zhang’s research was also supported by the Visiting Scholar Program at Chern Institute of Mathematics. 相似文献
3.
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 相似文献
4.
Oscar F. Bandtlow 《Integral Equations and Operator Theory》2008,61(1):21-43
For a, α > 0 let E(a, α) be the set of all compact operators A on a separable Hilbert space such that s
n
(A) = O(exp(-anα)), where s
n
(A) denotes the n-th singular number of A. We provide upper bounds for the norm of the resolvent (zI − A)−1 of A in terms of a quantity describing the departure from normality of A and the distance of z to the spectrum of A. As a consequence we obtain upper bounds for the Hausdorff distance of the spectra of two operators in E(a, α).
相似文献
5.
Francis J. Narcowich Xinping Sun Joseph D. Ward 《Advances in Computational Mathematics》2007,27(1):107-124
Error estimates for scattered data interpolation by “shifts” of a conditionally positive definite function (CPD) for target
functions in its native space, which is its associated reproducing kernel Hilbert space (RKHS), have been known for a long
time. Regardless of the underlying manifold, for example ℝn or S
n, these error estimates are determined by the rate of decay of the Fourier transform (or Fourier series) of the CPD. This
paper deals with the restriction of radial basis functions (RBFs), which are radial CPD functions on ℝn+1, to the unit sphere S
n. In the paper, we first strengthen a result derived by two of us concerning an explicit representation of the Fourier–Legendre
coefficients of the restriction in terms of the Fourier transform of the RBF. In addition, for RBFs that are related to completely
monotonic functions, we derive a new integral representation for these coefficients in terms of the measure generating the
completely monotonic function. These representations are then utilized to show that if an RBF has a native space equivalent
to a Sobolev space H
s(ℝn+1), then the restriction to S
n has a native space equivalent to H
s−1/2(S
n). In addition, they are used to recover the asymptotic behavior of such coefficients for a wide variety of RBFs. Some of
these were known earlier.
Joseph D. Ward: Francis J. Narcowich: Research supported by grant DMS-0204449 from the National Science Foundation. 相似文献
6.
A real multivariate polynomial p(x
1, …, x
n
) is said to sign-represent a Boolean function f: {0,1}
n
→{−1,1} if the sign of p(x) equals f(x) for all inputs x∈{0,1}
n
. We give new upper and lower bounds on the degree of polynomials which sign-represent Boolean functions. Our upper bounds
for Boolean formulas yield the first known subexponential time learning algorithms for formulas of superconstant depth. Our lower bounds for constant-depth circuits and intersections of halfspaces are the first new degree lower bounds
since 1968, improving results of Minsky and Papert. The lower bounds are proved constructively; we give explicit dual solutions to the necessary linear programs. 相似文献
7.
In this paper, we prove the algebraic independence of the reciprocal sums of odd terms in Fibonacci numbers ∑
n=1∞
F
2n−1−1, ∑
n=1∞
F
2n−1−2, ∑
n=1∞
F
2n−1−3 and write each ∑
n=1∞
F
2n−1−s
(s≥4) as an explicit rational function of these three numbers over ℚ. Similar results are obtained for various series including
the reciprocal sums of odd terms in Lucas numbers.
相似文献
8.
Philippe Bonnet 《manuscripta mathematica》2003,110(4):413-432
Let F be a polynomial mapping from ℂ
n
to ℂ
q
with n>q. We study the De Rham cohomology of its fibres and its relative cohomology groups, by introducing a special fibre F
−1(∞) ``at infinity' and its cohomology. Let us fix a weighted homogeneous degree on with strictly positive weights. The fibre at infinity is the zero set of the leading terms of the coordinate functions of
F. We introduce the cohomology groups H
k
(F
−1(∞)) of F at infinity. These groups enable us to compute all the other cohomology groups of F. For instance, if the fibre at infinity has an isolated singularity at the origin, we prove that every weighted homogeneous
basis of H
n−q
(F
−1
(∞)) is a basis of all the groups H
n−q
(F
−1(y)) and also a basis of the (n−q)
th
relative cohomology group of F. Moreover the dimension of H
n−q
(F
−1(∞)) is given by a global Milnor number of F, which only depends on the leading terms of the coordinate functions of F.
Received: 12 February 2002 / Revised version: 25 May 2002 Published online: 3 March 2003 相似文献
9.
Dominique Arlettaz 《Central European Journal of Mathematics》2004,2(1):50-56
This paper provides universal upper bounds for the exponent of the kernel and of the cokernel of the classical Boardman homomorphism
b
n
: π
n
(X)→H
n
(H;ℤ), from the cohomotopy groups to the ordinary integral cohomology groups of a spectrum X, and of its various generalizations π
n
(X)→E
n
(X), F
n
(X)→(E∧F)
n
(X), F
n
(X)→H
n
(X;π
0
F) and F
n
(X)→H
n+t
(X;π
t
F) for other cohomology theories E
*(−) and F
*(−). These upper bounds do not depend on X and are given in terms of the exponents of the stable homotopy groups of spheres and, for the last three homomorphisms, in
terms of the order of the Postnikov invariants of the spectrum F. 相似文献
10.
Frances Y. Kuo Grzegorz W. Wasilkowski Henryk Woźniakowski 《BIT Numerical Mathematics》2009,49(3):543-564
We study approximation of multivariate functions from a general separable reproducing kernel Hilbert space in the randomized
setting with the error measured in the L
∞ norm. We consider algorithms that use standard information consisting of function values or general linear information consisting of arbitrary linear functionals. The power of standard or linear information is defined as, roughly speaking, the optimal rate of convergence of algorithms using n function values or linear functionals. We prove under certain assumptions that the power of standard information in the randomized
setting is at least equal to the power of linear information in the worst case setting, and that the powers of linear and
standard information in the randomized setting differ at most by 1/2. These assumptions are satisfied for spaces with weighted
Korobov and Wiener reproducing kernels. For the Wiener case, the parameters in these assumptions are prohibitively large,
and therefore we also present less restrictive assumptions and obtain other bounds on the power of standard information. Finally,
we study tractability, which means that we want to guarantee that the errors depend at most polynomially on the number of
variables and tend to zero polynomially in n
−1 when n function values are used. 相似文献
11.
Leszek Plaskota Grzegorz W. Wasilkowski 《Journal of Fixed Point Theory and Applications》2009,6(2):227-248
This is an overview of recent results on complexity and optimality of adaptive algorithms for integrating and approximating
scalar piecewise r-smooth functions with unknown singular points. We provide adaptive algorithms that use at most n function samples and have the worst case errors proportional to n−r for functions with at most one unknown singularity. This is a tremendous improvement over nonadaptive algorithms whose worst case errors are at best proportional to n−1 for integration and n−1/p for the Lp approximation problem. For functions with multiple singular points the adaptive algorithms cease to dominate the nonadaptive
ones in the worst case setting. Fortunately, they regain their superiority in the asymptotic setting. Indeed, they yield convergence of order n−r for piecewise r-smooth functions with an arbitrary (unknown but finite) number of singularities. None of these results hold for the L∞ approximation. However, they hold for the Skorohodmetric, which we argue to be more appropriate than L∞ for dealing with discontinuous functions. Numerical test results and possible extensions are also discussed. 相似文献
12.
Constance van Eeden 《Annals of the Institute of Statistical Mathematics》1985,37(1):461-472
Summary Asymptotic properties of the mean integrated squared error (MISE) of kernel estimators of a density function, based on a sampleX
1, …,X
n, were obtained by Rosenblatt [4] and Epanechnikov [1] for the case when the densityf and its derivativef′ are continuous. They found, under certain additional regularity conditions, that the optimal choiceh
n0 for the scale factorh
n=Kn−α is given byh
n0=K0n−1/5 withK
0 depending onf and the kernel; they also showed that MISE(h
n0)=O(n−4/5) and Epanechnikov [1] found the optimal kernel.
In this paper we investigate the robustness of these results to departures from the assumptions concerning the smoothness
of the density function. In particular it is shown, under certain regularity conditions, that whenf is continuous but its derivativef′ is not, the optimal value of α in the scale factor becomes 1/4 and MISE(h
n0)=O(n−3/4); for the case whenf is not continuous the optimal value of α becomes 1/2 and MISE(h
n0)=O(n−1/2). For this last case the optimal kernel is shown to be the double exponential density.
Supported by the Natural Sciences and Engineering Research Council of Canada under Grant Nr. A 3114 and by the Gouvernement
du Québec, Programme de formation de chercheurs et d'action concertée. 相似文献
13.
LetG be a finite primitive linear group over a fieldK, whereK is a finite field or a number field. We bound the composition length ofG in terms of the dimension of the underlying vector space and of the degree ofK over its prime subfield. As a byproduct, we prove a result of number theory which bounds the number of prime factors (counting
multiplicities) ofq
n−1, whereq, n>1 are integers, improving a result of Turull and Zame [6]. 相似文献
14.
We show that the total number of faces bounding any one cell in an arrangement ofn (d−1)-simplices in ℝ
d
isO(n
d−1 logn), thus almost settling a conjecture of Pach and Sharir. We present several applications of this result, mainly to translational
motion planning in polyhedral environments. We than extend our analysis to derive other results on complexity in arrangements
of simplices. For example, we show that in such an arrangement the total number of vertices incident to the same cell on more
than one “side” isO(n
d−1
logn). We, also show that the number of repetitions of a “k-flap,” formed by intersectingd−k given simplices, along the boundary of the same cell, summed over all cells and allk-flaps, isO(n
d−1
log2
n). We use this quantity, which we call theexcess of the arrangement, to derive bounds on the complexity ofm distinct cells of such an arrangement.
Work on this paper by the first author has been partially supported by National Science Foundation Grant CCR-92-11541. Work
on this paper by the second author has been supported by Office of Naval Research Grant N00014-90-J-1284, by National Science
Foundation Grants CCR-89-01484 and CCR-91-22103, and by grants from the U.S.-Israeli Binational Science Foundation, the G.I.F.—the
German-Israeli Foundation for Scientific Reseach and Development, and the Fund for Basic Research administered by the Israeli
Academy of Sciences. 相似文献
15.
Igor Kukavica 《Journal d'Analyse Mathématique》1995,67(1):269-280
We establish sharp upper bounds on the (n−1)-dimensional Hausdorff measure of the zero (nodal) sets and on the maximal order of vanishing corresponding to eigenfunctions
of a regular elliptic problem on a bounded domain Ω ⊆ ℝ
n
with real-analytic boundary. The elliptic operator may be of an arbitrary even order, and its coefficients are assumed to
be real-analytic. This extends a result of Donnelly and Fefferman ([DF1], [DF3]) concerning upper bounds for nodal volumes
of eigenfunctions corresponding to the Laplacian on compact Riemannian manifolds with boundary. 相似文献
16.
For a positive integer n we let τ(n) denote the number of its positive divisors. In this paper, we obtain lower and upper bounds for the average value of the
ratio τ(n + 1)/τ(n) as n ranges through positive integers in the interval [1,x]. We also study the cardinality of the sets {τ(p − 1) : p ≤ x prime} and {τ(2n − 1) : n ≤ x}.
Authors’ addresses: Florian Luca, Instituto de Matemáticas, Universidad Nacional Autónoma'de'México, C.P. 58089, Morelia,
Michoacán, México; Igor E. Shparlinski, Department of Computing, Macquarie University, Sydney, NSW 2109, Australia 相似文献
17.
Janusz Konieczny 《Semigroup Forum》1992,44(1):393-402
We prove that there are exactlyn numbers greater than 2
n−1 that can serve as the cardinalities of row spaces ofn×n Boolean matrices. The numbers are: 2
n−1+1,2
n−1+2,2
n−1+4, ..., 2
n−1+2
n−2, 2
n
. Two consequences follow. The first is that the height of the partial order ofD-classes in the semigroup ofn×n Boolean matrices is at most 2
n−1+n−1. The second is that the numbers listed above are precisely the numbers greater than 2
n−1 that can serve as the cardinalities of topologies on a finite setX withn elements. 相似文献
18.
Eliyahu Beller 《Israel Journal of Mathematics》1977,27(3-4):320-330
A generalization of the Blaschke product is constructed. This product enables one to factor out the zeros of the members of
certain non-Nevanlinna classes of functions analytic in the unit disc, so that the remaining (non-vanishing) functions still
belong to the same class. This is done for the classesA
−n (0<n<∞) andB
−n (0<n<2) defined as follows:f ∈A
−n iff |f(z)|≦C
f
(1−|z|)−n
,f ∈B
−n
iff |f(z)|≦exp {C
f
(1−|z|)−n
}, whereC
f
depends onf. 相似文献
19.
Y. Yomdin 《Israel Journal of Mathematics》2011,186(1):45-60
The classical Remez inequality bounds the maximum of the absolute value of a polynomial P(x) of degree d on [−1, 1] through the maximum of its absolute value on any subset Z of positive measure in [−1, 1]. Similarly, in several variables the maximum of the absolute value of a polynomial P(x) of degree d on the unit cube Q
1
n
⊂ ℝ
n
can be bounded through the maximum of its absolute value on any subset Z ⊂ Q
1
n
of positive n-measure. The main result of this paper is that the n-measure in the Remez inequality can be replaced by a certain geometric invariant ω
d
(Z) which can be effectively estimated in terms of the metric entropy of Z and which may be nonzero for discrete and even finite sets Z. 相似文献
20.
Letm(t)dt be a positive measure onR
+. We investigate the relations among the growth ofm, the growth of its moment sequence {yn}, the growth of its Bergman kernel functionk
x=Σγ{n/-1}x
n, and the growth of the kernel function associated to the measureK(t)
−1m(t) dt. For a large class of measures, we find that these quantities satisfy asymptotic relations similar to the simple exact
relations which hold in the model casem(t)=e
−1.
Supported in part by a grant from the National Science Foundation. 相似文献