k-regular factors and semi-k-regular factors in bipartite graphs

LetG be a graph, andk1 an integer. LetU be a subset ofV(G), and letF be a spanning subgraph ofG such that deg _F (x)=k for allx V(G)–U. If deg _F (x)k for allxU, thenF is called an upper semi-k-regular factor with defect setU, and if deg _F (x)k for allxU, thenF is called a lower semi-k-regular factor with defect setU. Now letG=(X, Y;E(G)) be a bipartite graph with bipartition (X,Y) such that X=Yk+2. We prove the following two results.(1) Suppose that for each subsetU ₁X such that U ₁=max{k+1, X+1/2},G has an upper semi-k-regular factor with defect setU ₁Y, and for each subsetU ₂Y such that U ₂=max{k+1, X+1/2},G has an upper semi-k-regular factor with defect setXU ₂. ThenG has ak-factor.(2) Suppose that for each subsetU ₁X such that U ₁=X–1/k+1,G has a lower semi-k-regular factor with defect setU ₁Y, and for each subsetU ₂Y such that U ₂=X–1/k+1,G has a lower semi-k-regular factor with defect setXU ₂. ThenG has ak-factor.     

Convex independent sets and 7-holes in restricted planar point sets

For a finite setA of points in the plane, letq(A) denote the ratio of the maximum distance of any pair of points ofA to the minimum distance of any pair of points ofA. Fork>0 letc (k) denote the largest integerc such that any setA ofk points in general position in the plane, satisfying for fixed , contains at leastc convex independent points. We determine the exact asymptotic behavior ofc (k), proving that there are two positive constants=(), such thatk ^1/3c (k)k ^1/3. To establish the upper bound ofc (k) we construct a set, which also solves (affirmatively) the problem of Alonet al. [1] about the existence of a setA ofk points in general position without a 7-hole (i.e., vertices of a convex 7-gon containing no other points fromA), satisfying . The construction uses Horton sets, which generalize sets without 7-holes constructed by Horton and which have some interesting properties.     

Posterior Sensitivity to the Sampling Distribution and the Prior: More than One Observation

Sensitivity of a posterior quantity (f, P) to the choice of the sampling distribution f and prior P is considered. Sensitivity is measured by the range of (f, P) when f and P vary in nonparametric classes ^f and ^P respectively. Direct and iterative methods are described which obtain the range of (f, P) over f ^f when prior P is fixed, and also the overall range over f ^f and P ^P . When multiple i.i.d. observations X ₁,...,X _k are observed from f, the posterior quantity (f, P) is not a ratio-linear function of f. A method of steepest descent is proposed to obtain the range of (f, P). Several examples illustrate applications of these methods.     

On Riesz means with respect to a cylindric distance function

(1–) ₊ , — R ⁿ =R ^j ×R ^k , ()=max{¦ ₁¦, ¦ ₁¦},=( ₁, ₂), ₁R ^J , ₂R ^k ,j,k1,n=j+k. n=3 , (1–) ₊ [L ¹(R ⁿ )]¹, >1/2; j=4, (1–) ₊ R L ^p (R ⁿ ). .

---

---

The author would like to thank Professor W. Trebels for encouragement and valuable advice.     

Smoothness of solutions of a nonlinear ode

Smoothness of aC -functionf is measured by (Carleman) sequence {M _k} ₀ ; we sayfC _M [0, 1] if|f ^(k) (t)|CR ^k M _k,k=0, 1, ... withC, R>0. A typical statement proven in this paper isTHEOREM: Let u, b be two C -functions on [0, 1]such that (a) u=u ²+b, (b) |b ^(k) (t)|CR ^k (k!) , >1,k_–.Then |u^(k)(t)|C₁R^k((k–1)!),k_–.The first author acknowledges the hospitality of Mathematical Research Institute of the Ohio State University during his one month visit there in the spring of 1999     

Round-off error analysis of iterations for large linear systems

Summary We deal with the rounding error analysis of successive approximation iterations for the solution of large linear systemsA _x =b. We prove that Jacobi, Richardson, Gauss-Seidel and SOR iterations arenumerically stable wheneverA=A ^*>0 andA has PropertyA. This means that the computed resultx _k approximates the exact solution with relative error of order A·A ^–1 where is the relative computer precision. However with the exception of Gauss-Seidel iteration the residual vector Ax _k –b is of order A² A ^–1 and hence the remaining three iterations arenot well-behaved.This work was partly done during the author's visit at Carnegie-Mellon University and it was supported in part by the Office of Naval Research under Contract N00014-76-C-0370; NR 044-422 and by the National Science Foundation under Grant MCS75-222-55     

Quasianapole Interaction of Charged Fermions

We obtain the analytic expression for the total cross section of the reaction e ^– e ⁺l ^– l ⁺ (l=,) taking possible quasianapole interaction effects into account. We find numerical restrictions on the interaction parameter value from data for the reaction e ^– e ^+–+ in the energy domain below the Z ⁰ peak.     

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.     

