A note on backward errors for structured linear systems

Let x? be a computed solution to a linear system Ax=b with , where is a proper subclass of matrices in . A structured backward error (SBE) of x? is defined by a measure of the minimal perturbations and such that (1) and that the SBE can be used to distinguish the structured backward stability of the computed solution x?. For simplicity, we may define a partial SBE of x? by a measure of the minimal perturbation such that (2) Can one use the partial SBE to distinguish the structured backward stability of x?? In this note we show that the partial SBE may be much larger than the SBE for certain structured linear systems such as symmetric Toeplitz systems, KKT systems, and dual Vandermonde systems. Besides, certain backward errors for linear least squares are discussed. Copyright © 2004 John Wiley & Sons, Ltd.     

Wave operator for the system of the Dirac–Klein–Gordon equations

We prove the existence of the wave operator for the system of the massive Dirac–Klein–Gordon equations in three space dimensions x∈ R ³ where the masses m, M>0. We prove that for the small final data , (?, ?)∈ H ^{2 + µ, 1} × H ^{1 + µ, 1}, with and , there exists a unique global solution for system (1) with the final state conditions Copyright © 2010 John Wiley & Sons, Ltd.     

A local compactness theorem for Maxwell's equations

The paper gives a proof, valid for a large class of bounded domains, of the following compactness statements: Let G be a bounded domain, β be a tensor-valued function on G satisfying certain restrictions, and let {_n} be a sequence of vector-valued functions on G where the L₂-norms of {_n}, {curl _n}, and {div(β _n)} are bounded, and where all _n either satisfy x _n = 0 or (β F_n) = 0 at the boundary ?G of G ( = normal to ?G): then {_n} has a L₂-convergent subsequence. The first boundary condition is satisfied by electric fields, the second one by magnetic fields at a perfectly conducting boundary ?G if β is interpreted as electric dielectricity ? or as magnetic permeability μ, respectively. These compactness statements are essential for the application of abstract scattering theory to the boundary value problem for Maxwell's equations.     

Die Lösung der Prae-Maxwellschen Gleichungen mit Hilfe vollständiger Lösungssysteme

This paper deals with the Neumann problem of the pre-Maxwell partial differential equations for a vector field v defined in a region G ? R ³. We approximate its uniquely determined solution (integrability conditions assumed) uniformly on G by explicitly computable particular integrals and linear combinations of vector fields with a “fundamental” sequence of points .     

Strengths and Weaknesses of LH Arithmetic

In this paper we provide a new arithmetic characterization of the levels of the og‐time hierarchy (LH). We define arithmetic classes and that correspond to ‐LOGTIME and ‐LOGTIME, respectively. We break and into natural hierarchies of subclasses and . We then define bounded arithmetic deduction systems ′ whose ‐definable functions are precisely B( ‐LOGTIME). We show these theories are quite strong in that (1) LIOpen proves for any fixed m that , (2) TAC, a theory that is slightly stronger than ′ whose (LH)‐definable functions are LH, proves LH is not equal to ‐TIME(s) for any m> 0, where 2^s ∈L, s(n) ∈ ω(log n), and (3) TAC proves LH ≠ for all k and m. We then show that the theory TAC cannot prove the collapse of the polynomial hierarchy. Thus any such proof, if it exists, must be argued in a stronger systems than ours.     

Asymptotics of solutions for sub critical non‐convective type equations

We study the Cauchy problem for non‐linear dissipative evolution equations (1) where ?? is the linear pseudodifferential operator and the non‐linearity is a quadratic pseudodifferential operator (2) û ≡ ?_x→ξ u is the Fourier transformation. We consider non‐convective type non‐linearity, that is we suppose that a(t,0,y) ≠ 0. Let the initial data , are sufficiently small and have a non‐zero total mass , where is the weighted Sobolev space. Then we give the main term of the large time asymptotics of solutions in the sub critical case. Copyright © 2004 John Wiley & Sons, Ltd.     

The generalized Randić index of trees

The generalized Randi?; index of a tree T is the sum over the edges of T of where is the degree of the vertex x in T. For all , we find the minimal constant such that for all trees on at least 3 vertices, , where is the number of vertices of T. For example, when . This bound is sharp up to the additive constant—for infinitely many n we give examples of trees T on n vertices with . More generally, fix and define , where is the number of leaves of T. We determine the best constant such that for all trees on at least 3 vertices, . Using these results one can determine (up to terms) the maximal Randi?; index of a tree with a specified number of vertices and leaves. Our methods also yield bounds when the maximum degree of the tree is restricted. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 270–286, 2007     

