Large triangle-free subgraphs in graphs withoutK 4

It is shown that for arbitrary positive there exists a graph withoutK ₄ and so that all its subgraphs containing more than 1/2 + portion of its edges contain a triangle (Theorem 2). This solves a problem of Erdös and Neetil. On the other hand it is proved that such graphs have necessarily low edge density (Theorem 4).Theorem 3 which is needed for the proof of Theorem 2 is an analog of Goodman's theorem [8], it shows that random graphs behave in some respect as sparse complete graphs.Theorem 5 shows the existence of a graph on less than 10¹² vertices, withoutK ₄ and which is edge-Ramsey for triangles.     

Constraint decomposition algorithms in global optimization

Many global optimization problems can be formulated in the form min{c(x, y): x X, y Y, (x, y) Z, y G} where X, Y are polytopes in ^p , ⁿ , respectively, Z is a closed convex set in ^p+n, while G is the complement of an open convex set in ⁿ . The function c: ^p+n is assumed to be linear. Using the fact that the nonconvex constraints depend only upon they-variables, we modify and combine basic global optimization techniques such that some new decomposition methods result which involve global optimization procedures only in ⁿ . Computational experiments show that the resulting algorithms work well for problems with smalln.     

Periodic solutions of singularly perturbed delay equations

We consider a general class of singularly perturbed delay differential systems depending on a singular parameter and another parameter . For =0, the equation defines a mapT which undergoes a generic period doubling at =0. If the bifurcation is supercritical (subcritical), these period two points define a stable period two square wave (unstable period two pulse wave). We give conditions on the vector field such that there is a sectorS in the , plane such that there is a unique periodic orbit if the parameters are inS, the orbit is stable (unstable) if the period doubling bifurcation is supercritical (subcritical) and approaches the square (pulse) wave as 0.Partially supported by NSF and DARPA.     

Spectral parameter asymptotics of the Weyl solutions of Sturm-Liouville equations

In the paper one investigates the dependence of Weyl's solution ,)=c(,)+n()s(,) of the Sturm-Liouville equation y+q()y=²y on the spectral parameter . Under the condition that the potential q is bounded from below and q()exp(c₀+c[in1 ¦¦), it is proved for {ie217-01} for any positive values and A. If q()>1 and {ie217-02} for all >0, then in the semiplane >0 the Weyl solution (, ) is obtained from the Weyl solution (,x) is obtained from the Weyl solution e^ix with zero potential, with the aid of a generalization of B. Ya Levin's transformation operators.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova Akademii Nauk SSSR, Vol. 170, pp. 184–206, 1989.I express my sincere gratitude to L. A. Pastur and I. V. Ostrovskii for valuable advice and discussions.     

The correctness problem for best approximations by trigonometric polynomials in the class W o r H[ω]C

Suppose thatk, rz₊, W _o ^r H[]_C= {ff is a 2-periodic function,f C^r [–, ], (f^(r), ) ()}, T_k is the space of trigonometric polynomials of order k, p_k(f)T_k is the polynomial of best uniform approximation to f, and E_k(f) is the error of the best approximation. It is shown that for an arbitrary > 0 we have,where for 0<&#x2A7D;(1),k > 0.R () is the root of the equation , and for k = 0 or > (1) we have R()=.Translated from Matematicheskie Zametki, Vol. 22, No. 1, pp. 85–101, July, 1977.The author thanks S. B. Stechkin for posing the problem and for his attention to this work.     

Linear foliations ofT n

We present a definition of diophantine matrix and use this concept to distinguish two classes of minimal linear foliations ofT ⁿ, the diophantine and the Liouville one. Let _p , 1pn–1, denote a minimal (all leaves are dense) linearp-dimensional foliation ofT ⁿ, andH ^om(T ⁿ, _p ), 1mp, the cohomology group of type (0,m) of the foliated manifold (T ⁿ, _p ). Our main result is the computation of these groups.H ^om(T ⁿ, _p ) is isomorphic to if _p is diophantine and is an infinite dimensional non-Hausdorff vector space if _p is Liouville. Some of these groups were computed before, see [4], [6] and [9].     

Boundary layers in parabolic perturbations of scalar conservation laws

We consider the problem of estimating the boundary layer thickness for vanishing viscosity solutions of boundary value problems for parabolic perturbations of a scalar conservation law in a space strip in R^d . For the boundary layer thickness () we obtain that one can take ()= ^r, for any r<1/2, arbitrarily close to 1/2.     

On Logarithmic Smoothing of the Maximum Function

We consider the maximum function f resulting from a finite number of smooth functions. The logarithmic barrier function of the epigraph of f gives rise to a smooth approximation g of f itself, where >0 denotes the approximation parameter. The one-parametric family g converges – relative to a compact subset – uniformly to the function f as tends to zero. Under nondegeneracy assumptions we show that the stationary points of g and f correspond to each other, and that their respective Morse indices coincide. The latter correspondence is obtained by establishing smooth curves x() of stationary points for g , where each x() converges to the corresponding stationary point of f as tends to zero. In case of a strongly unique local minimizer, we show that the nondegeneracy assumption may be relaxed in order to obtain a smooth curve x().     

A smoothed bootstrap estimator for a studentized sample quantile

