First order limits of sparse graphs: Plane trees and path‐width

Ne?et?il and Ossona de Mendez introduced the notion of first order convergence as an attempt to unify the notions of convergence for sparse and dense graphs. It is known that there exist first order convergent sequences of graphs with no limit modeling (an analytic representation of the limit). On the positive side, every first order convergent sequence of trees or graphs with no long path (graphs with bounded tree‐depth) has a limit modeling. We strengthen these results by showing that every first order convergent sequence of plane trees (trees with embeddings in the plane) and every first order convergent sequence of graphs with bounded path‐width has a limit modeling. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 612–635, 2017     

A Gallai–Edmonds‐type structure theorem for path‐matchings

As a generalization of matchings, Cunningham and Geelen introduced the notion of path‐matchings. We give a structure theorem for path‐matchings which generalizes the fundamental Gallai–Edmonds structure theorem for matchings. Our proof is purely combinatorial. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 93–102, 2004     

On the time discrete approximation of the Brinkman–Forchheimer equations

In this work, we study the structural stability of the fully implicit Euler scheme for the Brinkman‐Forchheimer equations. More precisely, we consider the time discretization scheme of the unsteady Brinkman–Forchheimer equations, and we prove the existence of solutions. Moreover, we derive somebia priori estimates of the discrete in time solutions. Next, with the aid of the discrete Gronwall lemma, we show that the numerical solutions depend continuously on the Brinkman and the Forchheimer coefficient. Copyright © 2011 John Wiley & Sons, Ltd.     

On one problem for comonotone approximation

We prove that, for comonotone approximation, an analog of the second Jackson inequality with generalized Ditzian-Totik modulus of continuity ω _{k, r} ^ϕ is not true for (k, r) = (2, 2) even in the case where the constant depends on a function. __________ Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 57, No. 10, pp. 1424–1429, October, 2005.     

A Wiener–Hopf approximation technique for a multiple plate diffraction problem

An approximation method is derived for the computation of the acoustic field between a series of parallel plates, subject to a time periodic incident field. The method is based on the Wiener–Hopf method of factorization, with computations involving orthogonal bases of functions that are analytic in the complex half‐plane. Copyright 2004 John Wiley & Sons, Ltd.     

On a continuous time stochastic approximation problem

This paper is concerned with a continuous time stochastic approximation/optimization problem. The algorithm is given by a pair of differential-integral equations. Our main effort is to derive the asymptotic properties of the algorithm. It is shown that ast , a suitably normalized sequence of the estimation error,t(¯x _tr–) is equivalent to a scaled sequence of the random noise process, namely, (1/t) ₀ ^tr _sds. Consequently, the asymptotic normality is obtained via a functional invariance theorem, and the asymptotic covariance matrix is shown to be the optimal one. As a result, the algorithm is asymptotically efficient.Supported in part by the National Science Foundation, and in part by Wayne State University.Supported in part by Wayne State University through a research assistantship.     

On generalized matrix approximation problem in the spectral norm

In this paper theoretical results regarding a generalized minimum rank matrix approximation problem in the spectral norm are presented. An alternative solution expression for the generalized matrix approximation problem is obtained. This alternative expression provides a simple characterization of the achievable minimum rank, which is shown to be the same as the optimal objective value of the classical problem considered by Eckart–Young–Schmidt–Mirsky, as long as the generalized problem is feasible. In addition, this paper provides a result on a constrained version of the matrix approximation problem, establishing that the later problem is solvable via singular value decomposition.     

On the complexity of the multivariate Sturm–Liouville eigenvalue problem

We study the complexity of approximating the smallest eigenvalue of -Δ+q with Dirichlet boundary conditions on the d-dimensional unit cube. Here Δ is the Laplacian, and the function q is non-negative and has continuous first order partial derivatives. We consider deterministic and randomized classical algorithms, as well as quantum algorithms using quantum queries of two types: bit queries and power queries. We seek algorithms that solve the problem with accuracy . We exhibit lower and upper bounds for the problem complexity. The upper bounds follow from the cost of particular algorithms. The classical deterministic algorithm is optimal. Optimality is understood modulo constant factors that depend on d. The randomized algorithm uses an optimal number of function evaluations of q when d≤2. The classical algorithms have cost exponential in d since they need to solve an eigenvalue problem involving a matrix with size exponential in d. We show that the cost of quantum algorithms is not exponential in d, regardless of the type of queries they use. Power queries enjoy a clear advantage over bit queries and lead to an optimal complexity algorithm.     

On the quadratic finite element approximation to the obstacle problem

Summary. In this paper, we obtain the error bound for any , for the piecewise quadratic finite element approximation to the obstacle problem, without the hypothesis that the free boundary has finite length (see [3]). Received October 31, 2000 / Revised version received July 23, 2001 / Published online October 17, 2001 The project was supported by the National Natural Science Foundation of China     

On the Cauchy problem for Wigner–Poisson–BGK equation in the Wiener algebra

In this paper, we prove the existence and uniqueness of the local mild solution to the Cauchy problem of the n‐dimensional (n≥3) Wigner–Poisson–BGK equation in the space of some integrable functions whose inverse Fourier transform are integrable. The main difficulties in establishing mild solution are to derive the boundedness and locally Lipschitz properties of the appropriate nonlinear terms in the Wiener algebra. Copyright © 2015 John Wiley & Sons, Ltd.     

On the finite element approximation of a cascade flow problem

Summary The finite element analysis of a cascade flow problem with a given velocity circulation round profiles is presented. The nonlinear problem for the stream function with nonstandard boundary conditions is discretized by conforming linear triangular elements. We deal with the properties of the discrete problem and study the convergence of the method both for polygonal and nonpolygonal domains, including the effect of numerical integration.     

On the Hamilton–Waterloo problem with odd cycle lengths

Let denote the complete graph if v is odd and , the complete graph with the edges of a 1‐factor removed, if v is even. Given nonnegative integers , the Hamilton–Waterloo problem asks for a 2‐factorization of into α ‐factors and β ‐factors, with a ‐factor of being a spanning 2‐regular subgraph whose components are ℓ‐cycles. Clearly, , , and are necessary conditions. In this paper, we extend a previous result by the same authors and show that for any odd the above necessary conditions are sufficient, except possibly when , or when . Note that in the case where v is odd, M and N must be odd. If M and N are odd but v is even, we also show sufficiency but with further possible exceptions. In addition, we provide results on 2‐factorizations of the complete equipartite graph and the lexicographic product of a cycle with the empty graph.     

Note on the path‐matching formula

As a common generalization of matchings and matroid intersections, W.H. Cunningham and J.F. Geelen introduced the notion of path‐matchings. They proved a min‐max formula for the maximum value. Here, we exhibit a simplified version of their min‐max theorem and provide a purely combinatorial proof. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 110–119, 2002