An iterative adaptive finite element method for elliptic eigenvalue problems

We consider the task of resolving accurately the n$n$th eigenpair of a generalized eigenproblem rooted in some elliptic partial differential equation (PDE), using an adaptive finite element method (FEM). Conventional adaptive FEM algorithms call a generalized eigensolver after each mesh refinement step. This is not practical in our situation since the generalized eigensolver needs to calculate n$n$ eigenpairs after each mesh refinement step, it can switch the order of eigenpairs, and for repeated eigenvalues it can return an arbitrary linear combination of eigenfunctions from the corresponding eigenspace. In order to circumvent these problems, we propose a novel adaptive algorithm that only calls a generalized eigensolver once at the beginning of the computation, and then employs an iterative method to pursue a selected eigenvalue–eigenfunction pair on a sequence of locally refined meshes. Both Picard’s and Newton’s variants of the iterative method are presented. The underlying partial differential equation (PDE) is discretized with higher-order finite elements (hp$hp$-FEM) but the algorithm also works for standard low-order FEM. The method is described and accompanied with theoretical analysis and numerical examples. Instructions on how to reproduce the results are provided.     

Two phase transitions for the contact process on small worlds

In our version of Watts and Strogatz’s small world model, space is a d$d$-dimensional torus in which each individual has in addition exactly one long-range neighbor chosen at random from the grid. This modification is natural if one thinks of a town where an individual’s interactions at school, at work, or in social situations introduce long-range connections. However, this change dramatically alters the behavior of the contact process, producing two phase transitions. We establish this by relating the small world to an infinite “big world” graph where the contact process behavior is similar to the contact process on a tree. We then consider the contact process on a slightly modified small world model in order to show that its behavior is decidedly different from that of the contact process on a tree.     

Directed graphs,decompositions, and spatial linkages

The decomposition of a linkage into minimal components is a central tool of analysis and synthesis of linkages. In this paper we prove that every pinned d$d$-isostatic (minimally rigid) graph (grounded linkage) has a unique decomposition into minimal strongly connected components (in the sense of directed graphs), or equivalently into minimal pinned isostatic graphs, which we call d$d$-Assur graphs. We also study key properties of motions induced by removing an edge in a d$d$-Assur graph — defining a sharper subclass of strongly d$d$-Assur graphs by the property that all inner vertices go into motion, for each removed edge. The strongly 3-Assur graphs are the central building blocks for kinematic linkages in 3-space and the 3-Assur graphs are components in the analysis of built linkages. The d$d$-Assur graphs share a number of key combinatorial and geometric properties with the 2-Assur graphs, including an associated lower block-triangular decomposition of the pinned rigidity matrix which provides modular information for extending the motion induced by inserting one driver in a bottom Assur linkage to the joints of the entire linkage. We also highlight some problems in combinatorial rigidity in higher dimensions (d≥3$d\ge 3$) which cause the distinction between d$d$-Assur and strongly d$d$-Assur which did not occur in the plane.     

A finite dimensional approximation of the effective diffusivity for a symmetric random walk in a random environment

We consider a nearest neighbor, symmetric random walk on a homogeneous, ergodic random lattice Z^d${\mathbb{Z}}^d$. The jump rates of the walk are independent, identically Bernoulli distributed random variables indexed by the bonds of the lattice. A standard result from the homogenization theory, see [A. De Masi, P.A. Ferrari, S. Goldstein, W.D. Wick, An invariance principle for reversible Markov processes, Applications to random walks in random environments, J. Statist. Phys. 55(3/4) (1989) 787–855], asserts that the scaled trajectory of the particle satisfies the functional central limit theorem. The covariance matrix of the limiting normal distribution is called the effective diffusivity of the walk. We use the duality structure corresponding to the product Bernoulli measure to construct a numerical scheme that approximates this parameter when d?3$d?3$. The estimates of the convergence rates are also provided.     

Matchings in graphs of odd regularity and girth

We establish lower bounds on the matching number of graphs of given odd regularity d$d$ and odd girth g$g$, which are sharp for many values of d$d$ and g$g$. For d=g=5$d=g=5$, we characterize all extremal graphs.     