Infinite games in the Cantor space and subsystems of second order arithmetic

In this paper we study the determinacy strength of infinite games in the Cantor space and compare them with their counterparts in the Baire space. We show the following theorems: 1. RCA₀ ? ‐Det* ? ‐Det* ? WKL₀. 2. RCA₀ ? ( )2‐Det* ? ACA₀. 3. RCA₀ ? ‐Det* ? ‐Det* ? ‐Det ? ‐Det ? ATR₀. 4. For 1 < k < ω, RCA₀ ? ( )_k ‐Det* ? ( )_{k –1}‐Det. 5. RCA₀ ? ‐Det* ? ‐Det. Here, Det* (respectively Det) stands for the determinacy of infinite games in the Cantor space (respectively the Baire space), and ( )_k is the collection of formulas built from formulas by applying the difference operator k – 1 times. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

The independence number of an edge‐chromatic critical graph

A graph G with maximum degree Δ and edge chromatic number χ′(G)>Δ is edge‐Δ‐critical if χ′(G?e)=Δ for every edge e of G. It is proved here that the vertex independence number of an edge‐Δ‐critical graph of order n is less than . For large Δ, this improves on the best bound previously known, which was roughly ; the bound conjectured by Vizing, which would be best possible, is . © 2010 Wiley Periodicals, Inc. J Graph Theory 66:98‐103, 2011     

On hitting all maximum cliques with an independent set

We prove that every graph G for which has an independent set I such that ω(G?I)<ω(G). It follows that a minimum counterexample G to Reed's conjecture satisfies and hence also . This also applies to restrictions of Reed's conjecture to hereditary graph classes, and in particular generalizes and simplifies King, Reed and Vetta's proof of Reed's conjecture for line graphs. © 2010 Wiley Periodicals, Inc. J Graph Theory 66: 32–37, 2010     

Quasilinear degenerate parabolic equations of Kirchhoff type

We investigate the evolution problem where H is a Hilbert space, A is a self‐adjoint linear non‐negative operator on H with domain D(A), and is a continuous function. We prove that if , and , then there exists at least one global solution, which is unique if either m never vanishes, or m is locally Lipschitz continuous. Moreover, we prove that if for all , then this problem is well posed in H. On the contrary, if for some it happens that for all , then this problem has no solution if with β small enough. We apply these results to degenerate parabolic PDEs with non‐local non‐linearities. Copyright © 1999 John Wiley & Sons, Ltd.     

A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree

Let X_n be the number of cuts needed to isolate the root in a random recursive tree with n vertices. We provide a weak convergence result for X_n. The basic observation for its proof is that the probability distributions of are recursively defined by , where D_n is a discrete random variable with ? , which is independent of . This distributional recursion was not studied previously in the sense of weak convergence. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Global solutions in a fully parabolic chemotaxis system with singular sensitivity

The Neumann boundary value problem for the chemotaxis system is considered in a smooth bounded domain Ω??ⁿ, n?2, with initial data and v₀∈W^{1, ∞}(Ω) satisfying u₀?0 and v₀>0 in . It is shown that if then for any such data there exists a global‐in‐time classical solution, generalizing a previous result which asserts the same for n=2 only. Furthermore, it is seen that the range of admissible χ can be enlarged upon relaxing the solution concept. More precisely, global existence of weak solutions is established whenever . Copyright © 2010 John Wiley & Sons, Ltd.     

On asymmetric coverings and covering numbers

An asymmetric covering is a collection of special subsets S of an n‐set such that every subset T of the n‐set is contained in at least one special S with . In this paper we compute the smallest size of any for We also investigate “continuous” and “banded” versions of the problem. The latter involves the classical covering numbers , and we determine the following new values: , , , , and . We also find the number of non‐isomorphic minimal covering designs in several cases. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 218–228, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10022     

Tauberian theorem for m‐spherical transforms on the Heisenberg group