A chord-stretching map of a convex loop is an isometry

Let ⁿ be n-dimensional Euclidean space, and let : [0, L] ⁿ and : [0, L] ⁿ be closed rectifiable arcs in ⁿ of the same total length L which are parametrized via their arc length. is said to be a chord-stretched version of if for each 0s tL, |(t)–(s)| |(t)–(s)|. is said to be convex if is simple and if ([0, L]) is the frontier of some plane convex set. Individual work by Professors G. Choquet and G. T. Sallee demonstrated that if were simple then there existed a convex chord-stretched version of . This result led Professor Yang Lu to conjecture that if were convex and were a chord-stretched version of then and would be congruent, i.e. any chord-stretching map of a convex arc is an isometry. Professor Yang Lu has proved this conjecture in the case where and are C ² curves. In this paper we prove the conjecture in general.     

Stream vectors in three dimensional aerodynamics

Summary This work deals with the decomposition of a vector fieldu intou=×+. Non homogeneous boundary conditions on or are investigated; applications to the computation of inviscid flows are given; finally a conforming finite element implementation is studied and tested.     

Non removable edges in 3-connected cubic graphs

LetG be a cyclicallyk-edge-connected cubic graph withk 3. Lete be an edge ofG. LetG be the cubic graph obtained fromG by deletinge and its end vertices. The edgee is said to bek-removable ifG is also cyclicallyk-edge-connected. Let us denote by S _k (G) the graph induced by thek-removable edges and by N _k (G) the graph induced by the non 3-removable edges ofG. In a previous paper [7], we have proved that N ₃(G) is empty if and only ifG is cyclically 4-edge connected and that if N ₃(G) is not empty then it is a forest containing at least three trees. Andersen, Fleischner and Jackson [1] and, independently, McCuaig [11] studied N ₄(G). Here, we study the structure of N _k (G) fork 5 and we give some constructions of graphs such thatN _k (G) = E(G). We note that the main result of this paper (Theorem 5) has been announced independently by McCuaig [11].

---

Résumé SoitG un graphe cubique cyliquementk-arête-connexe, aveck 3. Soite une arête deG et soitG le graphe cubique obtenu à partir deG en supprimante et ses extrémités. L'arêtee est ditek-suppressible siG est aussi cycliquementk-arête-connexe. Désignons par S _k (G) le graphe induit par les arêtesk-suppressibles et par N _k (G) celui induit par les arêtes nonk-suppressibles. Dans un précédent article [7], nous avons montré que N ₃(G) est vide si et seulement siG est cycliquement 4-arête-connexe et que si N ₃(G) n'est pas vide alors c'est une forêt possédant au moins trois arbres. Andersen, Fleischner and Jackson [1] et, indépendemment, McCuaig [11] ont étudié N ₄(G). Ici, nous étudions la structure de N _k (G) pourk 5 et nous donnons des constructions de graphes pour lesquelsN _k (G) = E(G). Nous signalons que le résultat principal de cet article (Théorème 5) a été annoncé indépendamment par McCuaig [11].

     

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.     

Zur Interpolation und Integration differenzierbarer periodischer Funktionen

Summary Letx ₀<x ₁<...<x _n–1<x ₀+2 be nodes having multiplicitiesv ₀,...,v _n–1, 1v _k r (0k<n). We approximate the evaluation functional ,x fixed, and the integral respectively by linear functionals of the form and determine optimal weights for the Favard classesW _r C ₂. In the even case of optimal interpolation these weights are unique except forr=1,x(x _k +x _k–1)/2 mod 2. Moreover we get periodic polynomial splinesw _{k, j} (0k<n, 0j<v _k ) of orderr such that are the optimal weights. Certain optimal quadrature formulas are shown to be of interpolatory type with respect to these splines. For the odd case of optimal interpolation we merely have obtained a partial solution.

Bojanov hat in [4, 5] ähnliche Resultate wie wir erzielt. Um Wiederholungen zu vermeiden, werden Resultate, deren Beweise man bereits in [4, 5] findet, nur zitiert     

Efficient Solution of the Complex Quadratic Tridiagonal System for C2 PH Quintic Splines

The construction of C ² Pythagorean-hodograph (PH) quintic spline curves that interpolate a sequence of points p ₀,...,p _N and satisfy prescribed end conditions incurs a tridiagonal system of N quadratic equations in N complex unknowns. Albrecht and Farouki [1] invoke the homotopy method to compute all 2 ^N+k solutions to this system, among which there is a unique good PH spline that is free of undesired loops and extreme curvature variations (k{–1,0,+1} depends on the adopted end conditions). However, the homotopy method becomes prohibitively expensive when N10, and efficient methods to construct the good spline only are desirable. The use of iterative solution methods is described herein, with starting approximations derived from ordinary C ² cubic splines. The system Jacobian satisfies a global Lipschitz condition in C ^N , yielding a simple closed-form expression of the Kantorovich condition for convergence of Newton–Raphson iterations, that can be evaluated with O(N ²) cost. These methods are also generalized to the case of non-uniform knots.     