A unified proof of Brooks’ theorem and Catlin’s theorem

Brooks’ theorem is a fundamental result in the theory of graph coloring. Catlin proved the following strengthening of Brooks’ theorem: Let d$d$ be an integer at least 3, and let G$G$ be a graph with maximum degree d$d$. If G$G$ does not contain _Kd+1$K_{d+1}$ as a subgraph, then G$G$ has a d$d$-coloring in which one color class has size α(G)$\alpha \left(G\right)$. Here α(G)$\alpha \left(G\right)$ denotes the independence number of G$G$. We give a unified proof of Brooks’ theorem and Catlin’s theorem.     

A contact process with mutations on a tree

Consider the following stochastic model for immune response. Each pathogen gives birth to a new pathogen at rate λ$\lambda$. When a new pathogen is born, it has the same type as its parent with probability 1−r$1-r$. With probability r$r$, a mutation occurs, and the new pathogen has a different type from all previously observed pathogens. When a new type appears in the population, it survives for an exponential amount of time with mean 1, independently of all the other types. All pathogens of that type are killed simultaneously. Schinazi and Schweinsberg [R.B. Schinazi, J. Schweinsberg, Spatial and non-spatial stochastic models for immune response, Markov Process. Related Fields (2006) (in press)] have shown that this model on Z^d${\mathbb{Z}}^d$ behaves rather differently from its non-spatial version. In this paper, we show that this model on a homogeneous tree captures features from both the non-spatial version and the Z^d${\mathbb{Z}}^d$ version. We also obtain comparison results, between this model and the basic contact process on general graphs.     

On the construction of optimal cubature formulae which use integrals over hyperspheres

We consider formulae of approximate integration over a d$d$-dimensional ball which use n$n$ surface integrals along (d-1)$(d-1)$-dimensional spheres centered at the origin. For a class of functions defined on the ball with gradients satisfying an integral restriction, optimal formulae of this type are obtained.     

Limit theorems for occupation time fluctuations of branching systems I: Long-range dependence

We give a functional limit theorem for the fluctuations of the rescaled occupation time process of a critical branching particle system in R^d${\mathbb{R}}^d$ with symmetric α$\alpha$-stable motion and α<d<2α$\alpha <d<2\alpha$, which leads to a long-range dependence process involving sub-fractional Brownian motion. We also give an analogous result for the system without branching and d<α$d<\alpha$, which involves fractional Brownian motion. We use a space–time random field approach.     

Representation theory of the Yokonuma–Hecke algebra

We develop an inductive approach to the representation theory of the Yokonuma–Hecke algebra _Yd,n(q)${\mathrm{Y}}_{d,n}(q)$, based on the study of the spectrum of its Jucys–Murphy elements which are defined here. We give explicit formulas for the irreducible representations of _Yd,n(q)${\mathrm{Y}}_{d,n}(q)$ in terms of standard d  -tableaux; we then use them to obtain a semisimplicity criterion. Finally, we prove the existence of a canonical symmetrising form on _Yd,n(q)${\mathrm{Y}}_{d,n}(q)$ and calculate the Schur elements with respect to that form.     

Limit theorems for occupation time fluctuations of branching systems II: Critical and large dimensions

We give functional limit theorems for the fluctuations of the rescaled occupation time process of a critical branching particle system in R^d${\mathbb{R}}^d$ with symmetric α$\alpha$-stable motion in the cases of critical and large dimensions, d=2α$d=2\alpha$ and d>2α$d>2\alpha$. In a previous paper [T. Bojdecki, L.G. Gorostiza, A. Talarczyk, Limit theorems for occupation time fluctuations of branching systems I: long-range dependence, Stochastic Process. Appl., this issue.] we treated the case of intermediate dimensions, α<d<2α$\alpha <d<2\alpha$, which leads to a long-range dependence limit process. In contrast, in the present cases the limits are generalized Wiener processes. We use the same space–time random field method of the previous paper, the main difference being that now the tightness requires a new approach and the proofs are more difficult. We also give analogous results for the system without branching in the cases d=α$d=\alpha$ and d>α$d>\alpha$.     

Some results on monotone metric spaces

