Search

The abstract results and applications presented in “Controllability of fractional neutral stochastic functional differential systems, Z. Angew. Math. Phys. 65 (2014), no. 5, 941–959, are not correct. Moreover, the class of differential control problems studied in [1] is not H-controllable.

It is pointed out that the proof of the basic result of Rahmanov's paper has a serious gap. It is documented by original sources that a statement he relied on in the proof contains a misprint, and it is shown by a counterexample that this statement (with the misprint) is, in fact, false. A somewhat weaker statement is proved true.

A regular system is a Delone set in Euclidean space with a transitive group of symmetries or, in other words, the orbit of a crystallographic group. The local theory for regular systems, created by the geometric school of B. N. Delone, was aimed, in particular, to rigorously establish the “local-global-order” link, i.e., the link between the arrangement of a set around each of its points and symmetry/regularity of the set as a whole. The main result of this paper is a proof of the so-called 10R-theorem. This theorem asserts that identity of neighborhoods within a radius 10R of all points of a Delone set (in other words, an (r, R)-system) in 3D Euclidean space implies regularity of this set. The result was obtained and announced long ago independently by M. Shtogrin and the author of this paper. However, a detailed proof remains unpublished for many years. In this paper, we give a proof of the 10R-theorem. In the proof, we use some recent results of the author, which simplify the proof.

We introduce and develop a theory of limits for sequences of sparse graphs based on $L^p$ graphons, which generalizes both the existing $L^\infty$ theory of dense graph limits and its extension by Bollob\'as and Riordan to sparse graphs without dense spots. In doing so, we replace the no dense spots hypothesis with weaker assumptions, which allow us to analyze graphs with power law degree distributions. This gives the first broadly applicable limit theory for sparse graphs with unbounded average degrees. In this paper, we lay the foundations of the $L^p$ theory of graphons, characterize convergence, and develop corresponding random graph models, while we prove the equivalence of several alternative metrics in a companion paper., Comment: 44 pages

The Hermite–Hadamard inequality was extended using iterated integrals by Retkes [Acta Sci Math (Szeged) 74:95–106, 2008]. In this paper we further extend the main results of the above paper for convex and also for s-convex functions in the second sense.

In this paper we introduce a general framework for the study of limits of relational structures in general and graphs in particular, which is based on a combination of model theory and (functional) analysis. We show how the various approaches to graph limits fit to this framework and that they naturally appear as "tractable cases" of a general theory. As an outcome of this, we provide extensions of known results. We believe that this put these into next context and perspective. For example, we prove that the sparse--dense dichotomy exactly corresponds to random free graphons. The second part of the paper is devoted to the study of sparse structures. First, we consider limits of structures with bounded diameter connected components and we prove that in this case the convergence can be "almost" studied component-wise. We also propose the structure of limits objects for convergent sequences of sparse structures. Eventually, we consider the specific case of limits of colored rooted trees with bounded height and of graphs with bounded tree-depth, motivated by their role of elementary brick these graphs play in decompositions of sparse graphs, and give an explicit construction of a limit object in this case. This limit object is a graph built on a standard probability space with the property that every first-order definable set of tuples is measurable. This is an example of the general concept of {\em modeling} we introduce here. Our example is also the first "intermediate class" with explicitly defined limit structures., Comment: added journal reference

The main purpose of this paper is to explore the structure of local and regular Dirichlet forms associated with symmetric one-dimensional diffusions, which are also called symmetric linear diffusions. Let ( E , F ) (\mathcal {E},\mathcal {F}) be a regular and local Dirichlet form on L 2 ( I , m ) L^2(I,m) , where I I is an interval and m m is a fully supported Radon measure on I I . We shall first present a complete representation for ( E , F ) (\mathcal {E},\mathcal {F}) , which shows that ( E , F ) (\mathcal {E},\mathcal {F}) lives on at most countable disjoint “effective" intervals with an “adapted" scale function on each interval, and any point outside these intervals is a trap of the one-dimensional diffusion. Furthermore, we shall give a necessary and sufficient condition for C c ∞ ( I ) C_c^\infty (I) being a special standard core of ( E , F ) (\mathcal {E},\mathcal {F}) and shall identify the closure of C c ∞ ( I ) C_c^\infty (I) in ( E , F ) (\mathcal {E},\mathcal {F}) when C c ∞ ( I ) C_c^\infty (I) is contained but not necessarily dense in F \mathcal {F} relative to the E 1 1 / 2 \mathcal {E}_1^{1/2} -norm. This paper is partly motivated by a result of Hamza’s that was stated in a theorem of Fukushima, Oshima, and Takeda’s and that provides a different point of view to this theorem. To illustrate our results, many examples are provided.

In this paper we suggest a method for transforming a vector subdivision scheme generating $C^{\ell}$ limits to another such scheme of the same dimension, generating $C^{\ell+1}$ limits. In scalar subdivision, it is well known that a scheme generating $C^{\ell}$ limit curves can be transformed to a new scheme producing $C^{\ell+1}$ limit curves by multiplying the scheme's symbol with the smoothing factor $\tfrac{z+1}{2}$. We extend this approach to vector and Hermite subdivision schemes, by manipulating symbols. The algorithms presented in this paper allow to construct vector (Hermite) subdivision schemes of arbitrarily high regularity from a convergent vector scheme (from a Hermite scheme whose Taylor scheme is convergent with limit functions of vanishing first component)., 28 pages, 4 figures. Corrected typos, updated contact information