Positive Solutions for a Singular Nonlinear Problem on a Bounded Domain in R 2

For a bounded regular Jordan domain in R ², we introduce and study a new class of functions K() related on its Green function G. We exploit the properties of this class to prove the existence and the uniqueness of a positive solution for the singular nonlinear elliptic equation u+(x,u)=0, in D(), with u=0 on and uC(), where is a nonnegative Borel measurable function in ×(0,) that belongs to a convex cone which contains, in particular, all functions (x,t)=q(x)t ^–,>0 with nonnegative functions qK(). Some estimates on the solution are also given.     

An infinite dimensional analogue of the Albeverio-Röckner's theorem on Fukushima's conjecture

LetX be the solution of the SDE:dX _t = (X _t)dB _t +b(X _t)dt, with andb C _b (R) such that >0 for some constant , andB a real Brownian motion. Let be the law ofX onE=C([0, 1],R) andk E* – {0}, whereE* is the topological dual space ofE. Consider the classical form: _k (u, v)=u / kv / kd, whereu andv are smooth functions onE. We prove that, if _k is closable for anyk in a dense subset ofE* and if the smooth functions are contained in the domain of the generator of the closure of _k , must be a constant function.     

Formulating Measure Differential Inclusions in Infinite Dimensions

Measure differential inclusions were introduced by J. J. Moreau to study sweeping processes, and have since been used to study rigid body dynamics and impulsive control problems. The basic formulation of an MDI is d / d (t) K(t) where is a vector measure, an unsigned measure, and K() is a set-valued map with closed, convex values and is hemicontinuous. Note that need not be absolutely continuous with respect to . Stewart extended Moreau's original concept (which applied only to cone-valued K()) to general convex sets, and gave strong and weak formulations of d / d (t) K(t) where K(t) R ⁿ . Here the strong and weak formulations of Stewart are extended to infinite-dimensional problems where K(t) X where X is a separable reflexive Banach space; they are shown to be equivalent under mild assumptions on K().     

Subsets with Restricted Movement

Let G be a finite permutation group on a set with no fixed points in and let m and k be integers with 0 < m < k. For a finite subset of the movement of is defined as move() = max_gG| ^g \ |. Suppose further that G is not a 2-group and that p is the least odd prime dividing |G| and move() m for all k-element subsets of . Then either || k + m or k (7m – 5) / 2, || (9m – 3)/2. Moreover when || > k + m, then move() m for every subset of .     

Cross-monotone subsequences

Two finite real sequences (a ₁,...,a _k ) and (b ₁,...,b _k ) are cross-monotone if each is nondecreasing anda _i+1–a _i b _i+1–b _i for alli. A sequence (₁,..., _n ) of nondecreasing reals is in class CM(k) if it has disjointk-term subsequences that are cross-monotone. The paper shows thatf(k), the smallestn such that every nondecreasing (₁,..., _n ) is in CM(k), is bounded between aboutk ²/4 andk ₂/2. It also shows thatg(k), the smallestn for which all (₁,..., _n ) are in CM(k)and eithera _k b ₁ orb _k a ₁, equalsk(k–1)+2, and thath(k), the smallestn for which all (₁,..., _n ) are in CM(_k)and eithera ₁b ₁...a _k b _k orb ₁a ₁...b _k a _k , equals 2(k–1)²+2.The results forf andg rely on new theorems for regular patterns in (0, 1)-matrices that are of interest in their own right. An example is: Every upper-triangulark ²×k ² (0, 1)-matrix has eitherk 1's in consecutive columns, each below its predecessor, ork 0's in consecutive rows, each to the right of its predecessor, and the same conclusion is false whenk ² is replaced byk ²–1.     

Sur certaines algèbres associées à une mesure de Guelfand

Let be a Guelfand measure (cf. [A, B]) on a locally compact groupG DenoteL ₁ (G)=*L ₁(G)* the commutative Banach algebra associated to . We show thatL ₁ (G) is semi-simple and give a characterization of the closed ideals ofL ₁ (G). Using the -spherical Fourier transform, we characterize all linear bounded operators inL ₁ (G) which are invariants by -translations (i.e. such that ¹(( _x f) )=( _x ((f)) for eachxG andfL ₁ (G); where _x f(y)=f(xy); x,y G). WhenG is compact, we study the algebraL ₁ (G) and obtain results analogous to ones obtained for the commutative case: we show thatL ₁ (G) is regular, all closed sets of its Guelfand spectrum are sets of synthesis and establish theorems of harmonic synthesis for functions inL _p (G) (p=1,2 or +).