On approximation of solutions of multidimensional SDE's with reflecting boundary conditions

Let D be either a convex domain in ^d or a domain satisfying the conditions (A) and (B) considered by Lions and Sznitman [7] and Saisho [11]. We estimate the rate of L^p convergence for Euler and Euler–Peano schemes for stochastic differential equations in D with normal reflection at the boundary of the form

Full-size image

, where W is a d-dimensional Wiener process. As a consequence we give the rate of almost sure convergence for these schemes.     

First inverse moment of a generalized quadratic form

In this paper an approximate expression for the first inverse moment of

Full-size image

where _k is a Gaussian stationary vector process is derived. This generalized quadratic form is the estimate of the information matrix when using the Recursive Least Squares (RLS) algorithm with forgetting factor. This estimator is commonly used when estimating parameters in time-varying linear stochastic systems.     

Another view on martingale central limit theorems

Based on the martingale version of the Skorokhod embedding Heyde and Brown (1970) established a bound on the rate of convergence in the central limit theorem (CLT) for discrete time martingales having finite moments of order 2+2δ with 0<δ1. An extension for all δ>0 was proved in Haeusler (1988). This paper presents a rather quick access based solely on truncation, optional stopping, and prolongation techniques for martingale difference arrays to obtain other upper bounds for sup

Full-size image

(φbeing the standard normal d.f.) yielding weak sufficient conditions for the asymptotic normality of . It is shown that our approach also yields two types of martingale central limit theorems with random norming.     

Universal H-colorable graphs without a given configuration

For every pair of finite connected graphs F and H, and every positive integer k, we construct a universal graph U with the following properties:

Full-size image

Particularly, this solves a problem presented in [1] and [2] regarding the chromatic number of a universal graph.     

Directed triangles in directed graphs

We show that each directed graph on n vertices, each with indegree and outdegree at least n/t, where

Full-size image

, contains a directed circuit of length at most 3.     

Comparison of two norms of matrices

Any complex n × n matrix A satisfies the inequality

A ₁ ≤ n 1/2 A _d

where .₁ is the trace norm and ._d is the norm defined by

Full-size image

,

where B is the set of orthonormal bases in the space of n × 1 matrices. The present work is devoted to the study of matrices A satisfying the identity:

A₁ = n1/2 A _d

This paper is a first step towards a characterization of matrices satisfying this identity. Actually, a workable characterization of matrices subject to this condition is obtained only for n = 2. For n = 3, a partial result on nilpotent matrices is presented. Like our previous study (J. Dazord, Linear Algebra Appl. 254 (1997) 67), this study is a continuation of the work of M. Marcus and M. Sandy (M. Marcus and M. Sandy, Linear and Multilinear Algebra 29 (1991) 283). Also this study is related to the work of R. Gabriel on classification of matrices with respect to unitary similarity (see R. Gabriel, J. Riene Angew, Math. 307/308 (1979) 31; R. Gabriel, Math. Z. 200 (1989) 591).     

Bestness of the parabola theorem for continued fractions

We show that the simple conditional convergence set

Full-size image

fixed is maximal in the sense that if b is an arbitrary point in , then P{b} is not conditional convergence set.     

Large 2P3-free graphs with bounded degree

Let ex^* (D;H) be the maximum number of edges in a connected graph with maximum degree D and no induced subgraph H; this is finite if and only if H is a disjoint union of paths. If the largest component of such an H has order m, then ex^*(D; H) = O(D²ex^*(D; P_m)). Constructively, ex^*(D;qP_m) = Θ(gD²ex^*(D;P_m)) if q>1 and m> 2(Θ(gD²) if m = 2). For H = 2P₃ (and D 8), the maximum number of edges is if D is even and

Full-size image

if D is odd, achieved by a unique extremal graph.     

Tree groups and the 4-string pure braid group

Given a graph Г, undirected, with no loops or multiple edges, we define the graph group on Г, F_Г, as the group generated by the vertices of Г, with one relation xy = xy for each pair x and y of adjacent vertices of Г.

In this paper we will show that the unpermuted braid group on four strings is an HNN-extension of the graph group F_s, where