If the underlying distribution functionF is smooth it is known that the convergence rate of the standard bootstrap quantile estimator can be improved fromn ^–1/4 ton ^–1/2+, for arbitrary >0, by using a smoothed bootstrap. We show that a further significant improvement of this rate is achieved by studentizing by means of a kernel density estimate. As a consequence, it turns out that the smoothed bootstrap percentile-t method produces confidence intervals with critical points being second-order correct and having smaller length than competitors based on hybrid or on backwards critical points. Moreover, the percentile-t method for constructing one-sided or two-sided confidence intervals leads to coverage accuracies of ordern ^–1+, for arbitrary >0, in the case of analytic distribution functions.     

On the factor-thickness of regular graphs

For eachr-regular graphG, define a binary sequence(G) = ( ₁, ₂,..., _r-1) by _k = 0 ifG has ak-factor, and _k = 1 otherwise. A binary sequence = ( _i |i = 1, 2,...,r – 1) is said to be realizable if there exists anr-regular graphG such that(G) = . In this paper we characterize all binary sequences which are realizable.     

Singular perturbations in foliations

Summary We define a constraint system , [0,₀), which is a kind of family of vector fields on a manifold. This is a generalized version of the family of the equations , [0,₀),x ^m ,y ⁿ . Finally, we prove a singular perturbation theorem for the system , [0,₀).Dedicated to Professor Kenichi Shiraiwa on his 60th birthday     

On the existence of multiple solutions of nonhomogeneous elliptic equations involving critical Sobolev exponents

Letp=2N/(N –2),N 3 be the limiting Sobolev exponent and ^N a bounded smooth domain. We show that for H ^–1(),f satisfies some conditions then–u=c ₁ u ^p–1 +f(x,u) + admits at least two positive solutions.     

On Localization and Stabilization for Factorization Systems

If (, M)is a factorization system on a category C, we define new classes of maps as follows: a map f:AB is in if each of its pullbacks lies in (that is, if it is stably in ), and is in M ^* if some pullback of it along an effective descent map lies in M(that is, if it is locally in M). We find necessary and sufficient conditions for (, M ^*) to be another factorization system, and show that a number of interesting factorization systems arise in this way. We further make the connexion with Galois theory, where M ^*is the class of coverings; and include self-contained modern accounts of factorization systems, descent theory, and Galois theory.     

Two congruence lattices of completely simple semigroups

For a Rees matrix semigroupS with normalized sandwich matrix and C(S), the congruence lattice ofS, we consider the lattice generated by {itpT_l, pK, pT_r, pt_l, pk, pt_r}. HerepT ₁ andpt _l are the upper and lower ends of the interval which makes up the _i -class of , _i being the left trace relation onC(S). The remaining symbols have the analogous meaning relative to the kernel and the right trace relations. We also consider the lattice generated by {T _l, K, T_r, t_l, _k, t_r} where and are the equality and the universal relations onS, respectively. In both cases, we find lattices freest relative to these lattices and represent them as distributive lattices with generators and relations.With 3 Figures     

On the distribution of square-full and cube-full integers

LetN _r (x) be the number ofr-full integers x and let _r (x) be the error term in the asymptotic formula forN _r (x). Under Riemann's hypothesis, we prove the estimates ₂(x)x^1/7+, ₃(x)x^97/804+(>0), which improve those of Cao and Nowak. We also investigate the distribution ofr-full andl-free numbers in short intervals (r=2,3). Our results sharpen Krätzel's estimates.     

On Some Isomorphism on the Category of b-Spaces

Given a nuclear b-space N, we show that if is a finite or -finite measure space and 1p, then the functors L _loc ^p (,N.) and NL ^p (,.) are isomorphic on the category of b-spaces of L. Waelbroeck.     

How to approximate the solutions of certain free boundary problems for the Laplace equation by using the contraction principle

We show how the free boundary of an ideal fluid, subject to a generalized Bernoulli condition, can (under appropriate circumstances) be approximated. Our method is based on a class of free-boundary perturbation operatorsT , 0<<1, which are all contracting relative to a suitable norm and class of boundaries, and whose fixed points converge to the desired free boundary solution as 0+.

---

Zusammenfassung Wir zeigen, wie der freie Rand einer idealen Flüssigkeit, welcher einer verallgemeinerten Bernoulli-Bedingung genügt, unter geeigneten Umständen approximiert werden kann. Unsere Methode stützt sich auf eine Klasse freier RandperturbationsoperatorenT , 0<<1, welche relativ zu einer geeigneten Norm und Ränderklasse kontrahierend sind und deren Fixpunkte gegen die gewünschte Lösung der freien Randaufgabe mit 0+ konvergieren.

     

Positivity Preserving Forms have the Fatou Property

We prove that if (,D) is a positivity preserving form on L ² (E;m), and if (u _n)_n is a sequence in D() converging m-almost everywhere to u L ² (E;m), then (u,u) lim inf_n (u _n ,u _n ).     

Circle contractive linear multistep methods

Linear multistep methods satisfying a non-linear circle contractivity condition when the step-ratios are less than some 1+,>0, are shown to exist for any order. Methods with formulas of order 1 to 12 are given.     

Random polytopes in thed-dimensional cube

LetC ^d be the set of vertices of ad-dimensional cube,C ^d ={(x ₁, ...,x _d ):x _i =±1}. Let us choose a randomn-element subsetA(n) ofC ^d . Here we prove that Prob (the origin belongs to the convA(2d+x2d))=(x)+o(1) ifx is fixed andd . That is, for an arbitrary>0 the convex hull of more than (2+)d vertices almost always contains 0 while the convex hull of less than (2-)d points almost always avoids it.