Search

In this paper author was proved the boundedness of the multidimensional Hardy type operator in weighted Lebesgue spaces with a variable exponent. As an application we prove the boundedness of certain sublinear operators on the weighted variable Lebesgue space. Note that the proof of multidimensional Hardy type operator in weighted Lebesgue spaces with a variable exponent don't contained any mistakes. But at the proving of the boundedness of certain sublinear operators on the weighted variable Lebesgue space Georgian colleagues discovered a small but significant error in this paper. This result is assigned as Theorem 5 in noted paper. In other words, sufficient conditions for general weights ensuring the validity of the two-weight strong type inequalities for some sublinear operator was found. In this theorem the inequality (9) isn't true. In this note we give the details of the correct argument. We presume that the reader is familiar with the contents and notation of our original paper. At the heart of our correction is the following Theorem which replaces Theorem 5.

These are detailed notes on Perelman's papers "The entropy formula for the Ricci flow and its geometric applications" and "Ricci flow with surgery on three-manifolds"., 216 pages, minor corrections made

This survey is a slightly extended version of the lecture given by the author at the \emph{VI International Course of Mathematical Analysis in Andaluc\'\i a} (CIDAMA), in September 2014. Most results are contained (in a slightly less general setting) in the earlier paper [3] (Garrig\'os, Hartzstein, Signes, Torrea and Viviani, Pointwise convergence to initial data of heat and Laplace equations, Trans. Amer. Math. Soc. 368 (9) (2016), 6575-6600)., Comment: 17 pages. This is a preprint version of survey paper published in Advanced courses of mathematical analysis VI, 153-171, World Sci. Publ., Hackensack, NJ, 2017

The classical global criteria for the existence of Hamilton cycles only apply to graphs with large edge density and small diameter. In a series of papers Asratian and Khachatryan developed local criteria for the existence of Hamilton cycles in finite connected graphs, which are analogues of the classical global criteria due to Dirac (1952), Ore (1960), Jung (1978), and Nash-Williams (1971). The idea was to show that the global concept of Hamiltonicity can, under rather general conditions, be captured by local phenomena, using the structure of balls of small radii. (The ball of radius $r$ centered at a vertex $u$ is a subgraph of $G$ induced by the set of vertices whose distances from $u$ do not exceed $r$.) Such results are called localization theorems and present a possibility to extend known classes of finite Hamiltonian graphs. In this paper we formulate a general approach for finding localization theorems and use this approach to formulate local analogues of well-known results of Bauer et al. (1989), Bondy (1980), H\"aggkvist and Nicoghossian (1981), and Moon and Moser (1963). Finally we extend two of our results to infinite locally finite graphs and show that they guarantee the existence of Hamiltonian curves, introduced by K\"undgen, Li and Thomassen (2017)., Comment: 25 pages, 3 figures

This paper is a contribution to frame theory. Frames in a Hilbert space are generalizations of orthonormal bases. In particular, Gabor frames of $L^2(\mathbb{R})$, which are made of translations and modulations of one or more windows, are often used in applications. More precisely, the paper deals with a question posed in the last years by Christensen and Hasannasab about the existence of overcomplete Gabor frames, with some ordering over $\mathbb{Z}$, which are orbits of bounded operators on $L^2(\mathbb{R})$. Two classes of overcomplete Gabor frames which cannot be ordered over $\mathbb{Z}$ and represented by orbits of operators in $GL(L^2(\mathbb{R}))$ are given. Some results about operator representation are stated in a general context for arbitrary frames, covering also certain wavelet frames., Comment: 12 pages

We prove a new effective Chebotarev density theorem for Galois extensions $L/\mathbb{Q}$ that allows one to count small primes (even as small as an arbitrarily small power of the discriminant of $L$); this theorem holds for the Galois closures of "almost all" number fields that lie in an appropriate family of field extensions. Previously, applying Chebotarev in such small ranges required assuming the Generalized Riemann Hypothesis. The error term in this new Chebotarev density theorem also avoids the effect of an exceptional zero of the Dedekind zeta function of $L$, without assuming GRH. We give many different "appropriate families," including families of arbitrarily large degree. To do this, we first prove a new effective Chebotarev density theorem that requires a zero-free region of the Dedekind zeta function. Then we prove that almost all number fields in our families yield such a zero-free region. The innovation that allows us to achieve this is a delicate new method for controlling zeroes of certain families of non-cuspidal $L$-functions. This builds on, and greatly generalizes the applicability of, work of Kowalski and Michel on the average density of zeroes of a family of cuspidal $L$-functions. A surprising feature of this new method, which we expect will have independent interest, is that we control the number of zeroes in the family of $L$-functions by bounding the number of certain associated fields with fixed discriminant. As an application of the new Chebotarev density theorem, we prove the first nontrivial upper bounds for $\ell$-torsion in class groups, for all integers $\ell \geq 1$, applicable to infinite families of fields of arbitrarily large degree., Comment: 52 pages. This shorter version aligns with the published paper. Note that portions of Section 8 of the longer v1 have been developed as a separate paper with identifier arXiv:1902.02008

In this paper we consider Susceptible \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\rightarrow $$\end{document}→ Infectious \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\rightarrow $$\end{document}→ Recovered (SIR) epidemics on random graphs with clustering. To incorporate group structure of the underlying social network, we use a generalized version of the configuration model in which each node is a member of a specified number of triangles. SIR epidemics on this type of graph have earlier been investigated under the assumption of homogeneous infectivity and also under the assumption of Poisson transmission and recovery rates. We extend known results from literature by relaxing the assumption of homogeneous infectivity both in individual infectivity and between different kinds of neighbours. An important special case of the epidemic model analysed in this paper is epidemics in continuous time with arbitrary infectious period distribution. We use branching process approximations of the spread of the disease to provide expressions for the basic reproduction number \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$R_0$$\end{document}R0, the probability of a major outbreak and the expected final size. In addition, the impact of random vaccination with a perfect vaccine on the final outcome of the epidemic is investigated. We find that, for this particular model, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$R_0$$\end{document}R0 equals the perfect vaccine-associated reproduction number. Generalizations to groups larger than three are discussed briefly.

An equiangular tight frame (ETF) is a type of optimal packing of lines in a real or complex Hilbert space. In the complex case, the existence of an ETF of a given size remains an open problem in many cases. In this paper, we observe that many of the known constructions of ETFs are of one of two types. We further provide a new method for combining a given ETF of one of these two types with an appropriate group divisible design (GDD) in order to produce a larger ETF of the same type. By applying this method to known families of ETFs and GDDs, we obtain several new infinite families of ETFs. The real instances of these ETFs correspond to several new infinite families of strongly regular graphs. Our approach was inspired by a seminal paper of Davis and Jedwab which both unified and generalized McFarland and Spence difference sets. We provide combinatorial analogs of their algebraic results, unifying Steiner ETFs with hyperoval ETFs and Tremain ETFs.

This paper concerns the Vertex Reinforced Jump Process (VRJP) and its representations as a Markov process in random environment. In [21], it was shown that the VRJP on finite graphs, under a certain time rescaling, has the distribution of a mixture of Markov jump processes. This representation was extended to infinite graphs in [23], by introducing a random potential $\beta $. In this paper, we show that all possible representations of the VRJP as a mixture of Markov processes can be expressed in a similar form as in [23], using the random field $\beta $ and harmonic functions for an associated operator $H_\beta $. This allows to show that the VRJP on $\mathbb {Z}^{d}$ (with certain initial conditions) has a unique representation, by proving that an associated Martin boundary is trivial. Moreover, on infinite trees, we construct a family of representations, that are all different when the VRJP is transient and the tree is $d$-regular (with $d\geq 3$).

In the recent paper [Jin, Kolda & Ward, arXiv:1909.04801], it is proved that the Kronecker fast Johnson-Lindenstrauss transform (KFJLT) is, in fact, a Johnson-Lindenstrauss transform, which had previously only been conjectured. In this paper, we provide an alternative proof of this, for when the KFJLT is applied to Kronecker vectors, using a coherence and sampling argument. Our proof yields a different bound on the embedding dimension, which can be combined with the bound in the paper by Jin et al. to get a better bound overall. As a stepping stone to proving our result, we also show that the KFJLT is a subspace embedding for matrices with columns that have Kronecker product structure. Lastly, we compare the KFJLT to four other sketch techniques in numerical experiments on both synthetic and real-world data., Accepted to Linear Algebra and its Applications

In the authors' first paper, Beurling-Rudin-Korenbljum type characterization of the closed ideals in a certain algebra of holomorphic functions was used to describe the lattice of invariant subspaces of the shift plus a complex Volterra operator. Current work is an extension of the previous work and it describes the lattice of invariant subspaces of the shift plus a positive integer multiple of the complex Volterra operator on the Hardy space. Our work was motivated by a paper by Ong who studied the real version of the same operator., We deleted a proposition and a corollary from section 4, and simplified the proof of the main theorem. **The article has been published in Archiv der Mathematik**

We consider the problem of computing an approximate banded solution of the continuous-time Lyapunov equation $\underline{A}\underline{X}+\underline{X}\underline{A}^{T}=\underline{P}$, where the coefficient matrices $\underline{A}$ and $\underline{P}$ are large, symmetric banded matrices. The (sparsity) pattern of $\underline{A}$ describes the interconnection structure of a large-scale interconnected system. Recently, it has been shown that the entries of the solution $\underline{X}$ are spatially localized or decaying away from a banded pattern. We show that the decay of the entries of $\underline{X}$ is faster if the condition number of $\underline{A}$ is smaller. By exploiting the decay of entries of $\underline{X}$, we develop two computationally efficient methods for approximating $\underline{X}$ by a banded matrix. For a well-conditioned and sparse banded $\underline{A}$, the computational and memory complexities of the methods scale linearly with the state dimension. We perform extensive numerical experiments that confirm this, and that demonstrate the effectiveness of the developed methods. The methods proposed in this paper can be generalized to (sparsity) patterns of $\underline{A}$ and $\underline{P}$ that are more general than banded matrices. The results of this paper open the possibility for developing computationally efficient methods for approximating the solution of the large-scale Riccati equation by a sparse matrix., Accepted in Automatica, Final version, 16 pages, 10 figures

In a recent work of Duke, Imamo\={g}lu, and T\'{o}th, the linking number of certain links on the space $\text{SL}(2,\mathbb{Z})\backslash\text{SL}(2,\mathbb{R})$ is investigated. This linking number has an alternative interpretation as the intersection number of closed geodesics on the modular curve, which is the focus of this paper. By relating the intersection number to a combinatorial computation involving rivers of Conway topographs, an efficient algorithm for computing intersection numbers is produced. A formula for the total intersection of a pair of positive coprime fundamental discriminants is also derived, which can be thought of as a real quadratic analogue of a classical result of Gross and Zagier. The paper ends with numerical computations and distribution questions relating to intersection numbers., Comment: 28 pages. Updated formatting to be consistent with my other papers, and added a few errata

In a series of recent papers (Adcock, Hansen and Poon, 2013, Appl. Comput. Harm. Anal. 45(5):3132-3167), (Adcock, Gataric and Hansen, 2014, SIAM J. Imaging Sci. 7(3):1690-1723) and (Adcock, Hansen, Kutyniok and Ma, 2015, SIAM J. Math. Anal. 47(2):1196-1233), it was shown that one can optimally recover the wavelet coefficients of an unknown compactly supported function from pointwise evaluations of its Fourier transform via the method of generalized sampling. While these papers focused on the optimality of generalized sampling in terms of its stability and error bounds, the current paper explains how this optimal method can be implemented to yield a computationally efficient algorithm. In particular, we show that generalized sampling has a computational complexity of $\mathcal{O}(M(N)\log N)$ when recovering the first $N$ boundary-corrected wavelet coefficients of an unknown compactly supported function from $M(N)$ Fourier samples. Therefore, due to the linear correspondences between the number of samples $M$ and number of coefficients $N$ shown previously, generalized sampling offers a computationally optimal way of recovering wavelet coefficients from Fourier data.

A facial unique-maximum coloring of a plane graph is a proper coloring of the vertices using positive integers such that each face has a unique vertex that receives the maximum color in that face. Fabrici and G\"{o}ring (2016) proposed a strengthening of the Four Color Theorem conjecturing that all plane graphs have a facial unique-maximum coloring using four colors. This conjecture has been disproven for general plane graphs and it was shown that five colors suffice. In this paper we show that plane graphs, where vertices of degree at least four induce a star forest, are facially unique-maximum 4-colorable. This improves a previous result for subcubic plane graphs by Andova, Lidick\'y, Lu\v{z}ar, and \v{S}krekovski (2018). We conclude the paper by proposing some problems., Comment: 8 pages, 5 figures

This paper introduces a new class of Dynkin games, where the two players are allowed to make their stopping decisions at a sequence of exogenous Poisson arrival times. The value function and the associated optimal stopping strategy are characterized by the solution of a backward stochastic differential equation. The paper further provides a replication strategy for the game and applies the model to study the optimal conversion and calling strategies of convertible bonds, and their asymptotics when the Poisson intensity goes to infinity.\ud \ud \ud

In this paper, we use the theory of Riordan matrices to introduce the notion of a Riordan graph. The Riordan graphs are a far-reaching generalization of the well known and well studied Pascal graphs and Toeplitz graphs, and also some other families of graphs. The Riordan graphs are proved to have a number of interesting (fractal) properties, which can be useful in creating computer networks with certain desirable features, or in obtaining useful information when designing algorithms to compute values of graph invariants. The main focus in this paper is the study of structural properties of families of Riordan graphs obtained from infinite Riordan graphs, which includes a fundamental decomposition theorem and certain conditions on Riordan graphs to have an Eulerian trail/cycle or a Hamiltonian cycle. We will study spectral properties of the Riordan graphs in a follow up paper., 45 pages, 12 figures

This paper addresses the sharpness of a weighted $L^{2}$-estimate for the Fourier extension operator associated to the circle, obtained by J. Bennett, A. Carbery, F. Soria and A. Vargas in 2006. A point left open in their paper was the necessity of a certain $\log R$-factor in the bound. Here, I show that the factor is necessary for all $1/2$-Ahlfors-David regular weights on the circle, but it can be removed for $s$-Ahlfors-David regular weights with $s \neq 1/2$., 12 pages

In this paper we investigate quasi-Monte Carlo (QMC) integration using digital nets over Z b in reproducing kernel Hilbert spaces. The tent transformation (previously called baker’s transform) was originally used for lattice rules by Hickernell (2002) to achieve higher order convergence of the integration error for smooth non-periodic integrands, and later, has been successfully applied to digital nets over Z 2 by Cristea et al. (2007) and Goda (2015). The aim of this paper is to generalize the latter two results to digital nets over Z b for an arbitrary prime b . For this purpose, we introduce the b -adic tent transformation for an arbitrary positive integer b greater than 1, which is a generalization of the original (dyadic) tent transformation. Further, again for an arbitrary positive integer b greater than 1, we analyze the mean square worst-case error of QMC rules using digital nets over Z b which are randomly digitally shifted and then folded using the b -adic tent transformation in reproducing kernel Hilbert spaces. Using this result, for a prime b , we prove the existence of good higher order polynomial lattice rules over Z b among a smaller number of candidates as compared to the result by Dick and Pillichshammer (2007), which achieve almost the optimal convergence rate of the mean square worst-case error in unanchored Sobolev spaces of smoothness of arbitrary high order.

Quasi-Monte Carlo (QMC) rules are equal weight quadrature rules for approximating integrals over the s-dimensional unit cube [0, 1]s. One line of research studies the integration error of functions in the unit ball of so-called Korobov spaces, which are Hilbert spaces of periodic functions on [0, 1]s with square integrable partial mixed derivatives of order ?. Using Parseval's identity, this smoothness can be defined for all real numbers ? > 1/2. In this setting, the condition ? > 1/2 is necessary as otherwise the Korobov space contains discontinuous functions for which function evaluation is not well defined. This paper is concerned with more precise endpoint estimates of the integration error using QMC rules for Korobov spaces with ? arbitrarily close to 1/2. To obtain such estimates we introduce a log-scale for function spaces with smoothness close to 1/2, which we call log-Korobov spaces. We show that lattice rules can be used to obtain an integration error of order ??(N?1/2(logN)?μ(1??)/2)$\mathcal {O}(N^{-1/2} (\log N)^{-\mu (1-\lambda )/2})$ for any 1/μ 1 is a certain power in the log-scale. A second result is concerned with tractability of numerical integration for weighted Korobov spaces with product weights (?j)j??$(\gamma _{j})_{j \in \mathbb {N}}$. Previous results have shown that if ?j=1??j?${\sum }_{j=1}^{\infty } \gamma _{j}^{\tau } < \infty $ for some 1/(2?)

In this paper we fix 7 types of undirected graphs: paths, paths with prescribed endvertices, circuits, forests, spanning trees, (not necessarily spanning) trees and cuts. Given an undirected graph $G=(V,E)$ and two "object types" $\mathrm{A}$ and $\mathrm{B}$ chosen from the alternatives above, we consider the following questions. \textbf{Packing problem:} can we find an object of type $\mathrm{A}$ and one of type $\mathrm{B}$ in the edge set $E$ of $G$, so that they are edge-disjoint? \textbf{Partitioning problem:} can we partition $E$ into an object of type $\mathrm{A}$ and one of type $\mathrm{B}$? \textbf{Covering problem:} can we cover $E$ with an object of type $\mathrm{A}$, and an object of type $\mathrm{B}$? This framework includes 44 natural graph theoretic questions. Some of these problems were well-known before, for example covering the edge-set of a graph with two spanning trees, or finding an $s$-$t$ path $P$ and an $s'$-$t'$ path $P'$ that are edge-disjoint. However, many others were not, for example can we find an $s$-$t$ path $P\subseteq E $ and a spanning tree $T\subseteq E$ that are edge-disjoint? Most of these previously unknown problems turned out to be NP-complete, many of them even in planar graphs. This paper determines the status of these 44 problems. For the NP-complete problems we also investigate the planar version, for the polynomial problems we consider the matroidal generalization (wherever this makes sense).

In this paper, we further investigate the problem of commutativity up to a factor (or $\lambda$-commutativity) in the setting of bounded and unbounded linear operators in a complex Hilbert space. The results are based on a new approach to the problem. We finish the paper by a conjecture on the commutativity of self-adjoint operators., Comment: 08 pages (to appear in Journal of Mathematical Analysis and Applications, Elsevier)

This paper focuses on the problem of modeling for small world effect on complex networks. Let's consider the supercritical Poisson continuous percolation on $d$-dimensional torus $T^d_n$ with volume $n^d$. By adding "long edges (short cuts)" randomly to the largest percolation cluster, we obtain a random graph $\mathscr G_n$. In the present paper, we first prove that the diameter of $\mathscr G_n$ grows at most polynomially fast in $\ln n$ and we call it the Poisson Geometry Small World. Secondly, we prove that the random walk on $\mathscr G_n$ possesses the rapid mixing property, namely, the random walk mixes in time at most polynomially large in $\ln n$., 23 pages

This paper considers the non-Hermitian Zakharov-Shabat (ZS) scattering problem which forms the basis for defining the SU$(2)$-nonlinear Fourier transformation (NFT). The theoretical underpinnings of this generalization of the conventional Fourier transformation is quite well established in the Ablowitz-Kaup-Newell-Segur (AKNS) formalism; however, efficient numerical algorithms that could be employed in practical applications are still unavailable. In this paper, we present a unified framework for the forward and inverse NFT using exponential one-step methods which are amenable to FFT-based fast polynomial arithmetic. Within this discrete framework, we propose a fast Darboux transformation (FDT) algorithm having an operational complexity of $\mathscr{O}\left(KN+N\log^2N\right)$ such that the error in the computed $N$-samples of the $K$-soliton vanishes as $\mathscr{O}\left(N^{-p}\right)$ where $p$ is the order of convergence of the underlying one-step method. For fixed $N$, this algorithm outperforms the the classical DT (CDT) algorithm which has a complexity of $\mathscr{O}\left(K^2N\right)$. We further present extension of these algorithms to the general version of DT which allows one to add solitons to arbitrary profiles that are admissible as scattering potentials in the ZS-problem. The general CDT/FDT algorithms have the same operational complexity as that of the $K$-soliton case and the order of convergence matches that of the underlying one-step method. A comparative study of these algorithms is presented through exhaustive numerical tests., Comment: Some typos have been corrected, figures have been updated and minor changes have been made in order to address the concerns of the referees

In this paper we study in detail a family of continued fraction expansions of any number in the unit closed interval $[0,1]$ whose digits are differences of consecutive non-positive integer powers of an integer $m \geq 2$. For the transformation which generates this expansion and its invariant measure, the Perron-Frobenius operator is given and studied. For this expansion, we apply the method of random systems with complete connections by Iosifescu and obtained the solution of its Gauss-Kuzmin type problem., Comment: This paper has been withdrawn by the author due to a change of the team of authors

Let $\Omega$ be either $\mathbb{R}^n$ or a strongly Lipschitz domain of $\mathbb{R}^n$, and $\omega\in A_{\infty}(\mathbb{R}^n)$ (the class of Muckenhoupt weights). Let $L$ be a second order divergence form elliptic operator on $L^2 (\Omega)$ with the Dirichlet or Neumann boundary condition, and assume that the heat semigroup generated by $L$ has the Gaussian property $(G_1)$ with the regularity of their kernels measured by $\mu\in(0,1]$. Let $\Phi$ be a continuous, strictly increasing, subadditive, positive and concave function on $(0,\infty)$ of critical lower type index $p_{\Phi}^-\in(0,1]$. In this paper, the authors introduce the "geometrical" weighted local Orlicz-Hardy spaces $h^{\Phi}_{\omega,\,r}(\Omega)$ and $h^{\Phi}_{\omega,\,z}(\Omega)$ via the weighted local Orlicz-Hardy spaces $h^{\Phi}_{\omega}(\mathbb{R}^n)$, and obtain their two equivalent characterizations in terms of the nontangential maximal function and the Lusin area function associated with the heat semigroup generated by $L$ when $p_{\Phi}^-\in(n/(n+\mu),1]$. As applications, the authors prove that the operators $\nabla^2{\mathbb G}_D$ are bounded from $h^{\Phi}_{\omega,\,r}(\Omega)$ to the weighted Orlicz space $L^{\Phi}_{\omega}(\Omega)$, and from $h^{\Phi}_{\omega,\,r}(\Omega)$ to itself when $\Omega$ is a bounded semiconvex domain in $\mathbb{R}^n$ and $p_{\Phi}^-\in(\frac{n}{n+1},1]$, and the operators $\nabla^2{\mathbb G}_N$ are bounded from $h^{\Phi}_{\omega,\,z}(\Omega)$ to $L^{\Phi}_{\omega}(\Omega)$, and from $h^{\Phi}_{\omega,\,z}(\Omega)$ to $h^{\Phi}_{\omega,\,r}(\Omega)$ when $\Omega$ is a bounded convex domain in $\mathbb{R}^n$ and $p_{\Phi}^-\in(\frac{n}{n+1},1]$, where ${\mathbb G}_D$ and ${\mathbb G}_N$ denote, respectively, the Dirichlet Green operator and the Neumann Green operator., Comment: This paper has been withdrawn by the authors

The total domination number of a graph $G$ without isolated vertices is the minimum number of vertices that dominate all vertices in $G$. The total bondage number $b_t(G)$ of $G$ is the minimum number of edges whose removal enlarges the total domination number. This paper considers grid graphs. An $(n,m)$-grid graph $G_{n,m}$ is defined as the cartesian product of two paths $P_n$ and $P_m$. This paper determines the exact values of $b_t(G_{n,2})$ and $b_t(G_{n,3})$, and establishes some upper bounds of $b_t(G_{n,4})$., Comment: 15 pages with 4 figures

In a recent paper Velleman and Warrington analyzed the expected values of some of the parameters in a memory game, namely, the length of the game, the waiting time for the first match, and the number of lucky moves. In this paper we continue this direction of investigation and obtain the limiting distributions of those parameters. More specifically, we prove that when suitably normalized, these quantities converge in distribution to a normal, Rayleigh, and Poisson random variable, respectively. We also make a connection between the memory game and one of the models of preferential attachment graphs. In particular, as a by--product of our methods we obtain simpler proofs (although without rate of convergence) of some of the results of Pek\"oz, R\"ollin, and Ross on the joint limiting distributions of the degrees of the first few vertices in preferential attachment graphs. For proving that the length of the game is asymptotically normal, our main technical tool is a limit result for the joint distribution of the number of balls in a multi--type generalized P\'olya urn model., Comment: 24 pages, 1 figure

We introduce semaphore codes associated to a Turing machine via resets. Semaphore codes provide an approximation theory for resets. In this paper we generalize the set-up of our previous paper "Random walks on semaphore codes and delay de Bruijn semigroups" to the infinite case by taking the profinite limit of $k$-resets to obtain $(-\omega)$-resets. We mention how this opens new avenues to attack the P versus NP problem., Comment: 28 pages; Sections 3-6 appeared in a previous version of arXiv:1509.03383 as Sections 9-12 (the split of the previous paper was suggested by the journal); Sections 1-2 and 7 are new

An $(n, k)$-Poisson Multinomial Distribution (PMD) is a random variable of the form $X = \sum_{i=1}^n X_i$, where the $X_i$'s are independent random vectors supported on the set of standard basis vectors in $\mathbb{R}^k.$ In this paper, we obtain a refined structural understanding of PMDs by analyzing their Fourier transform. As our core structural result, we prove that the Fourier transform of PMDs is {\em approximately sparse}, i.e., roughly speaking, its $L_1$-norm is small outside a small set. By building on this result, we obtain the following applications: {\bf Learning Theory.} We design the first computationally efficient learning algorithm for PMDs with respect to the total variation distance. Our algorithm learns an arbitrary $(n, k)$-PMD within variation distance $\epsilon$ using a near-optimal sample size of $\widetilde{O}_k(1/\epsilon^2),$ and runs in time $\widetilde{O}_k(1/\epsilon^2) \cdot \log n.$ Previously, no algorithm with a $\mathrm{poly}(1/\epsilon)$ runtime was known, even for $k=3.$ {\bf Game Theory.} We give the first efficient polynomial-time approximation scheme (EPTAS) for computing Nash equilibria in anonymous games. For normalized anonymous games with $n$ players and $k$ strategies, our algorithm computes a well-supported $\epsilon$-Nash equilibrium in time $n^{O(k^3)} \cdot (k/\epsilon)^{O(k^3\log(k/\epsilon)/\log\log(k/\epsilon))^{k-1}}.$ The best previous algorithm for this problem had running time $n^{(f(k)/\epsilon)^k},$ where $f(k) = \Omega(k^{k^2})$, for any $k>2.$ {\bf Statistics.} We prove a multivariate central limit theorem (CLT) that relates an arbitrary PMD to a discretized multivariate Gaussian with the same mean and covariance, in total variation distance. Our new CLT strengthens the CLT of Valiant and Valiant by completely removing the dependence on $n$ in the error bound., Comment: 68 pages, full version of STOC 2016 paper

Let v be a planar Lipschitz vector field. We prove that the r-th variation-norm Hilbert transform along v, composed with a standard Littlewood-Paley projection operator P_k, is bounded from L^2 to L^{2, \infty}, and from L^p to itself for all p>2. Here r>2 and the operator norm is independent of k\in \Z. This generalises Lacey and Li's result for the case of the Hilbert transform. However, their result only assumes measurability for vector fields. In contrast to that, we need to assume vector fields to be Lipschitz., To appear in the Proc. of the AMS. Part of a companion paper by Hickman, Lie, Roos and the author, relies on the result in the present paper

In this paper we consider variational problems involving 1-dimensional connected sets in the Euclidean plane, such as the classical Steiner tree problem and the irrigation (Gilbert-Steiner) problem. We relate them to optimal partition problems and provide a variational approximation through Modica-Mortola type energies proving a $\Gamma$-convergence result. We also introduce a suitable convex relaxation and develop the corresponding numerical implementations. The proposed methods are quite general and the results we obtain can be extended to $n$-dimensional Euclidean space or to more general manifold ambients, as shown in the companion paper [11]., Comment: 30 pages, 5 figures

The Naruse hook-length formula is a recent general formula for the number of standard Young tableaux of skew shapes, given as a positive sum over excited diagrams of products of hook-lengths. In 2015 we gave two different $q$-analogues of Naruse's formula: for the skew Schur functions, and for counting reverse plane partitions of skew shapes. In this paper we give an elementary proof of Naruse's formula based on the case of border strips. For special border strips, we obtain curious new formulas for the Euler and $q$-Euler numbers in terms of certain Dyck path summations., Comment: 33 pages, 10 figures. This is the second paper of the series "Hook formulas for skew shapes". Most of Sections 8 and 9 in this paper used to be part of arxiv:1512.08348 (v1,v2); v2 fixed several typos; v3 made precision in definition of flagged tableaux in Section 3.2 and fixed typo in Example 3.3; v4 fixed small typos in proof of Corollary 7.6

In this paper we discuss a problem of generalization of binomial distributed triangle, that is sequence A287326 in OEIS. The main property of A287326 that it returns a perfect cube n as sum of n-th row terms over k, 0 or 1 , by means of its symmetry. In this paper we have derived a similar triangles in order to receive powers m=5,7 as row items sum and generalized obtained results in order to receive every odd-powered monomial n2m+1, m as sum of row terms of corresponding triangle. This version might be out of date, proceed by the link to see actual version., 16 pages, 8 figures, 2 tables, typos revised, added missing references, results generalized and shortened, derivations detailed.

Let $\Omega$ be either $\mathbb{R}^n$ or an unbounded strongly Lipschitz domain of $\mathbb{R}^n$, and $\Phi$ be a continuous, strictly increasing, subadditive and positive function on $(0,\infty)$ of upper type 1 and of strictly critical lower type $p_{\Phi}\in(n/(n+1),1]$. Let $L$ be a divergence form elliptic operator on $L^2 (\Omega)$ with the Neumann boundary condition and the heat semigroup generated by $L$ have the Gaussian property $(G_{\infty})$. In this paper, the authors introduce the Orlicz-Hardy space $H_{\Phi,\,L}(\Omega)$ via the nontangential maximal function associated with $\{e^{-t\sqrt{L}}\}_{t\ge0}$, and establish its equivalent characterization in terms of the Lusin area function associated with $\{e^{-t\sqrt{L}}\}_{t\ge0}$. The authors also introduce the "geometrical" Orlicz-Hardy space $H_{\Phi,\,z}(\Omega)$ via the classical Orlicz-Hardy space $H_{\Phi}(\mathbb{R}^n)$, and prove that the spaces $H_{\Phi,\,L}(\Omega)$ and $H_{\Phi,\,z}(\Omega)$ coincide with equivalent norms, from which, characterizations of $H_{\Phi,\,L}(\Omega)$, including the vertical and the nontangential maximal function characterizations associated with $\{e^{-tL}\}_{t\ge0}$, and the Lusin area function characterization associated with $\{e^{-tL}\}_{t\ge0}$, are deduced. All the above results generalize the well-known results of P. Auscher and E. Russ by taking $\Phi(t)\equiv t$ for all $t\in(0,\infty)$., Comment: This paper has been withdrawn by the authors

In this paper, we continue an investigation of the $p$-adic Ising-Vannimenus model on the Cayley tree of an arbitrary order $k$ $(k\geq 2$). We prove the existence of $p$-adic quasi Gibbs measures by analyzing fixed points of multi-dimensional $p$-adic system of equations. We are also able to show the uniqueness of translation-invariant $p$-adic Gibbs measure. Finally, it is established the existence of the phase transition for the Ising-Vannimenus model depending on the order $k$ of the Cayley tree and the prime $p$. Note that the methods used in the paper are not valid in the real setting, since all of them are based on $p$-adic analysis and $p$-adic probability measures., 23 pages, 1 figure

In this paper we provide a first realization of an idea of Jacques Tits from a 1956 paper, which first mentioned that there should be a field of characteristique une, which is now called $${\mathbb{F}_1}$$ , the field with one element. This idea was that every split reductive group scheme over $${\mathbb{Z}}$$ should descend to $${\mathbb{F}_1}$$ , and its group of $${\mathbb{F}_1}$$ -rational points should be its Weyl group. We connect the notion of a torified scheme to the notion of $${\mathbb{F}_1}$$ -schemes as introduced by Connes and Consani. This yields models of toric varieties, Schubert varieties and split reductive group schemes as $${\mathbb{F}_1}$$ -schemes. We endow the class of $${\mathbb{F}_1}$$ -schemes with two classes of morphisms, one leading to a satisfying notion of $${\mathbb{F}_1}$$ -rational points, the other leading to the notion of an algebraic group over $${\mathbb{F}_1}$$ such that every split reductive group is defined as an algebraic group over $${\mathbb{F}_1}$$ . Furthermore, we show that certain combinatorics that are expected from parabolic subgroups of GL(n) and Grassmann varieties are realized in this theory.

Let $G$ be a simple, undirected, finite graph with vertex set $V(G)$ and edge set $E(G)$. A $k$-dimensional box is a Cartesian product of closed intervals $[a_1,b_1]\times [a_2,b_2]\times\cdots\times [a_k,b_k]$. The boxicity of $G$, box$(G)$, is the minimum integer $k$ such that $G$ can be represented as the intersection graph of $k$-dimensional boxes; i.e., each vertex is mapped to a $k$-dimensional box and two vertices are adjacent in $G$ if and only if their corresponding boxes intersect. Let $\mathcal{P}=(S,P)$ be a poset, where $S$ is the ground set and $P$ is a reflexive, antisymmetric and transitive binary relation on $S$. The dimension of $\mathcal{P}$, $\dim(\mathcal{P})$, is the minimum integer $t$ such that $P$ can be expressed as the intersection of $t$ total orders. Let $G_{\mathcal{P}}$ be the underlying comparability graph of $\mathcal{P}$; i.e., $S$ is the vertex set and two vertices are adjacent if and only if they are comparable in $\mathcal{P}$. It is a well-known fact that posets with the same underlying comparability graph have the same dimension. The first result of this paper links the dimension of a poset to the boxicity of its underlying comparability graph. In particular, we show that for any poset $\mathcal{P}$, box$(G_{\mathcal{P}})/(\chi(G_{\mathcal{P}})-1) \le \dim(\mathcal{P})\le 2\mbox{box}(G_{\mathcal{P}})$, where $\chi(G_{\mathcal{P}})$ is the chromatic number of $G_{\mathcal{P}}$ and $\chi(G_{\mathcal{P}})\ne1$. It immediately follows that if $\mathcal{P}$ is a height-$2$ poset, then box$(G_{\mathcal{P}})\le \dim(\mathcal{P})\le 2\mbox{box}(G_{\mathcal{P}})$ since the underlying comparability graph of a height-$2$ poset is a bipartite graph. The second result of the paper relates the boxicity of a graph $G$ with a natural partial order associated with the extended double cover of $G$, denoted as $G_c$: Note that $G_c$ is a bipartite graph with partite sets $A$ and $B$ which are copies of $V(G)$ such that, corresponding to every $u\in V(G)$, there are two vertices $u_A\in A$ and $u_B\in B$ and $\{u_A,v_B\}$ is an edge in $G_c$ if and only if either $u=v$ or $u$ is adjacent to $v$ in $G$. Let $\mathcal{P}_c$ be the natural height-$2$ poset associated with $G_c$ by making $A$ the set of minimal elements and $B$ the set of maximal elements. We show that $\frac{\mbox{box}(G)}{2} \le \dim(\mathcal{P}_c) \le 2\mbox{box}(G)+4$. These results have some immediate and significant consequences. The upper bound $\dim(\mathcal{P})\le 2\mbox{box}(G_\mathcal{P})$ allows us to derive hitherto unknown upper bounds for poset dimension such as $\dim(\mathcal{P})\le 2\mbox{ tree width }(G_{\mathcal{P}})+4$, since boxicity of any graph is known to be at most its tree width $+\; 2$. In the other direction, using the already known bounds for partial order dimension we get the following: (1) The boxicity of any graph with maximum degree $\Delta$ is $O(\Delta\log^2\Delta)$, which is an improvement over the best-known upper bound of $\Delta^2+2$. (2) There exist graphs with boxicity $\Omega(\Delta\log\Delta)$. This disproves a conjecture that the boxicity of a graph is $O(\Delta)$. (3) There exists no polynomial-time algorithm to approximate the boxicity of a bipartite graph on $n$ vertices with a factor of $O(n^{0.5-\epsilon})$ for any $\epsilon>0$ unless $NP=ZPP$.

We say that the polynomial sequence $(Q^{(\lambda)}_n)$ is a semiclassical Sobolev polynomial sequence when it is orthogonal with respect to the inner product $$ _S= +\lambda , $$ where ${\bf u}$ is a semiclassical linear functional, ${\mathscr D}$ is the differential, the difference or the $q$--difference operator, and $\lambda$ is a positive constant. In this paper we get algebraic and differential/difference properties for such polynomials as well as algebraic relations between them and the polynomial sequence orthogonal with respect to the semiclassical functional $\bf u$. The main goal of this article is to give a general approach to the study of the polynomials orthogonal with respect to the above nonstandard inner product regardless of the type of operator ${\mathscr D}$ considered. Finally, we illustrate our results by applying them to some known families of Sobolev orthogonal polynomials as well as to some new ones introduced in this paper for the first time., Comment: 23 pages, special issue dedicated to Professor Guillermo Lopez lagomasino on the occasion of his 60th birthday, accepted in Journal of Approximation Theory

Marvin Knopp developed the theory of automorphic integrals, which generalize automorphic forms; each automorphic integral has an additional period function in its automorphic relation. The period functions satisfy relations that arise from the underlying group relations. Knopp showed that entire automorphic integrals with rational period functions satisfy a Hecke correspondence theorem, provided the rational period functions have poles only at 0 or infinity. For other automorphic integrals each corresponding Dirichlet series has a functional equation with a remainder term that arises from the nonzero poles of the rational period function. In this paper we prove a Hecke correspondence theorem for a class of automorphic integrals with rational period functions on the Hecke groups. We restrict our attention to automorphic integrals of weight that is twice an odd integer and to rational period functions that satisfy a symmetry property we call "Hecke-symmetry." We explicate the relationship between the structure of the rational period functions and the corresponding remainder terms. Each remainder term satisfies two relations (the second of which is new in this paper) corresponding to the two relations for the rational period function.

In this paper we classify, up to analytic isomorphism, the family of almost stretched Artinian complete intersection A=R/I with a given Hilbert function, in the case R is a power series ring with an arbitrary number of variables., 20 pages. This paper generalizes a previous version where the result was proven for a power series ring in two variables

Partial cubes are isometric subgraphs of hypercubes. Structures on a graph defined by means of semicubes, and Djokovi\'{c}'s and Winkler's relations play an important role in the theory of partial cubes. These structures are employed in the paper to characterize bipartite graphs and partial cubes of arbitrary dimension. New characterizations are established and new proofs of some known results are given. The operations of Cartesian product and pasting, and expansion and contraction processes are utilized in the paper to construct new partial cubes from old ones. In particular, the isometric and lattice dimensions of finite partial cubes obtained by means of these operations are calculated., Comment: 36 pages, 17 figures

This paper is a sequel to the paper \cite{refGH}. We relate the matroid notion of a combinatorial geometry to a generalization which we call a configuration type. Configuration types arise when one classifies the Hilbert functions and graded Betti numbers for fat point subschemes supported at $n\le8$ essentially distinct points of the projective plane. Each type gives rise to a surface $X$ obtained by blowing up the points. We classify those types such that $n=6$ and $-K_X$ is nef. The surfaces obtained are precisely the desingularizations of the normal cubic surfaces. By classifying configuration types we recover in all characteristics the classification of normal cubic surfaces, which is well-known in characteristic 0 \cite{refBW}. As an application of our classification of configuration types, we obtain a numerical procedure for determining the Hilbert function and graded Betti numbers for the ideal of any fat point subscheme $Z=m_1p_1+...+m_6p_6$ such that the points $p_i$ are essentially distinct and $-K_X$ is nef, given only the configuration type of the points $p_1,...,p_6$ and the coefficients $m_i$., 14 pages, final version

This paper is a sequel to \cite{Tz10}, where a local version of ZFC, LZFC, was introduced and examined and transitive models of ZFC with properties that resemble large cardinal properties, namely Mahlo and $\Pi_1^1$-indescribable models, were considered. By analogy we refer to such models as "large models", and the properties in question as "large model properties". Continuing here in the same spirit we consider further large model properties, that resemble stronger large cardinals, namely, "elementarily embeddable", "extendible" and "strongly extendible", "critical" and "strongly critical", "self-critical'' and "strongly self-critical", the definitions of which involve elementary embeddings. Each large model property $\phi$ gives rise to a localization axiom $Loc^{\phi}({\rm ZFC})$ saying that every set belongs to a transitive model of ZFC satisfying $\phi$. The theories ${\rm LZFC}^\phi={\rm LZFC}$+$Loc^{\phi}({\rm ZFC})$ are local analogues of the theories ZFC+"there is a proper class of large cardinals $\psi$", where $\psi$ is a large cardinal property. If $sext(x)$ is the property of strong extendibility, it is shown that ${\rm LZFC}^{sext}$ proves Powerset and $\Sigma_1$-Collection. In order to refute $V=L$ over LZFC, we combine the existence of strongly critical models with an axiom of different flavor, the Tall Model Axiom ($TMA$). $V=L$ can also be refuted by $TMA$ plus the axiom $GC$ saying that "there is a greatest cardinal", although it is not known if $TMA+GC$ is consistent over LZFC. Finally Vop\v{e}nka's Principle ($VP$) and its impact on LZFC are examined. It is shown that ${\rm LZFC}^{sext}+VP$ proves Powerset and Replacement, i.e., ZFC is fully recovered. The same is true for some weaker variants of ${\rm LZFC}^{sext}$. Moreover the theories LZFC$^{sext}$+$VP$ and ZFC+$VP$ are shown to be identical., Comment: 32 pages

In our previous paper math.QA/0409261, we defined a deformation of the group algebra of the group of even elements of a Coxeter group W, and showed that it is flat for all values of parameters if and only if all the rank 3 parabolic subgroups of W are infinite. In this paper, we study what happens in the general case. Then the deformation is flat only for some values of parameters, and the set of all such values is called the flatness locus. The main result of the paper is an explicit description of the this flatness locus as a scheme over Z. More specifically, we show that this scheme is the intersection of the flatness loci for the subalgebras corresponding to parabolic subgroups of rank 3. The latter are determined by solving the rigid multiplicative Deligne-Simpson problem. We also define additive analogs of our algebras and study their properties., Comment: 19 pages, latex

It is well known that subspaces of the Hardy space over the unit disk which are invariant under the backward shift occur as the image of an observability operator associated with a discrete-time linear system with stable state-dynamics, as well as the functional-model space for a Hilbert space contraction operator. We discuss two multivariable extensions of this structure, where the classical Hardy space is replaced by (1) the Fock space of formal power series in a collection of d noncommuting indeterminates with norm-square-summable vector coefficients, and (2) the reproducing kernel Hilbert space (often now called the Arveson space) over the unit ball in $${\mathbb{C}^{d}}$$ with reproducing kernel $${k(\lambda, \zeta) = 1/(1 - \langle \lambda, \zeta \rangle) (\lambda, \zeta \in \mathbb{C}^{d} with \| \lambda \|, \| \zeta \| < 1}$$ ). In the first case, the associated linear system is of noncommutative Fornasini---Marchesini type with evolution along a free semigroup with d generators, while in the second case the linear system is a standard (commutative) Fornasini---Marchesini-type system with evolution along the integer lattice $${\mathbb{Z}^{d}}$$ . An abelianization map (or symmetrization of the Fock space) links the first case with the second. The second case has special features depending on whether the operator-tuple defining the state dynamics is commutative or not. The paper focuses on multidimensional state-output linear systems and the associated observability operators; followup papers Ball, Bollotnikov, and Fang (2007a, 2007b) use the results here to extend the analysis to represent observability-operator ranges as reproducing kernel Hilbert spaces with reproducing kernels constructed from the transfer function of a conservative multidimensional (noncommutative or commutative) input-state-output linear system.

In the present paper, we study the chaotic representation property for certain families ${\mathscr{X}}$ of square integrable martingales on a finite time interval $[0,T]$. For this purpose, we introduce the notion of compensated-covariation stability of such families. The chaotic representation property will be defined using iterated integrals with respect to a given family ${\mathscr{X}}$ of square integrable martingales having deterministic mutual predictable covariation $\langle X,Y\rangle$ for all $X,Y\in{\mathscr{X}}$. The main result of the present paper is stated in Theorem 5.8 below: If ${\mathscr{X}}$ is a compensated-covariation stable family of square integrable martingales such that $\langle X,Y\rangle$ is deterministic for all $X,Y\in{\mathscr{X}}$ and, furthermore, the system of monomials generated by ${\mathscr{X}}$ is total in $L^{2}(\Omega,\mathscr{F}^{\mathscr{X}}_{T},\mathbb{P})$, then ${\mathscr{X}}$ possesses the chaotic representation property with respect to the $\sigma$-field $\mathscr{F}^{\mathscr{X}}_{T}$. We shall apply this result to the case of Lévy processes. Relative to the filtration $\mathbb{F}^{L}$ generated by a Lévy process $L$, we construct families of martingales which possess the chaotic representation property. As an illustration of the general results, we will also discuss applications to continuous Gaussian families of martingales and independent families of compensated Poisson processes. We conclude the paper by giving, for the case of Lévy processes, several examples of concrete families ${\mathscr{X}}$ of martingales including Teugels martingales.

This paper is concerned with the performance of Orthogonal Matching Pursuit (OMP) algorithms applied to a dictionary $\mathcal{D}$ in a Hilbert space $\mathcal{H}$. Given an element $f\in \mathcal{H}$, OMP generates a sequence of approximations $f_n$, $n=1,2,\dots$, each of which is a linear combination of $n$ dictionary elements chosen by a greedy criterion. It is studied whether the approximations $f_n$ are in some sense comparable to {\em best $n$ term approximation} from the dictionary. One important result related to this question is a theorem of Zhang \cite{TZ} in the context of sparse recovery of finite dimensional signals. This theorem shows that OMP exactly recovers $n$-sparse signal, whenever the dictionary $\mathcal{D}$ satisfies a Restricted Isometry Property (RIP) of order $An$ for some constant $A$, and that the procedure is also stable in $\ell^2$ under measurement noise. The main contribution of the present paper is to give a structurally simpler proof of Zhang's theorem, formulated in the general context of $n$ term approximation from a dictionary in arbitrary Hilbert spaces $\mathcal{H}$. Namely, it is shown that OMP generates near best $n$ term approximations under a similar RIP condition., 12 pages

This paper presents a hybridized formulation for the weak Galerkin mixed finite element method (WG-MFEM) which was introduced and analyzed for second order elliptic equations. The WG-MFEM method was designed by using discontinuous piecewise polynomials on finite element partitions consisting of polygonal or polyhedral elements of arbitrary shape. The key to WG-MFEM is the use of a discrete weak divergence operator which is defined and computed by solving inexpensive problems locally on each element. The hybridized formulation of this paper leads to a significantly reduced system of linear equations involving only the unknowns arising from the Lagrange multiplier in hybridization. Optimal-order error estimates are derived for the hybridized WG-MFEM approximations. Some numerical results are reported to confirm the theory and a superconvergence for the Lagrange multiplier., Comment: 14 pages, 1 figure, 3 tables

Many finite-state reversible Markov chains can be naturally decomposed into "projection" and "restriction" chains. In this paper we provide bounds on the total variation mixing times of the original chain in terms of the mixing properties of these related chains. This paper is in the tradition of existing bounds on Poincare and log-Sobolev constants of Markov chains in terms of similar decompositions [JSTV04, MR02, MR06, MY09]. Our proofs are simple, relying largely on recent results relating hitting and mixing times of reversible Markov chains [PS13, Oli12]. We describe situations in which our results give substantially better bounds than those obtained by applying existing decomposition results and provide examples for illustration., Comment: 39 pages, 1 figure