In this paper we prove a Tauberian type theorem for the space L ( H _n ). This theorem gives sufficient conditions for a L ( H _n ) submodule J ? L ( H _n ) to make up all of L ( H _n ). As a consequence of this theorem, we are able to improve previous results on the Pompeiu problem with moments on the Heisenberg group for the space L^∞( H _n ). In connection with the Pompeiu problem, given the vanishing of integrals ∫ z ^m L _g f ( z , 0) dσ ( z ) = 0 for all g ∈ H _n and i = 1, 2 for appropriate radii r₁ and r₂, we now have the (improved) conclusion f ≡ 0, where = · · · and form the standard basis for T^(0,1)( H _n ). (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Compactness Conditions for the Green Operator in Lp(ℝ) Corresponding to a General Sturm–Liouville Operator

We consider the equation ℝ, where , for ℝ, (ℝ), (ℝ), (ℝ), (ℝ) := C(ℝ)). We give necessary and sufficient conditions under which, regardless of , the following statements hold simultaneously: I) For any (ℝ) Equation (0.1) has a unique solution (ℝ) where $\int ^{\infty}_{-\infty}$ ℝ. II) The operator (ℝ) → (ℝ) is compact. Here is the Green function corresponding to (0.1). This result is applied to study some properties of the spectrum of the Sturm–Liouville operator.     

Between ends and fibers

Let Γ be an infinite, locally finite, connected graph with distance function δ. Given a ray P in Γ and a constant C ≥ 1, a vertex‐sequence is said to be regulated by C if, for all n??, never precedes x_n on P, each vertex of P appears at most C times in the sequence, and . R. Halin (Math. Ann., 157, 3 , 125–137) defined two rays to be end‐equivalent if they are joined by infinitely many pairwise‐disjoint paths; the resulting equivalence classes are called ends. More recently H. A. Jung (Graph Structure Theory, Contemporary Mathematics, 147, 6 , 477–484) defined rays P and Q to be b‐equivalent if there exist sequences and VQ regulated by some constant C ≥ 1 such that for all n??; he named the resulting equivalence classes b‐fibers. Let denote the set of nondecreasing functions from into the set of positive real numbers. The relation (called f‐equivalence) generalizes Jung's condition to . As f runs through , uncountably many equivalence relations are produced on the set of rays that are no finer than b‐equivalence while, under specified conditions, are no coarser than end‐equivalence. Indeed, for every Γ there exists an “end‐defining function” that is unbounded and sublinear and such that implies that P and Q are end‐equivalent. Say if there exists a sublinear function such that . The equivalence classes with respect to are called bundles. We pursue the notion of “initially metric” rays in relation to bundles, and show that in any bundle either all or none of its rays are initially metric. Furthermore, initially metric rays in the same bundle are end‐equivalent. In the case that Γ contains translatable rays we give some sufficient conditions for every f‐equivalence class to contain uncountably many g‐equivalence classes (where ). We conclude with a variety of applications to infinite planar graphs. Among these, it is shown that two rays whose union is the boundary of an infinite face of an almost‐transitive planar map are never bundle‐ equivalent. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 125–153, 2007     

Uniqueness of Integrable Solutions ∇ζ = Gζ, ζ∣Γ = 0 for Integrable Tensor-Coefficients G and Applications to Elasticity

Let be bounded Lipschitz and relatively open. We show that the solution to the linear first order system 1 : (1) vanishes if and , (e.g. ). We prove to be a norm if with , for some p, q > 1 with 1/p + 1/q = 1 and . We give a new proof for the so called ‘in-finitesimal rigid displacement lemma’ in curvilinear coordinates: Let , satisfy for some with . Then there are and a constant skew-symmetric matrix , such that . (© 2013 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

On the Points on the Unit Circle with Finite b–Adic Expansions

Let be an arbitrary integer base and let be the number of different prime factors of with , . Further let be the set of points on the unit circle with finite –adic expansions of their coordinates and let be the set of angles of the points . Then is an additive group which is the direct sum of infinite cyclic groups and of the finite cyclic group . If in case of the points of are arranged according to the number of digits of their coordinates, then the arising sequence is uniformly distributed on the unit circle. On the other hand, in case of the only points in are the exceptional points (1, 0), (0, 1), (–1, 0), (0, –1). The proofs are based on a canonical form for all integer solutions of .     

Random coloring method in the combinatorial problem of Erdős and Lovász

The work deals with a combinatorial problem of P. Erd?s and L. Lovász concerning simple hypergraphs. Let denote the minimum number of edges in an n‐uniform simple hypergraph with chromatic number at least . The main result of the work is a new asymptotic lower bound for . We prove that for large n and r satisfying the following inequality holds where . This bound improves previously known bounds for . The proof is based on a method of random coloring. We have also obtained results concerning colorings of h‐simple hypergraphs. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2012