In this paper our aim is to show some new inequalities of the Redheffer type for Bessel and modified Bessel functions of the first kind. The key tools in our proofs are some classical results on the monotonicity of quotients of differentiable functions as well as on the monotonicity of quotients of two power series. We also use some known results on the quotients of Bessel and modified Bessel functions of the first kind, and by using the monotonicity of the Dirichlet eta function we prove a sharp inequality for the tangent function. At the end of the paper a conjecture is stated, which may be of interest for further research.

In a paper that initiated the modern study of the stochastic block model (SBM), Decelle, Krzakala, Moore, and Zdeborova, backed by Mossel, Neeman, and Sly, conjectured that detecting clusters in the symmetric SBM in polynomial time is always possible above the Kesten-Stigum (KS) threshold, while it is possible to detect clusters information theoretically (i.e., not necessarily in polynomial time) below the KS threshold when the number of clusters k is at least 4. Massoulie, Mossel et al., and Bordenave, Lelarge, and Massoulie proved that the KS threshold is in fact efficiently achievable for k = 2, while Mossel et al. proved that it cannot be crossed at k = 2. The above conjecture remained open for k ≥ 3. This paper proves the two parts of the conjecture, further extending the results to general SBMs. For the efficient part, an approximate acyclic belief propagation (ABP) algorithm is developed and proved to detect communities for any k down to the KS threshold in quasi-linear time. Achieving this requires showing optimality of ABP in the presence of cycles, a challenge for message-passing algorithms. The paper further connects ABP to a power iteration method on a nonbacktracking operator of generalized order, formalizing the interplay between message passing and spectral methods. For the information-theoretic part, a nonefficient algorithm sampling a typical clustering is shown to break down the KS threshold at k = 4. The emerging gap is shown to be large in some cases, making the SBM a good case study for information-computation gaps. © 2017 Wiley Periodicals, Inc.

The notion of a p-convergent operator on a Banach space was originally introduced in 1993 by Castillo and Sanchez in the paper entitled “Dunford–Pettis-like properties of continuous vector function spaces”. In the present paper we consider the p-convergent operators on Banach lattices, prove some domination properties of the same and consider their applications (together with the notion of a weak p-convergent operator, which we introduce in the present paper) to a study of the Schur property of order p. Also, the notion of a disjoint p-convergent operator on Banach lattices is introduced, studied and its applications to a study of the positive Schur property of order p are considered.

A map (S,G) is a closed Riemann surface S with embedded graph G such that S \G is the disjoint union of connected components, called faces, each of which is homeomorphic to an open disk. Tutte began a systematic study of maps in the 1960s and contemporary authors are actively developing it. In the present paper, after recalling the concept of a circular map introduced by the author and Mednykh, a relationship between bipartite maps and circular maps is demonstrated via the concept of the duality of maps. In this way an enumeration formula for the number of bipartite maps with a given number of edges is obtained. A hypermap is a map whose vertices are colored black and white in such a way that every edge connects vertices of different colors. The hypermaps are also known as dessins d’enfants (or Grothendieck’s dessins). A hypermap is self-equivalent with respect to reversing the colors of vertices if it is equivalent to the hypermap obtained by reversing the colors of its vertices. The main result of the present paper is an enumeration formula for the number of unrooted hypermaps, regardless of genus, which have n edges and are self-equivalent with respect to reversing the colors of vertices. Bibliography: 13 titles.

In this paper, the authors first construct a dynamical system which is strongly mixing but has no weak specification property. Then the authors introduce two new concepts which are called the quasi-weak specification property and the semi-weak specification property in this paper, respectively, and the authors prove the equivalence of quasi-weak specification property, semi-weak specification property and strongly mixing.

In 1874, Franz Mertens proved the so-called Mertens’ theorem, and in 1974, Kenneth S. Williams showed Mertens’ theorem associated with a character. In a previous paper, we presented a graph-theoretic analogue to Williams’ theorem. In this paper, we generalize our previous work in the sense that a character is extended to a representation. To our knowledge, a number-theoretic analogue to our result is not yet known. So, we expect that, by using our methods, it can be proven in the future.

The quadratic Vieta formulas (x, y) ↦ (u, v) = (x + y, xy) in the complex geometry define a two-fold branched covering ℂ2 → ℂ2 ramified over the parabola u 2 = 4v. Thinking about topics considered in Arnold’s paper Topological content of the Maxwell theorem on multipole representation of spherical functions, I came to a very simple idea: in fact, these formulas describe the algebraic structure, i.e., addition and multiplication, of complex numbers. What if, instead of the field of complex numbers, we consider an arbitrary ring? Namely for an arbitrary ring A (commutative, with unity) consider the mapping Φ: A 2 → A 2 defined by the Vieta formulas (x, y) ↦ (u, v) = (x + y, xy). What kind of algebraic properties of the ring itself does this map reflect? At first, it is interesting to investigate the simplest finite rings A = ℤ m and A = ℤ k ×ℤ m . Recently, it has been very popular to consider graphs associated to rings (the zero-divisor graph, the Cayley graph, etc.). In the present paper, we study the directed graph defined by the Vieta mapping Φ.