We present some new results on monotone metric spaces. We prove that every bounded 1-monotone metric space in R^d${\mathbb{R}}^d$ has a finite 1-dimensional Hausdorff measure. As a consequence we obtain that each continuous bounded curve in R^d${\mathbb{R}}^d$ has a finite length if and only if it can be written as a finite sum of 1-monotone continuous bounded curves. Next we construct a continuous function f such that M   has a zero Lebesgue measure provided the graph(f|M)$\mathrm{graph}(f|M)$ is a monotone set in the plane. We finally construct a differentiable function with a monotone graph and unbounded variation.     

Time version of the shortest path problem in a stochastic-flow network

Many studies on hardware framework and routing policy are devoted to reducing the transmission time for a flow network. A time version of the shortest path problem thus arises to find a quickest path, which sends a given amount of data from the unique source to the unique sink with minimum transmission time. More specifically, the capacity of each arc in the flow network is assumed to be deterministic. However, in many real-life networks, such as computer systems, telecommunication systems, etc., the capacity of each arc should be stochastic due to failure, maintenance, etc. Such a network is named a stochastic-flow network. Hence, the minimum transmission time is not a fixed number. We extend the quickest path problem to evaluating the probability that d$d$ units of data can be sent under the time constraint T$T$. Such a probability is named the system reliability. In particular, the data are transmitted through two minimal paths simultaneously in order to reduce the transmission time. A simple algorithm is proposed to generate all (d,T)$(d,T)$-MPs and the system reliability can then be computed in terms of (d,T)$(d,T)$-MPs. Moreover, the optimal pair of minimal paths with highest system reliability could be obtained.     

Disjoint cycles with different length in 4-arc-dominated digraphs

A d$d$-arc-dominated digraph is a digraph D$D$ of minimum out-degree d$d$ such that for every arc (x,y)$(x,y)$ of D$D$, there exists a vertex u$u$ of D$D$ of out-degree d$d$ such that (u,x)$(u,x)$ and (u,y)$(u,y)$ are arcs of D$D$. Henning and Yeo [Vertex disjoint cycles of different length in digraphs, SIAM J. Discrete Math. 26 (2012) 687–694] conjectured that a digraph with minimum out-degree at least four contains two vertex-disjoint cycles of different length. In this paper, we verify this conjecture for 4-arc-dominated digraphs.     

Profile decompositions of fractional Schrödinger equations with angularly regular data

We study the fractional Schrödinger equations in R^1+d${\mathbb{R}}^{1+d}$, d?3$d?3$, of order d/(d−1)<α<2$d/(d-1)<\alpha <2$. Under the angular regularity assumption we prove linear and nonlinear profile decompositions which extend the previous results [9] to data without radial assumption. As applications we show blowup phenomena of solutions to mass-critical fractional Hartree equations.     

Multi-tiling and Riesz bases

Let S   be a bounded, Riemann measurable set in R^d${\mathbb{R}}^d$, and Λ be a lattice. By a theorem of Fuglede, if S   tiles R^d${\mathbb{R}}^d$ with translation set Λ, then S has an orthogonal basis of exponentials. We show that, under the more general condition that S multi-tiles  R^d${\mathbb{R}}^d$ with translation set Λ, S has a Riesz basis of exponentials. The proof is based on Meyer?s quasicrystals.     

Approximation numbers of Sobolev embeddings—Sharp constants and tractability

We investigate optimal linear approximations (approximation numbers) in the context of periodic Sobolev spaces H^s(T^d)$H^s\left({\mathbb{T}}^d\right)$ of fractional smoothness s>0$s>0$ for various equivalent norms including the classical one. The error is always measured in _L2(T^d)$L_2\left({\mathbb{T}}^d\right)$. Particular emphasis is given to the dependence of all constants on the dimension d$d$. We capture the exact decay rate in n$n$ and the exact decay order of the constants with respect to d$d$, which is in fact polynomial. As a consequence we observe that none of our considered approximation problems suffers from the curse of dimensionality. Surprisingly, the square integrability of all weak derivatives up to order three (classical Sobolev norm) guarantees weak tractability of the associated multivariate approximation problem.