S =

Full-size image

The form of the extension will resolve a conjecture of Tits for the 4-string braid group. We will conclude, by analyzing the subgroup structure of graph groups in the case of trees, that for any tree T on a countable vertex set, F_t is a subgroup of the 4-string braid group.

We will also show that this uncountable collection of subgroups of the 4-string braid group is linear, that is, each subgroup embeds in GL(3, ), as well as embedding in Aut(F), where F is the free group of rank 2.     

Longest cycles in 3-connected graphs

In this paper, we get the following result: Let G be a 3-connected graph with n vertices. Then , where

Full-size image

. This is a new lower bound for the circumference c(G) of a 3-connected graph G.     

A single-element extension of antimatroids

An antimatroid is a family of sets which is accessible, closed under union, and includes an empty set. A number of examples of antimatroids arise from various kinds of shellings and searches on combinatorial objects, such as, edge/node shelling of trees, poset shelling, node-search on graphs, etc. (Discrete Math. 78 (1989) 223; Geom. Dedicata 19 (1985) 247; Greedoids, Springer, Berlin, 1980) [1, 2 and 3]. We introduce a one-element extension of antimatroids, called a lifting, and the converse operation, called a reduction. It is shown that a family of sets is an antimatroid if and only if it is constructed by applying lifting repeatedly to a trivial lattice. Furthermore, we introduce two specific types of liftings, 1-lifting and 2-lifting, and show that a family of sets is an antimatroid of poset shelling if and only if it is constructed from a trivial lattice by repeating 1-lifting. Similarly, an antimatroid of edge-shelling of a tree is shown to be constructed by repeating 2-lifting, and vice versa.     

Strong continuity of the relative rearrangement maps and application to a Galerkin approach for nonlocal problems

We study the strong continuity of the map u   (b_*u, b_*u(| > u(·)|)). Here,

Full-size image