In this paper we develop the theory of anti-compact sets we introduced earlier. We describe the class of Frechet spaces where anti-compact sets exist. They are exactly the spaces that have a countable set of continuous linear functionals. In such spaces we prove an analogue of the Hahn–Banach theorem on extension of a continuous linear functional from the original space to a space generated by some anti-compact set. We obtain an analogue of the Lyapunov theorem on convexity and compactness of the range of vector measures, which establishes convexity and a special kind of relative weak compactness of the range of an atomless vector measure with values in a Frechet space possessing an anti-compact set. Using this analogue of the Lyapunov theorem, we prove the solvability of an infinite-dimensional analogue of the problem of fair division of resources. We also obtain an analogue of the Lyapunov theorem for nonadditive analogues of measures that are vector quasi-measures valued in an infinite-dimensional Frechet space possessing an anti-compact set. In the class of Frechet spaces possessing an anti-compact set, we obtain analogues of the Krein–Milman theorem on extreme points for convex bounded sets that are not necessarily compact. A special place is occupied by analogues of the Krein–Milman theorem in terms of extreme sequences introduced in the paper (the so-called sequential analogues of the Krein–Milman theorem).

The k-core, defined as the maximal subgraph of minimum degree at least k, of the random graph G(n,p) has been studied extensively. In a landmark paper Pittel, Wormald and Spencer [J Combin Theory Ser B 67 (1996), 111–151] determined the threshold dk for the appearance of an extensive k-core. The aim of the present paper is to describe how the k-core is “embedded” into the random graph in the following sense. Let k≥3 and fix d=np>dk. Colour each vertex that belongs to the k-core of G(n,p) in black and all remaining vertices in white. Here we derive a multi-type branching process that describes the local structure of this coloured random object as n tends to infinity. This generalises prior results on, e.g., the internal structure of the k-core. In the physics literature it was suggested to characterize the core by means of a message passing algorithm called Warning Propagation. Ibrahimi, Kanoria, Kraning and Montanari [Ann Appl Probab 25 (2015), 2743–2808] used this characterization to describe the 2-core of random hypergraphs. To derive our main result we use a similar approach. A key observation is that a bounded number of iterations of this algorithm is enough to give a good approximation of the k-core. Based on this the study of the k-core reduces to the analysis of Warning Propagation on a suitable Galton-Watson tree. © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 00, 000–000, 2017

The goal of this paper is to point out that the results obtained in the recent papers (Chen and Song in Nonlinear Anal 72:1895–1901, 2010; Chu in J Math Anal Appl 327:1041–1045, 2007; Chu et al. in Nonlinear Anal 59:1001–1011, 2004a, J. Math Anal Appl 289:666–672, 2004b) can be seriously strengthened in the sense that we can significantly relax the assumptions of the main results so that we still get the same conclusions. In order to do this first, we prove that for $$n \ge 3$$ any transformation which preserves the n-norm of any n vectors is automatically plus-minus linear. This will give a re-proof of the well-known Mazur–Ulam-type result that every n-isometry is automatically affine ( $$n \ge 2$$ ) which was proven in several papers, e.g. in Chu et al. (Nonlinear Anal 70:1068–1074, 2009). Second, following the work of Rassias and Semrl (Proc Am Math Soc 118:919–925, 1993), we provide the solution of a natural Aleksandrov-type problem in n-normed spaces, namely, we show that every surjective transformation which preserves the unit n-distance in both directions ( $$n\ge 2$$ ) is automatically an n-isometry.

The study of the global structure of ultrafilters on the natural numbers with respect to the quasi-orders of Rudin-Keisler and Rudin-Blass reducibility was initiated in the 1970s by Blass, Keisler, Kunen, and Rudin. In a 1973 paper Blass studied the special class of P-points under the quasi-ordering of Rudin-Keisler reducibility. He asked what partially ordered sets can be embedded into the P-points when the P-points are equipped with this ordering. This question is of most interest under some hypothesis that guarantees the existence of many P-points, such as Martin’s axiom for σ \sigma -centered posets. In his 1973 paper he showed under this assumption that both ω 1 {\omega }_{1} and the reals can be embedded. Analogous results were obtained later for the coarser notion of Tukey reducibility. We prove in this paper that Martin’s axiom for σ \sigma -centered posets implies that the Boolean algebra P ( ω ) / FIN \mathcal {P}(\omega ) / \operatorname {FIN} equipped with its natural partial order can be embedded into the P-points both under Rudin-Keisler and Tukey reducibility. Consequently, the continuum hypothesis implies that every partial order of size at most continuum embeds into the P-points under both notions of reducibility.

In this paper, we present some results on the complete convergence for arrays of rowwise negatively superadditive dependent (NSD, in short) random variables by using the Rosenthal-type maximal inequality, Kolmogorov exponential inequality and the truncation method. The results obtained in the paper extend the corresponding ones for weighted sums of negatively associated random variables with identical distribution to the case of arrays of rowwise NSD random variables without identical distribution.

