Sparsity-certifying Graph Decompositions

We describe a new algorithm, the (k, ℓ)-pebble game with colors, and use it to obtain a characterization of the family of (k, ℓ)-sparse graphs and algorithmic solutions to a family of problems concerning tree decompositions of graphs. Special instances of sparse graphs appear in rigidity theory and have received increased attention in recent years. In particular, our colored pebbles generalize and strengthen the previous results of Lee and Streinu [12] and give a new proof of the Tutte-Nash-Williams characterization of arboricity. We also present a new decomposition that certifies sparsity based on the (k, ℓ)-pebble game with colors. Our work also exposes connections between pebble game algorithms and previous sparse graph algorithms by Gabow [5], Gabow and Westermann [6] and Hendrickson [9]. Ileana Streinu; Research of both authors funded by the NSF under grants NSF CCF-0430990 and NSF-DARPA CARGO CCR-0310661 to the first author.     

Harmonic type approximation lemmas

We give a survey of known and not known harmonic type approximation lemmas which are descendants of the classical De Giorgi's one, and we outline some of their recent or possible applications.     

Mathematica™ in context

Aspects of the problem of teaching introductory undergraduate mathematics are considered in the context of both an increased participation rate in higher education as well as increasingly sophisticated computational technology. In particular, some of the changes in student and governmental expectations of course outcomes are canvassed, and an ongoing project initiated as a response both to these changes and to the availability of modern computational algebra systems that have sophisticated user interfaces is described. The project's aim is to develop students' mathematical understanding by undertaking practical laboratory work focused on applications that are perceived by students to be relevant to their social context and employment aspirations.     

A note on a derivation method for SDE models: Applications in biology and viability criteria

We discuss a method, which was popularized by E. J. Allen and that is frequently used in applications to construct SDE models. The derivation procedure is based on information about the elementary processes involved in the dynamics and their corresponding probabilities. We formulate criteria for the viability of the resulting models. In particular, explicit necessary and sufficient conditions are deduced for the non-negativity and/or boundedness of solutions. Moreover, we show that the class of deterministic models for which the construction leads to an admissible SDE extension is strongly limited. Several examples are presented to illustrate the implications of our results.     

Multidimensional models for analysing frequency modulated signals

In radio frequency (RF) applications, slowly varying signals often modulate the amplitude and frequency of fast carrier waves. Thus a numerical simulation of the differential algebraic equations (DAEs) modelling the electric circuit becomes tedious. Alternative models are required to achieve efficient simulations. A multivariate formulation of signals yields a suitable representation via decoupling the widely separated time scales. Consequently, the circuit's DAEs change into warped multirate partial DAEs. On the other hand, the transient behaviour of the circuit can also be approximated by a parameter-dependent DAE model including a multivariate structure. The properties of this alternative strategy are investigated. In particular, the two multidimensional approaches are compared with respect to the simulation of RF signals.     

Nonstandard finite difference methods: recent trends and further developments

In this paper, we review many recent developments and further applications of nonstandard finite difference (NSFD) methods encountered in the past decade. In particular, it is a follow up article of the one published in 2005 [K.C. Patidar, On the use of non-standard finite difference methods, J. Differ. Equ. Appl. 11 (2005), pp. 735–758]. It also includes those research contributions in this field that are very significant and published prior to the above article but were not included in the above paper simply because we did not have access to them when we wrote the above article. We also give a detailed account on various definitions/notions of NSFD methods appeared in the literature in past two decades. All contributions are listed chronologically except that in some instances we have grouped certain works to show connectivity in those fields. While categorizing these research contributions, we considered a number of different application areas. Moreover, due to space limitations, firstly, we have not included all works that used NSFD methodology but certainly important contributions are given due consideration, and secondly, we have only included the salient features of the proposed numerical schemes for many of these contributions and ignored other contents where the involved approaches sound fairly standard thus implying why these methods are known robust. Of course, the cases when there is a specific variation, in the theoretical analysis of these NSFD schemes, are highlighted with more details.     

General existence principles for Stieltjes differential equations with applications to mathematical biology

Stieltjes differential equations, which contain equations with impulses and equations on time scales as particular cases, simply consist on replacing usual derivatives by derivatives with respect to a nondecreasing function. In this paper we prove new existence results for functional and discontinuous Stieltjes differential equations and we show that such general results have real world applications. Specifically, we show that Stieltjes differential equations are specially suitable to study populations which exhibit dormant states and/or very short (impulsive) periods of reproduction. In particular, we construct two mathematical models for the evolution of a silkworm population. Our first model can be explicitly solved, as it consists on a linear Stieltjes equation. Our second model, more realistic, is nonlinear, discontinuous and functional, and we deduce the existence of solutions by means of a result proven in this paper.     

Boundary value problems for mixed type equations and applications

In this paper we outline a general method for finding well-posed boundary value problems for linear equations of mixed elliptic and hyperbolic type, which extends previous techniques of Berezanskii, Didenko, and Friedrichs. This method is then used to study a particular class of fully nonlinear mixed type equations which arise in applications to differential geometry.     

Differentiation of Multivariable Composite Functions and Bell Polynomials

We generalize the Bell polynomials in order to derive an operational tool for the differentiation of composite functions in several variables. In particular we show a formula that relates the Bell polynomials for multivariable composite functions to the classical ones. Some applications are suggested.     

A cubic differential system with nine limit cycles