for σ]0 means Ω[, u_* (respectively, (b|_{u=u*(σ)})*) denotes the decreasing rearrangement of u (respectively b restricted to the set {u = u_*(σ)}) and |E| denotes the Lebesgue measure of a set E included in a domain Ω. The results are useful for solving plasmas physics equations or any nonlocal problems involving the monotone rearrangement, its inverse or its derivatives.     

Atoms of set systems with a fixed number of pairwise unions

For a finite set system with ground set X, we let

Full-size image

. An atom of H is a nonempty maximal subset C of X such that for all A H, either C A or C ∩ A = 0. We obtain a best possible upper bound for the number of atoms determined by a set system H with H = k and H H = u for all integers k and u. This answers a problem posed by Sós.     

A note on unsolvable systems of max–min (fuzzy) equations

For unsolvable systems of linear equations of the form Ax=b over the max–min (fuzzy) algebra

Full-size image

we propose an efficient method for finding a Chebychev-best approximation of the matrix in the set

Full-size image

.     

A parameter-uniform implicit difference scheme for solving time-dependent Burgers’ equations

A numerical study is made for solving one dimensional time dependent Burgers’ equation with small coefficient of viscosity. Burgers’ equation is one of the fundamental model equations in the fluid dynamics to describe the shock waves and traffic flows. For high coefficient of viscosity a number of solution methodology exist in the literature [6], [7], [8] and [9] and [14] but for the sufficiently low coefficient of viscosity, the exist solution methodology fail and a discrepancy occurs in the literature. In this paper, we present a numerical method based on finite difference which works nicely for both the cases, i.e., low as well as high viscosity coefficient. The method comprises a standard implicit finite difference scheme to discretize in temporal direction on uniform mesh and a standard upwind finite difference scheme to discretize in spacial direction on piecewise uniform mesh. The quasilinearzation process is used to tackle the non-linearity. An extensive amount of analysis has been carried out to obtain the parameter uniform error estimates which show that the resulting method is uniformly convergent with respect to the parameter. To illustrate the method, numerical examples are solved using the presented method and compare with exact solution for high value of coefficient of viscosity.     

Extremal regular graphs for the achromatic number

The problem of constructing (m, n) cages suggests the following class of problems. For a graph parameter θ, determine the minimum or maximum value of p for which there exists a k-regular graph on p points having a given value of θ. The minimization problem is solved here when θ is the achromatic number, denoted by ψ. This result follows from the following main theorem. Let M(p, k) be the maximum value of ψ(G) over all k-regular graphs G with p points, let {x} be the least integer of size at least x, and let be given by ω(k) = {i(ik+1)+1:1i<∞}. Define the function ƒ(p, k) by

Full-size image

. Then for fixed k2 we have M(p, K=ƒ(p, k) if pω(k) and M(p, k)=ƒ(p,k-1 if pε ω(k) for all p sufficiently large with respect to k.     

Chromatic-index-critical graphs of orders 13 and 14

A graph is chromatic-index-critical if it cannot be edge-coloured with Δ colours (with Δ the maximal degree of the graph), and if the removal of any edge decreases its chromatic index. The Critical Graph Conjecture stated that any such graph has odd order. It has been proved false and the smallest known counterexample has order [[18] A.J.W. Hilton, R.J. Wilson, Edge-colorings of graphs: a progress report, in: M.F. Cabobianco, et al. (Eds.), Graph Theory and its Applications: East and West, New York, 1989, pp. 241–249; [31] H.P. Yap, Some topics in graph theory, London Mathematical Society, Lecture Note Series, vol. 108, Cambridge University Press, Cambridge, 1986].

In this paper we show that there are no chromatic-index-critical graphs of order 14. Our result extends that of [[5] G. Brinkmann, E. Steffen, Chromatic-index-critical graphs of orders 11 and 12, European J. Combin. 19 (1998) 889–900] and leaves order 16 as the only case to be checked in order to decide on the minimality of the counterexamples given by Chetwynd and Fiol. In addition we list all nontrivial critical graphs of order 13.     

Bounds on the number of isolates in sum graph labeling

A simple undirected graph H is called a sum graph if there is a labeling L of the vertices of H into distinct positive integers such that any two vertices u and v of H are adjacent if and only if there is a vertex w with label L(w)=L(u)+L(v). The sum number σ(G) of a graph G=(V,E) is the least integer r such that the graph H consisting of G and r isolated vertices is a sum graph. It is clear that σ(G)|E|. In this paper, we discuss general upper and lower bounds on the sum number. In particular, we prove that, over all graphs G=(V,E) with fixed |V|3 and |E|, the average of σ(G) is at least

Full-size image

. In other words, for most graphs, σ(G)Ω(|E|).     

Oscillation criteria for first-order neutral nonlinear difference equations with variable coefficients

Consider the first-order neutral nonlinear difference equation of the form

, where τ > 0, σ_i ≥ 0 (i = 1, 2,…, m) are integers, {p_n} and {q_n} are nonnegative sequences. We obtain new criteria for the oscillation of the above equation without the restrictions Σ_n=0^∞ q_n = ∞ or Σ_n=0^∞ nq_n Σ_j=n^∞ q_j = ∞ commonly used in the literature.     

Solution of bordered singular systems in numerical continuation and bifurcation

In numerical continuation and bifurcation problems linear systems with coefficient matrices in the block form arise naturally. Here

Full-size image

and n may be large but m is small. A usually has a special structure (banded, block banded, sparse,…) and B, C, D are dense, so that it is advisable to use a specialized solver for A and to solve with M by some block method. Unfortunately, A is often also a nearly singular matrix (in fact, made nonsingular only by roundoff and truncation errors). On the other hand, M is usually nonsingular but can be ill-conditioned and in certain situations will degenerate to singularity as well. We describe numerical tests for this problem using the mixed block elimination method of Govaerts and Pryce (1993) for solving bordered linear systems with possibly nearly singular blocks A. To this end, we compute by Newton's method a triple-point bifurcation point in a parameterized reaction—diffusion equation (the Brusselator). The numerical tests show that the linear systems are solved in a stable way, in spite of the use of a black-box solver (SGBTRS from LAPACK) for a nearly singular matrix.