A wide class of problems in combinatorics, computer science and physics can be described along the following lines. There are a large number of variables ranging over a finite domain that interact through constraints that each bind a few variables and either encourage or discourage certain value combinations. Examples include the $k$-SAT problem or the Ising model. Such models naturally induce a Gibbs measure on the set of assignments, which is characterised by its partition function. The present paper deals with the partition function of problems where the interactions between variables and constraints are induced by a sparse random (hyper)graph. According to physics predictions, a generic recipe called the "replica symmetric cavity method" yields the correct value of the partition function if the underlying model enjoys certain properties [Krzkala et al., PNAS 2007]. Guided by this conjecture, we prove general sufficient conditions for the success of the cavity method. The proofs are based on a "regularity lemma" for probability measures on sets of the form $\Omega^n$ for a finite $\Omega$ and a large $n$ that may be of independent interest., Comment: This version replaces version 1 and the RANDOM 2015 version of the paper, which contained critical errors affecting the main results

This paper is concerned with factors of independent and identically distributed processes on the $d$ -regular tree for $d\geq 3$ . We study the mutual information of values on two given vertices. If the vertices are neighbors (i.e. their distance is $1$ ), then a known inequality between the entropy of a vertex and the entropy of an edge provides an upper bound for the (normalized) mutual information. In this paper we obtain upper bounds for vertices at an arbitrary distance $k$ , of order $(d-1)^{-k/2}$ . Although these bounds are sharp, we also show that an interesting phenomenon occurs here: for any fixed process, the rate of mutual information decay is much faster, essentially of order $(d-1)^{-k}$ .

We study the approximation of compact linear operators defined over certain weighted tensor product Hilbert spaces. The information complexity is defined as the minimal number of arbitrary linear functionals needed to obtain an e -approximation for the d -variate problem which is fully determined in terms of the weights and univariate singular values. Exponential tractability means that the information complexity is bounded by a certain function that depends polynomially on d and logarithmically on e − 1 . The corresponding unweighted problem was studied in Hickernell et al. (2020) with many negative results for exponential tractability. The product weights studied in the present paper change the situation. Depending on the form of polynomial dependence on d and logarithmic dependence on e − 1 , we study exponential strong polynomial, exponential polynomial, exponential quasi-polynomial, and exponential ( s , t ) -weak tractability with max ( s , t ) ≥ 1 . For all these notions of exponential tractability, we establish necessary and sufficient conditions on weights and univariate singular values for which it is indeed possible to achieve the corresponding notion of exponential tractability. The case of exponential ( s , t ) -weak tractability with max ( s , t ) 1 is left for future study. The paper uses some general results obtained in Hickernell et al. (2020) and Kritzer and Woźniakowski (2019).

In this paper we apply a group action approach to the study of Erdős–Falconer-type problems in vector spaces over finite fields and use it to obtain non-trivial exponents for the distribution of simplices. We prove that there exists s 0 ⁢ ( d ) < d ${s_{0}(d) such that if E ⊂ 𝔽 q d ${E\subset{\mathbb{F}}_{q}^{d}}$ , d ≥ 2 ${d\geq 2}$ , with | E | ≥ C ⁢ q s 0 ${|E|\geq Cq^{s_{0}}}$ , then | T d d ⁢ ( E ) | ≥ C ′ ⁢ q ( d + 1 2 ) ${|T^{d}_{d}(E)|\geq C^{\prime}q^{d+1\choose 2}}$ , where T k d ⁢ ( E ) ${T^{d}_{k}(E)}$ denotes the set of congruence classes of k-dimensional simplices determined by k + 1 ${k+1}$ -tuples of points from E. Non-trivial exponents were previously obtained by Chapman, Erdogan, Hart, Iosevich and Koh [4] for T k d ⁢ ( E ) ${T^{d}_{k}(E)}$ with 2 ≤ k ≤ d - 1 ${2\leq k\leq d-1}$ . A non-trivial result for T 2 2 ⁢ ( E ) ${T^{2}_{2}(E)}$ in the plane was obtained by Bennett, Iosevich and Pakianathan [2]. These results are significantly generalized and improved in this paper. In particular, we establish the Wolff exponent 4 3 ${\frac{4}{3}}$ , previously established in [4] for the q ≡ 3 ⁢ mod ⁢ 4 ${q\equiv 3\textup{ mod }4}$ case to the case q ≡ 1 ⁢ mod ⁢ 4 ${q\equiv 1\textup{ mod }4}$ , and this results in a new sum-product type inequality. We also obtain non-trivial results for subsets of the sphere in 𝔽 q d ${{\mathbb{F}}_{q}^{d}}$ , where previous methods have yielded nothing. The key to our approach is a group action perspective which quickly leads to natural and effective formulae in the style of the classical Mattila integral from geometric measure theory.

In this paper, we study the uniqueness of difference-differential polynomials of entire functions $f$ and $g$ sharing one value with counting multiplicity. In this paper we extend and generalize the results of X. Y. Zhang, J. F. Chen and W. C. Lin [17] L. Kai, L. Xin-ling and C. Ting-bin [7] and many others [2, 16].

In this paper we study d -variate approximation for weighted Korobov spaces in the worst-case setting. The considered algorithms use finitely many evaluations of arbitrary linear functionals. We give matching necessary and sufficient conditions for some notions of tractability in terms of two weight parameters. Our result is an affirmative answer to a problem which is left open in a recent paper of Kritzer, Pillichshammer and Wo?niakowski.

The paper is devoted to the master thesis on “information theory” which was written by the author in 1956–57. The topic was suggested by his advisor A. A. Bobrov (a student of A. Ya. Khinchin and A. N. Kolmogorov), and the thesis was written under the influence of lectures by N. I. Gavrilov (a student of I. G. Petrovskii) on the qualitative theory of differential equations, which included the statement of Birkhoff’s theorem for ergodic dynamical systems. In the thesis, the author used the concept of Shannon entropy in the study of ergodic dynamical systems f(p, t) in a separable compact metric space R with an invariant measure μ (where μ(R) = 1) and introduced the notion of the (ϵ, T)-entropy of a system as a quantitative characteristic of the degree of mixing. In the work, not only partitions of R were considered, but also partitions of the interval (−∞,∞) into subintervals of length T > 0. In particular, f(p, T) was regarded as an automorphism S of X = R, and the (ϵ, T)-entropy is essentially the e-entropy of S. But, despite some “oversights” in the definition of the (ϵ, T)-entropy and many years that have passed, the author decided to publish the corresponding chapter of the thesis in connection with the following: 1) There is a number of papers that refer to this work in the explanation of the history of the concept of Kolmogorov’s entropy. 2) Recently, B. M. Gurevich obtained new results on the ϵ-entropy hϵ(S), which show that for two ergodic automorphisms with equal finite entropies their ϵ-entropies also coincide for all ϵ, but, on the other hand, there are unexpected nonergodic automorphisms with equal finite entropies, but different ϵ-entropies for some ϵ. This shows that the concept of ϵ-entropy is of scientific value.