Advances in Computer Algebra software have made calculations possible that were previously intractable. Our particular interest is in the investigation of limit cycles of nonlinear differential equations. We describe some recent developments in handling very large computations involving resultants and present an example of a nonlinear differential system of degree three with nine small amplitude limit cycles surrounding a focus. We know of no examples of cubic systems with more than this number bifurcating from a fine focus, as opposed to a centre. Our example appears to be the first to have been obtained without recourse to some numerical calculation.     

On a high order numerical method for functions with singularities

By splitting a given singular function into a relatively smooth part and a specially structured singular part, it is shown how the traditional Fourier method can be modified to give numerical methods of high order for calculating derivatives and integrals. Singular functions with various types of singularities of importance in applications are considered. Relations between the discrete and the continuous Fourier series for the singular functions are established. Of particular interest are piecewise smooth functions, for which various important applications are indicated, and for which numerous numerical results are presented.

     

Belief functions contextual discounting and canonical decompositions

In this article, the contextual discounting of a belief function, a classical discounting generalization, is extended and its particular link with the canonical disjunctive decomposition is highlighted. A general family of correction mechanisms allowing one to weaken the information provided by a source is then introduced, as well as the dual of this family allowing one to strengthen a belief function.     

Hyperchaotic states in the parameter-space

In this paper we propose a numerical method to characterize hyperchaotic points in the parameter-space of continuous-time dynamical systems. The method considers the second largest Lyapunov exponent value as a measure of hyperchaotic motion, to construct two-dimensional parameter-space color plots. Different levels of hyperchaos in these plots are represented by a continuously changing yellow-red scale. As an example, a particular system modeled by a set of four nonlinear autonomous first-order ordinary differential equations is considered. Practical applications of these plots include, by instance, walking in the parameter-space of hyperchaotic systems along desirable paths.     

Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k

A graph G is (k,0)‐colorable if its vertices can be partitioned into subsets V₁ and V₂ such that in G[V₁] every vertex has degree at most k, while G[V₂] is edgeless. For every integer k?0, we prove that every graph with the maximum average degree smaller than (3k+4)/(k+2) is (k,0)‐colorable. In particular, it follows that every planar graph with girth at least 7 is (8, 0)‐colorable. On the other hand, we construct planar graphs with girth 6 that are not (k,0)‐colorable for arbitrarily large k. © 2009 Wiley Periodicals, Inc. J Graph Theory 65:83–93, 2010     

An asymptotic solution to the cycle decomposition problem for complete graphs

Let m₁,m₂,…,mt be a list of integers. It is shown that there exists an integer N such that for all n?N, the complete graph of order n can be decomposed into edge-disjoint cycles of lengths m₁,m₂,…,mt if and only if n is odd, 3?mi?n for i=1,2,…,t, and . In 1981, Alspach conjectured that this result holds for all n, and that a corresponding result also holds for decompositions of complete graphs of even order into cycles and a perfect matching.     

Asymptotic cohomological functions of toric divisors

We study functions on the class group of a toric variety measuring the rates of growth of the cohomology groups of multiples of divisors. We show that these functions are piecewise polynomial with respect to finite polyhedral chamber decompositions. As applications, we express the self-intersection number of a T-Cartier divisor as a linear combination of the volumes of the bounded regions in the corresponding hyperplane arrangement and prove an asymptotic converse to Serre vanishing.     

Numerical solution to a two-dimensional hypersingular integral equation and sound propagation in urban areas

A mathematical model of sound propagation from a noise source in urban areas is constructed. The exterior Neumann problem for the scalar Helmholtz equation is reduced to a system of hypersingular integral equations. A numerical method for solving the system of integral equations is described. The convergence of the quadrature formulas underlying the numerical method is estimated. Numerical results are presented for particular applications.     

Hierarchies of Huygens' Operators and Hadamard's Conjecture

We develop a new unified approach to the problem of constructing linear hyperbolic partial differential operators that satisfy Huygens' principle in the sense of J. Hadamard. The underlying method is essentially algebraic and based on a certain nonlinear extension of similarity (gauge) transformations in the ring of analytic differential operators.The paper provides a systematic and self-consistent review of classical and recent results on Huygens' principle in Minkowski spaces. Most of these results are carried over to more general pseudo-Riemannian spaces with the metric of a plane gravitational wave.A particular attention is given to various connections of Huygens' principle with integrable systems and the soliton theory. We discuss the link to nonlinear KdV-type evolution equations, Darboux–Bäcklund transformations and the bispectral problem in the sense of Duistermaat, Grünbaum and Wilson.     

Hamiltonian identities for elliptic partial differential equations

New identities for elliptic partial differential equations are obtained. Several applications are discussed. In particular, Young's law for the contact angles in triple junction formation is proven rigorously. Structure of level curves of saddle solutions to Allen-Cahn equation are also carefully analyzed.     

An efficient approximation for stochastic differential equations on the partition ofsymmetricalirst

In certain applications of stochastic differential equations a numerical solution must be found corresponding to a particular sample path of the driving process. The order of convergence of approximations based on regular samples of the path is limited, and some approximations are asymptotically efficient in that they minimise the leading coefficient in the expansion of mean-square errors as power series in the sample step size. This paper considers approximations based on irregular samples taken at the passage times of the driving process through a series of thresholds. Such approximations can involve less computation than their regular sample counterparts, particularly for real-time applications. The orders of convergence of the Euler and Milshtein approximations are derived and a new approximation is defined which is asymptotically efficient with respect to the irregular samples. Its asymptotic mean-square error is less than half that of efficient approximations based on regular sample