On percolation and ‐hardness

The edge‐percolation and vertex‐percolation random graph models start with an arbitrary graph G, and randomly delete edges or vertices of G with some fixed probability. We study the computational complexity of problems whose inputs are obtained by applying percolation to worst‐case instances. Specifically, we show that a number of classical ‐hard problems on graphs remain essentially as hard on percolated instances as they are in the worst‐case (assuming ). We also prove hardness results for other ‐hard problems such as Constraint Satisfaction Problems and Subset‐Sum, with suitable definitions of random deletions. Along the way, we establish that for any given graph G the independence number and the chromatic number are robust to percolation in the following sense. Given a graph G, let be the graph obtained by randomly deleting edges of G with some probability . We show that if is small, then remains small with probability at least 0.99. Similarly, we show that if is large, then remains large with probability at least 0.99. We believe these results are of independent interest.     

Law of the iterated logarithm for random graphs

A milestone in probability theory is the law of the iterated logarithm (LIL), proved by Khinchin and independently by Kolmogorov in the 1920s, which asserts that for iid random variables with mean 0 and variance 1 In this paper we prove that LIL holds for various functionals of random graphs and hypergraphs models. We first prove LIL for the number of copies of a fixed subgraph H. Two harder results concern the number of global objects: perfect matchings and Hamiltonian cycles. The main new ingredient in these results is a large deviation bound, which may be of independent interest. For random k‐uniform hypergraphs, we obtain the Central Limit Theorem and LIL for the number of Hamilton cycles.     

Implicit–explicit schemes for nonlinear nonlocal equations with a gradient flow structure in one space dimension

Nonlinear convection–diffusion equations with nonlocal flux and possibly degenerate diffusion arise in various contexts including interacting gases, porous media flows, and collective behavior in biology. Their numerical solution by an explicit finite difference method is costly due to the necessity of discretizing a local spatial convolution for each evaluation of the convective numerical flux, and due to the disadvantageous Courant–Friedrichs–Lewy (CFL) condition incurred by the diffusion term. Based on explicit schemes for such models devised in the study of Carrillo et al. a second‐order implicit–explicit Runge–Kutta (IMEX‐RK) method can be formulated. This method avoids the restrictive time step limitation of explicit schemes since the diffusion term is handled implicitly, but entails the necessity to solve nonlinear algebraic systems in every time step. It is proven that this method is well defined. Numerical experiments illustrate that for fine discretizations it is more efficient in terms of reduction of error versus central processing unit time than the original explicit method. One of the test cases is given by a strongly degenerate parabolic, nonlocal equation modeling aggregation in study of Betancourt et al. This model can be transformed to a local partial differential equation that can be solved numerically easily to generate a reference solution for the IMEX‐RK method, but is limited to one space dimension.     

Restricted thresholding: recovering smoothness and preserving edges

Restricted non linear approximation is a generalization of the N‐term approximation in which a measure on the index set of the approximants controls the type, instead of the number, of elements in the approximation. Thresholding is a well‐known type of non linear approximation. We relate a generalized upper and lower Temlyakov property with the decreasing rate of the thresholding approximation. This relation is in the form of a characterization through some general discrete Lorentz spaces. Thus, not only we recover some results in the literature but find new ones. As an application of these results, we compress and reduce noise of some images with wavelets and shearlets and show, at least empirically, that the L²‐norm is not necessarily the best norm to measure the approximation error.     

A sufficient condition for the existence of a principal eigenvalue for nonlocal diffusion equations with applications

Considerable work has gone into studying the properties of nonlocal diffusion equations. The existence of a principal eigenvalue has been a significant portion of this work. While there are good results for the existence of a principal eigenvalue equations on a bounded domain, few results exist for unbounded domains. On bounded domains, the Krein–Rutman theorem on Banach spaces is a common tool for showing existence. This article shows that generalized Krein–Rutman can be used on unbounded domains and that the theory of positive operators can serve as a powerful tool in the analysis of nonlocal diffusion equations. In particular, a useful sufficient condition for the existence of a principal eigenvalue is given.     

Bilinear biorthogonal expansions and the Dunkl kernel on the real line

We study an extension of the classical Paley–Wiener space structure, which is based on bilinear expansions of integral kernels into biorthogonal sequences of functions. The structure includes both sampling expansions and Fourier–Neumann type series as special cases, and it also provides a bilinear expansion for the Dunkl kernel (in the rank 1 case) which is a Dunkl analogue of Gegenbauer’s expansion of the plane wave and the corresponding sampling expansions. In fact, we show how to derive sampling and Fourier–Neumann type expansions from the results related to the bilinear expansion for the Dunkl kernel.     

Positive and Nontrivial Solutions for the Urysohn Integral Equation

We establish new criteria for the existence of either positive or nonzero solutions of the Urysohn integral equation. We also discuss the existence of an interval of positive eigenvalues and sufficient conditions for the existence of at least a positive eigenvalue with a nonzero or positive eigenfunction for the Urysohn integral operator. Among others, we employ techniques based on fixed point index theory for compact maps, which are new for this type of equation.     

A computational two scaled model for the simulation of micro-heterogeneous low-alloyed TRIP steels

In transformation induced plasticity (TRIP) steel a diffusionless austenitic-martensitic phase transformation induced by plastic deformation can be observed, resulting in excellent macroscopic properties. In particular low-alloyed TRIP steels, which can be obtained at lower production costs than high-alloyed TRIP steel, combine this mechanism with a heterogeneous arrangement of different phases at the microscale, namely ferrite, bainite, and retained austenite. The macroscopic behavior is governed by a complex interaction of the phases at the micro-level and the inelastic phase transformation from retained austenite to martensite. A reliable model for low-alloyed TRIP steel should therefore account for these microstructural processes to achieve an accurate macroscopic prediction. To enable this, we focus on a multiscale method often referred to as FE² approach, see [6]. In order to obtain a reasonable representative volume element, a three-dimensional statistically similar representative volume element (SSRVE) [1] can be used. Thereby, also computational costs associated with FE² calculations can be significantly reduced at a comparable prediction quality. The material model used here to capture the above mentioned microstructural phase transformation is based on [3] which was proposed for high alloyed TRIP steels, see also e.g. [8]. Computations based on the proposed two-scale approach are presented here for a three dimensional boundary value problem to show the evolution of phase transformation at the microscale and its effects on the macroscopic properties. (© 2016 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Embedding of analytic function spaces with given mean growth of the derivative

If ? is a positive function defined in [0, 1) and 0 < p < ∞, we consider the space ??(p, ?) which consists of all functions f analytic in the unit disc ?? for which the integral means of the derivative M _p (r, f ′) = 0 < r < 1, satisfy M _p (r, f ′) = O(? (r)), as r → 1. In this paper, for any given p ∈ (0, 1), we characterize the functions ?, among a certain class of weight functions, to be able to embedd ??(p, ?) into classical function spaces. These results complement other previously obtained by the authors for p ≥ 1. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Degree distribution of the greatest common divisor of polynomials over 𝔽q

We study the degree distribution of the greatest common divisor of two or more random polynomials over a finite field ??_q. We provide estimates for several parameters like number of distinct common irreducible factors, number of irreducible factors counting repetitions, and total degree of the gcd of two or more polynomials. We show that the limiting distribution of a random variable counting the total degree of the gcd is geometric and that the distributions of random variables counting the number of common factors (with and without repetitions) are very close to Poisson distributions when q is large. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006