The present paper is devoted to graph-links with many components and consists of two parts. In the first part of the paper we classify vertices of a labeled graph according to the component they belong to. Using this classification, we construct an invariant of graph-links. This invariant shows that the labeled second Bouchet graph generates a nonrealizable graph-link. In the second part of the work we introduce the notion of an oriented graph-link. We define a writhe number for the oriented graph-link and we get an invariant of oriented graph-links, the Jones polynomial, by normalizing the Kauffman bracket with the writhe number.

In this paper, we introduce and study an explicit hybrid re- laxed extragradient iterative method to approximate a common solution to generalized mixed equilibrium problem and fixed point problem for a nonexpansive semigroup in Hilbert space. Further, we prove that the sequence generated by the proposed iterative scheme converges strongly to the common solution to generalized mixed equilibrium problem and fixed point problem for a nonexpansive semigroup. This common solu- tion is the unique solution of a variational inequality problem and is the optimality condition for a minimization problem. The results presented in this paper are the supplement, improvement and generalization of the previously known results in this area.

In this paper, we study convergence of coupled dynamical systems on convergent sequences of graphs to a continuum limit. We show that the solutions of the initial value problem for the dynamical system on a convergent graph sequence tend to that for the nonlocal diffusion equation on a unit interval, as the graph size tends to infinity. We improve our earlier results in [Arch. Ration. Mech. Anal., 21 (2014), pp. 781--803] and extend them to a larger class of graphs, which includes directed and undirected, sparse and dense, random and deterministic graphs. There are three main ingredients of our approach. First, we employ a flexible framework for incorporating random graphs into the models of interacting dynamical systems, which fits seamlessly with the derivation of the continuum limit. Next, we prove the averaging principle for approximating a dynamical system on a random graph by its deterministic (averaged) counterpart. The proof covers systems on sparse graphs and yields almost sure convergence on time intervals of order $\log n,$ where $n$ is the number of vertices. Finally, a Galerkin scheme is developed to show convergence of the averaged model to the continuum limit. The analysis of this paper covers the Kuramoto model of coupled phase oscillators on a variety of graphs including sparse Erd\H{o}s-R{\' e}nyi, small-world, and power law graphs., Comment: To appear in Communications in Mathematical Sciences

In this paper, we study the joint Laplace transform and probability generating functions of two pairs of random variables: (1) the two-sided first-exit time and the number of claims by this time; (2) the two-sided smooth exit-recovery time and its associated number of claims. The joint transforms are expressed in terms of the so-called doubly-killed scale function that is defined in this paper. We also find explicit expressions for the joint density function of the two-sided first-exit time and the number of claims by this time. Numerical examples are presented for exponential claims.

This paper is concerned with problems in the context of the theoretical foundation of adaptive algorithms for the numerical treatment of operator equations. It is well-known that the analysis of such schemes naturally leads to function spaces of Besov type. But, especially when dealing with equations on non-smooth manifolds, the definition of these spaces is not straightforward. Nevertheless, motivated by applications, recently Besov-type spaces $$B^\alpha _{\Psi ,q}(L_p(\Gamma ))$$ on certain two-dimensional, patchwise smooth surfaces were defined and employed successfully. In the present paper, we extend this definition (based on wavelet expansions) to a quite general class of d-dimensional manifolds and investigate some analytical properties of the resulting quasi-Banach spaces. In particular, we prove that different prominent constructions of biorthogonal wavelet systems $$\Psi $$ on domains or manifolds $$\Gamma $$ which admit a decomposition into smooth patches actually generate the same Besov-type function spaces $$B^\alpha _{\Psi ,q}(L_p(\Gamma ))$$ , provided that their univariate ingredients possess a sufficiently large order of cancellation and regularity. For this purpose, a theory of almost diagonal matrices on related sequence spaces $$b^\alpha _{p,q}(\nabla )$$ of Besov type is developed.

In the game of cops and robber, the cops try to capture a robber moving on the vertices of the graph. The minimum number of cops required to win on a given graph G is called the cop number of G. The biggest open conjecture in this area is the one of Meyniel, which asserts that for some absolute constant C, the cop number of every connected graph G is at most C|VG|. In this paper, we show that Meyniel's conjecture holds asymptotically almost surely for the binomial random graph Gn,p, which improves upon existing results showing that asymptotically almost surely the cop number of Gn,p is Onlogn provided that pni¾?2+elogn for some e>0. We do this by first showing that the conjecture holds for a general class of graphs with some specific expansion-type properties. This will also be used in a separate paper on random d-regular graphs, where we show that the conjecture holds asymptotically almost surely when d=dni¾?3. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 396-421, 2016

In this paper, we study a class of nonlinear Schrodinger–Poisson systems with indefinite steep potential well: $$\begin{aligned} \left\{ \begin{array}{l@{\quad }l} -\Delta u+V_{\lambda }(x)u+K(x)\phi u=|u|^{p-2}u &{} \text { in }\mathbb {R}^{3},\\ -\Delta \phi =K\left( x\right) u^{2} &{} \ \text {in }\mathbb {R}^{3}, \end{array} \right. \end{aligned}$$ where $$30$$ and $$ K(x)\ge 0$$ for all $$x\in \mathbb {R}^{3}$$ . We require that $$a\in C( \mathbb {R}^{3}) $$ is nonnegative and has a potential well $$\Omega _{a}$$ , namely $$a(x)\equiv 0$$ for $$x\in \Omega _{a}$$ and $$a(x)>0$$ for $$x\in \mathbb {R}^{3}\setminus \overline{\Omega _{a}}$$ . Unlike most other papers on this problem, we allow that $$b\in C(\mathbb {R}^{3}) $$ is unbounded below and sign-changing. By introducing some new hypotheses on the potentials and applying the method of penalized functions, we obtain the existence of nontrivial solutions for $$\lambda $$ sufficiently large. Furthermore, the concentration behavior of the nontrivial solution is also described as $$\lambda \rightarrow \infty $$ .

A central tool in the study of systems of linear equations with integer coefficients is the Generalised von Neumann Theorem of Green and Tao. This theorem reduces the task of counting the weighted solutions of these equations to that of counting the weighted solutions for a particular family of forms, the Gowers norms $\Vert f \Vert_{U^{s+1}[N]}$ of the weight $f$. In this paper we consider systems of linear inequalities with real coefficients, and show that the number of solutions to such weighted diophantine inequalities may also be bounded by Gowers norms. Furthermore, we provide a necessary and sufficient condition for a system of real linear forms to be governed by Gowers norms in this way. We present applications to cancellation of the M\"{o}bius function over certain sequences. The machinery developed in this paper can be adapted to the case in which the weights are unbounded but suitably pseudorandom, with applications to counting the number of solutions to diophantine inequalities over the primes. Substantial extra difficulties occur in this setting, however, and we have prepared a separate paper on these issues., Comment: 75 pages. Reworked introduction based on referee comments. To appear in Algebra & Number Theory

We prove a sharp bound on the fifth moment of modular L-functions of fixed small weight, and large prime level., Comment: v1: 81 pages. v3: 65 pages. We have extracted some material which now appears in two shorter, stand-alone papers. The calculations of Kloosterman sums and Fourier coefficients of Eisenstein series are in one new paper, and the stationary phase results are in a new paper with Ian Petrow as an additional co-author. This version also implements minor corrections and improvements to exposition

We consider connectivity properties of certain i.i.d. random environments on i¾?d, where at each location some steps may not be available. Site percolation and oriented percolation are examples of such environments. In these models, one of the quantities most often studied is the random set of vertices that can be reached from the origin by following a connected path. More generally, for the models we consider, multiple different types of connectivity are of interest, including: the set of vertices that can be reached from the origin; the set of vertices from which the origin can be reached; the intersection of the two. As with percolation models, many of the models we consider admit, or are expected to admit phase transitions. Among the main results of the paper is a proof of the existence of phase transitions for some two-dimensional models that are non-monotone in their underlying parameter, and an improved bound on the critical value for oriented site percolation on the triangular lattice. The connectivity of the random directed graphs provides a foundation for understanding the asymptotic properties of random walks in these random environments, which we study in a second paper. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 45, 111-137, 2014

In this paper we consider the Gerber-Shiu penalty function in the compound binomial risk model with time-correlated claims. It is assumed that each main claim will induce a by-claim but the occurrence of the by-claim may be delayed with a certain probability. Formulas for the probability generating function of the penalty function are obtained, together with the expression for the penalty function with zero initial surplus. Then we show that the penalty function satisfies a defective renewal equation. When the claims follow geometric distributions, explicit expression for the Gerber-Shiu function is derived. Numerical example is provided to illustrate the application of the result discussed in the paper.

In this paper, for the purpose of measuring the non-self-centrality extent of non-selfcentered graphs, a novel eccentricity-based invariant, named as non-self-centrality number (NSC number for short), of a graph G is defined as follows: \(N\left( G \right) = \sum\nolimits_{{v_i}{v_j} \in V\left( G \right)} {|{e_i} - {e_j}|} \) where the summation goes over all the unordered pairs of vertices in G and ei is the eccentricity of vertex vi in G, whereas the invariant will be called third Zagreb eccentricity index if the summation only goes over the adjacent vertex pairs of graph G. In this paper, we determine the lower and upper bounds on N(G) and characterize the corresponding graphs at which the lower and upper bounds are attained. Finally we propose some attractive research topics for this new invariant of graphs.

In this paper we consider an isotropic variant of the BMO-type norm recently introduced (Bourgain, Brezis, and Mironescu, 2015). We prove that, when considering characteristic functions of sets, this norm is related to the perimeter. A byproduct of our analysis is a new characterization of the perimeter of sets in terms of this norm, independent of the theory of distributions. In this paper we consider an isotropic variant of the BMO-type norm recently introduced (Bourgain, Brezis, and Mironescu, 2015). We prove that, when considering characteristic functions of sets, this norm is related to the perimeter. A byproduct of our analysis is a new characterization of the perimeter of sets in terms of this norm, independent of the theory of distributions.

This paper presents a curvature-free version of the Log ( 2 k − 1 ) \text {Log}(2k-1) Theorem of Anderson, Canary, Culler, and Shalen [J. Differential Geometry 44 (1996), pp. 738–782]. It generalizes a result by Hou [J. Differential Geometry 57 (2001), no. 1, pp. 173–193] and its proof is rather straightforward once we know the work by Lim [Trans. Amer. Math. Soc. 360 (2008), no. 10, pp. 5089–5100] on volume entropy for graphs. As a byproduct we obtain a curvature-free version of the Collar Lemma in all dimensions.

Many papers study polynomial tractability for multivariate problems. Let n(@?,d) be the minimal number of information evaluations needed to reduce the initial error by a factor of @? for a multivariate problem defined on a space of d-variate functions. Here, the initial error is the minimal error that can be achieved without sampling the function. Polynomial tractability means that n(@?,d) is bounded by a polynomial in @?^-^1 and d and this holds for all (@?^-^1,d)@?[1,~)xN. In this paper we study generalized tractability by verifying when n(@?,d) can be bounded by a power of T(@?^-^1,d) for all (@?^-^1,d)@[email protected], where @W can be a proper subset of [1,~)xN. Here T is a tractability function, which is non-decreasing in both variables and grows slower than exponentially to infinity. In this article we consider the set @W=[1,~)x{1,2,...,d^*}@?[1,@?"0^-^1)xN for some d^*>=1 and @?"[email protected]?(0,1). We study linear tensor product problems for which we can compute arbitrary linear functionals as information evaluations. We present necessary and sufficient conditions on T such that generalized tractability holds for linear tensor product problems. We show a number of examples for which polynomial tractability does not hold but generalized tractability does.

A paradigm that was successfully applied in the study of both pure and algorithmic problems in graph theory can be colloquially summarized as stating that any graph is close to being the disjoint union of expanders. Our goal in this paper is to show that in several of the instantiations of the above approach, the quantitative bounds that were obtained are essentially best possible. Three examples of our results are the following: A classical result of Lipton, Rose and Tarjan from 1979 states that if F is a hereditary family of graphs and every graph in F has a vertex separator of size n/(log⁡n)1+o(1), then every graph in F has O(n) edges. We construct a hereditary family of graphs with vertex separators of size n/(log⁡n)1−o(1) such that not all graphs in the family have O(n) edges. Trevisan and Arora-Barak-Steurer have recently shown that given a graph G, one can remove only 1% of its edges to obtain a graph in which each connected component has good expansion properties. We show that in both of these decomposition results, the expansion properties they guarantee are essentially best possible, even when one is allowed to remove 99% of G's edges. Sudakov and the second author have recently shown that every graph with average degree d contains an n-vertex subgraph with average degree at least (1−o(1))d and vertex expansion 1/(log⁡n)1+o(1). We show that one cannot guarantee a better vertex expansion even if allowing the average degree to be O(1). The above results are obtained as corollaries of a new family of graphs which we construct in this paper. These graphs have a super-linear number of edges and nearly logarithmic girth, yet each of their subgraphs has (optimally) poor expansion properties.

Szemeredi's Regularity Lemma is a well-known and powerful tool in modern graph theory. This result led to a number of interesting applications, particularly in extremal graph theory. A regularity lemma for 3-uniform hypergraphs developed by Frankl and Rodl [8] allows some of the Szemeredi Regularity Lemma graph applications to be extended to hypergraphs. An important development regarding Szemeredi's Lemma showed the equivalence between the property of e-regularity of a bipartite graph G and an easily verifiable property concerning the neighborhoods of its vertices (Alon et al. [1]; cf. [6]). This characterization of e-regularity led to an algorithmic version of Szemeredi's lemma [1]. Similar problems were also considered for hypergraphs. In [2], [9], [13], and [18], various descriptions of quasi-randomness of k-uniform hypergraphs were given. As in [1], the goal of this paper is to find easily verifiable conditions for the hypergraph regularity provided by [8]. The hypergraph regularity of [8] renders quasi-random "blocks of hyperedges" which are very sparse. This situation leads to technical difficulties in its application. Moreover, as we show in this paper, some easily verifiable conditions analogous to those considered in [2] and [18] fail to be true in the setting of [8]. However, we are able to find some necessary and sufficient conditions for this hypergraph regularity. These conditions enable us to design an algorithmic version of a hypergraph regularity lemma in [8]. This algorithmic version is presented by the authors in [5].

Data erasure can often occur in communication. Guarding against erasures involves redundancy in data representation. Mathematically this may be achieved by redundancy through the use of frames. One way to measure the robustness of a frame against erasures is to examine the worst case condition number of the frame with a certain number of vectors erased from the frame. The term numerically erasure-robust frames was introduced in Fickus and Mixon (Linear Algebra Appl 437:1394–1407, 2012) to give a more precise characterization of erasure robustness of frames. In the paper the authors established that random frames whose entries are drawn independently from the standard normal distribution can be robust against up to approximately 15 % erasures, and asked whether there exist frames that are robust against erasures of more than 50 %. In this paper we show that with very high probability random frames are, independent of the dimension, robust against erasures as long as the number of remaining vectors is at least \(1+\delta _0\) times the dimension for some \(\delta _0>0\). This is the best possible result, and it also implies that the proportion of erasures can be arbitrarily close to 1 while still maintaining robustness. Our result depends crucially on a new estimate for the smallest singular value of a rectangular random matrix with independent standard normal entries.

We study approximation of multivariate functions defined over Rd. We assume that all rth order partial derivatives of the functions considered are continuous and uniformly bounded. Approximation algorithms U(f) only use the values of f or its partial derivatives up to order r. We want to recover the function f with small error measured in a weighted Lq norm with a weight function ρ. We study the worst case (information) complexity which is equal to the minimal number of function and derivative evaluations needed to obtain error ε. We provide necessary and sufficient conditions in terms of the weight ρ and the parameters q and r for the weighted approximation problem to have finite complexity. We also provide conditions guaranteeing that the complexity is of the same order as the complexity of the classical approximation problem over a finite domain. Since the complexity of the weighted integration problem is equivalent to the complexity of the weighted approximation problem with q=1, the results of this paper also hold for weighted integration. This paper is a continuation of [7], where weighted approximation over R was studied.

We consider the problem of approximating fixed points of contractive functions whose contraction factor is close to 1. In a previous paper (1993, K. Sikorski et al. , J. Complexity 9 , 181–200), we proved that for the absolute error criterion, the upper bound on the number of function evaluations to compute e -approximations is O( n 3 (ln(1/ e )+ln(1/(1− q ))+ln n )) in the worst case, where 0 q n is the dimension of the problem. This upper bound is achieved by the circumscribed ellipsoid (CE) algorithm combined with a dimensional deflation process. In this paper we present an inscribed ellipsoid (IE) algorithm that enjoys O( n (ln(1/ e )+ln(1/(1− q )))) bound. For q close to 1, the IE algorithm thus runs in many fewer iterations than the simple iteration method, that requires ⌈ln(1/ e )/ln(1/ q )⌉ function evaluations. Our analysis also implies that: (1) The dimensional deflation procedure in the CE algorithm is not necessary and that the resulting “plain” CE algorithm enjoys O( n 2 (log(1/ e )+log(1/(1− q )))) upper bound on the number of function evaluations. (2) The IE algorithm solves the problem in the residual sense, i.e., computes x such that ‖ f ( x )− x ‖⩽ δ , with O( n ln(1/ δ )) function evaluations for every q ⩽1.

In this paper we present several natural q-analogues of the poly-Bernoulli numbers arising in combinatorial contexts. We also recall some related analytical results and ask for combinatorial interpretations.

The purpose of this paper is to study the relationships between the support of a refinable distributionφand the global and local linear independence of the integer translates ofφ. It has been shown elsewhere that a compactly supported distributionφhas globally independent integer translates if and only ifφhas minimal convex support. However, such a distribution may have “holes” in its support. By insisting thatφ∈L2(R) and generates a multiresolution analysis, Lemarié and Malgouyres have ensured that no such holes can occur. In this article we generalize this result to refinable distributions. We also give a result on the local linear independence of the integer translates ofφ. We work with integer dilation factorN⩾2 throughout this paper.

In a recent paper, the authors proved that, under natural assumptions on the first marginal, the Monge problem in $ {\mathbb{R}^d} $ for the cost given by a general norm admits a solution. Although the basic idea of the proof is simple, it involves some complex technical results. Here we will give a proof of the result in the simpler case of a uniformly convex norm, and we will also use very recent results by Ahmad, Kim, and McCann. This allows us to reduce the technical burdens while still giving the main ideas of the general proof. The proof of the density of the transport set in the particular case considered in this paper is original. Bibliography: 22 titles.