Weyl quantization of Lebesgue spaces

We study boundedness and compactness properties for the Weyl quantization with symbols in L^q (?^2d ) acting on L^p (?^d ). This is shown to be equivalent, in suitable Banach space setting, to that of the Wigner transform. We give a short proof by interpolation of Lieb's sufficient conditions for the boundedness of the Wigner transform, proving furthermore that these conditions are also necessary. This yields a complete characterization of boundedness for Weyl operators in L^p setting; compactness follows by approximation. We extend these results defining two scales of spaces, namely L_*^q (?^2d ) and L_?^q (R^2d ), respectively smaller and larger than the L^q (?^2d ),and showing that the Weyl correspondence is bounded on L_*^q (R^2d ) (and yields compact operators), whereas it is not on L_?^q (R^2d ). We conclude with a remark on weak‐type L^p boundedness (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Limit theory for the random on‐line nearest‐neighbor graph

In the on‐line nearest‐neighbor graph (ONG), each point after the first in a sequence of points in ?^d is joined by an edge to its nearest neighbor amongst those points that precede it in the sequence. We study the large‐sample asymptotic behavior of the total power‐weighted length of the ONG on uniform random points in (0,1)^d. In particular, for d = 1 and weight exponent α > 1/2, the limiting distribution of the centered total weight is characterized by a distributional fixed‐point equation. As an ancillary result, we give exact expressions for the expectation and variance of the standard nearest‐neighbor (directed) graph on uniform random points in the unit interval. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Lieb–Thirring inequalities for higher order differential operators

We derive Lieb–Thirring inequalities for the Riesz means of eigenvalues of order γ ≥ 3/4 for a fourth order operator in arbitrary dimensions. We also consider some extensions to polyharmonic operators, and to systems of such operators, in dimensions greater than one. For the critical case γ = 1 – 1/(2l) in dimension d = 1 with l ≥ 2 we prove the inequality L⁰_l,γ,d < L_l,γ,d , which holds in contrast to current conjectures. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Spectral Algorithms for Tensor Completion

In the tensor completion problem, one seeks to estimate a low‐rank tensor based on a random sample of revealed entries. In terms of the required sample size, earlier work revealed a large gap between estimation with unbounded computational resources (using, for instance, tensor nuclear norm minimization) and polynomial‐time algorithms. Among the latter, the best statistical guarantees have been proved, for third‐order tensors, using the sixth level of the sum‐of‐squares (sos ) semidefinite programming hierarchy. However, the sos approach does not scale well to large problem instances. By contrast, spectral methods—based on unfolding or matricizing the tensor—are attractive for their low complexity, but have been believed to require a much larger sample size. This paper presents two main contributions. First, we propose a new method, based on unfolding, which outperforms naive ones for symmetric k^th‐order tensors of rank r. For this result we make a study of singular space estimation for partially revealed matrices of large aspect ratio, which may be of independent interest. For third‐order tensors, our algorithm matches the sos method in terms of sample size (requiring about rd^3/2 revealed entries), subject to a worse rank condition (r ≪ d^3/4 rather than r ≪ d^3/2). We complement this result with a different spectral algorithm for third‐order tensors in the overcomplete (r ≥ d) regime. Under a random model, this second approach succeeds in estimating tensors of rank d ≤ r ≪ d^3/2 from about rd^3/2 revealed entries. © 2018 Wiley Periodicals, Inc.     

On the number of minimal 1-Steiner trees

We count the number of nonisomorphic geometric minimum spanning trees formed by adding a single point to ann-point set ind-dimensional space, by relating it to a family of convex decompositions of space. TheO(n ^d log^{2d 2}−d n) bound that we obtain significantly improves previously known bounds and is tight to within a polylogarithmic factor. The research of D. Eppstein was performed in part while visiting Xerox PARC.     

Toeplitz Operators on Generalized Bergman Spaces

We consider the weighted Bergman spaces HL²(\mathbb B^d, m_l){\mathcal {H}L^{2}(\mathbb {B}^{d}, \mu_{\lambda})}, where we set dm_l(z) = c_l(1-|z|²)^l dt(z){d\mu_{\lambda}(z) = c_{\lambda}(1-|z|^2)^{\lambda} d\tau(z)}, with τ being the hyperbolic volume measure. These spaces are nonzero if and only if λ > d. For 0 < λ ≤ d, spaces with the same formula for the reproducing kernel can be defined using a Sobolev-type norm. We define Toeplitz operators on these generalized Bergman spaces and investigate their properties. Specifically, we describe classes of symbols for which the corresponding Toeplitz operators can be defined as bounded operators or as a Hilbert–Schmidt operators on the generalized Bergman spaces.     

Resolutions of PG(5, 2) with point‐cyclic automorphism group

A t‐(υ, k, λ) design is a set of υ points together with a collection of its k‐subsets called blocks so that all subsets of t points are contained in exactly λ blocks. The d‐dimensional projective geometry over GF(q), PG(d, q), is a 2‐(q^d + q^d−1 + … + q + 1, q + 1, 1) design when we take its points as the points of the design and its lines as the blocks of the design. A 2‐(υ, k, 1) design is said to be resolvable if the blocks can be partitioned as ℛ = {R₁, R₂, …, R_s}, where s = (υ − 1)/(k−1) and each R_i consists of υ/k disjoint blocks. If a resolvable design has an automorphism σ which acts as a cycle of length υ on the points and ℛ^σ = ℛ, then the design is said to be point‐cyclically resolvable. The design associated with PG(5, 2) is known to be resolvable and in this paper, it is shown to be point‐cyclically resolvable by enumerating all inequivalent resolutions which are invariant under a cyclic automorphism group G = 〈σ〉 where σ is a cycle of length 63. These resolutions are the only resolutions which admit a point‐transitive automorphism group. Furthermore, some necessary conditions for the point‐cyclic resolvability of 2‐(υ, k, 1) designs are also given. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 2–14, 2000     

Anderson localization and Lifshits tails for random surface potentials

We consider Schrödinger operators on L²(R^d) with a random potential concentrated near the surface R^d₁×{0}⊂R^d. We prove that the integrated density of states of such operators exhibits Lifshits tails near the bottom of the spectrum. From this and the multiscale analysis by Boutet de Monvel and Stollmann [Arch. Math. 80 (2003) 87-97] we infer Anderson localization (pure point spectrum and dynamical localization) for low energies. Our proof of Lifshits tails relies on spectral properties of Schrödinger operators with partially periodic potentials. In particular, we show that the lowest energy band of such operators is parabolic.     

Bounds on vertex colorings with restrictions on the union of color classes

A proper coloring of a graph is a labeled partition of its vertices into parts which are independent sets. In this paper, given a positive integer j and a family ? of connected graphs, we consider proper colorings in which we require that the union of any j color classes induces a subgraph which has no copy of any member of ?. This generalizes some well‐known types of proper colorings like acyclic colorings (where j = 2 and ?is the collection of all even cycles) and star colorings (where j = 2 and ?consists of just a path on 4 vertices), etc. For this type of coloring, we obtain an upper bound of O(d^{(k ? 1)/(k ? j)}) on the minimum number of colors sufficient to obtain such a coloring. Here, d refers to the maximum degree of the graph and k is the size of the smallest member of ?. For the case of j = 2, we also obtain lower bounds on the minimum number of colors needed in the worst case. As a corollary, we obtain bounds on the minimum number of colors sufficient to obtain proper colorings in which the union of any j color classes is a graph of bounded treewidth. In particular, using O(d^8/7) colors, one can obtain a proper coloring of the vertices of a graph so that the union of any two color classes has treewidth at most 2. We also show that this bound is tight within a multiplicative factor of O((logd)^1/7). We also consider generalizations where we require simultaneously for several pairs (j_i, ?_i) (i = 1, …, l) that the union of any j_i color classes has no copy of any member of ?_i and obtain upper bounds on the corresponding chromatic numbers. © 2011 Wiley Periodicals, Inc. J Graph Theory 66: 213–234, 2011     

<Emphasis Type="Italic">L</Emphasis><Superscript><Emphasis Type="Italic">p</Emphasis></Superscript>–dimension free boundedness for Riesz transforms associated to Hermite functions<Superscript>⋆</Superscript>

Riesz transforms associated to Hermite functions were introduced by S. Thangavelu, who proved that they are bounded operators on 1<p< . In this paper we give a different proof that allows us to show that the L^p–norms of these operators are bounded by a constant not depending on the dimension d. Moreover, we define Riesz transforms of higher order and free dimensional estimates of the L^p–bounds of these operators are obtained. In order to prove the mentioned results we give an extension of the Littlewood-Paley theory that we believe of independent interest.Mathematical Subject Classification (2000):42B20, 42B25, 42C10Partially supported by Instituto Argentino de Matemática CONICET, Convenio Universidad Autónoma de Madrid-Universidad Nacional del Litoral, UBACYT 2000-2002 and Ministerio de Ciencia y Tecnologí BFM2002-04013-C02-02     

The diameter game

A large class of Positional Games are defined on the complete graph on n vertices. The players, Maker and Breaker, take the edges of the graph in turns, and Maker wins iff his subgraph has a given — usually monotone — property. Here we introduce the d‐diameter game, which means that Maker wins iff the diameter of his subgraph is at most d. We investigate the biased version of the game; i.e., when the players may take more than one, and not necessarily the same number of edges, in a turn. Our main result is that we proved that the 2‐diameter game has the following surprising property: Breaker wins the game in which each player chooses one edge per turn, but Maker wins as long as he is permitted to choose 2 edges in each turn whereas Breaker can choose as many as (1/9)n^1/8/(lnn)^3/8. In addition, we investigate d‐diameter games for d ≥ 3. The diameter games are strongly related to the degree games. Thus, we also provide a generalization of the fair degree game for the biased case. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Commutativity of kth‐order slant Toeplitz operators

In this paper, commutativity of k^th‐order slant Toeplitz operators are discussed. We show that commutativity and essential commutativity of two slant Toeplitz operators are the same. Also, we study k^th‐order slant Toeplitz operators on the Bergman space L²_a(D) and give some commuting properties, algebraic and spectral properties of k^th‐order slant Toeplitz operators on the Bergman space (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Inexpensive d‐dimensional matchings

Suppose that independent U(0, 1) weights are assigned to the ${d\choose 2}n^{2}$ edges of the complete d‐partite graph with n vertices in each of the d maximal independent sets. Then the expected weight of the minimum‐weight perfect d‐dimensional matching is at least $\frac{3}{16}n^{1-(2/d)}$. We describe a randomized algorithm that finds a perfect d‐dimensional matching whose expected weight is at most 5d³n^1?(2/d)+d¹⁵ for all d≥3 and n≥1. © 2002 John Wiley & Sons, Inc. Random Struct. Alg., 20, 50–58, 2002     

On isomorphity of measure-preserving ℤ<Superscript>2</Superscript>-actions that have isomorphic Cartesian powers

Assume that Δ and Π are representations of the group ℤ² by operators on the space L ₂(X, μ) that are induced by measure-preserving automorphisms, and for some d, the representations Δ^⨂d and Π^⨂d are conjugate to each other, Δ(ℤ² \(0, 0)) consists of weakly mixing operators, and there is a weak limit (over some subsequence in ℤ² of operators from Δ(ℤ²)) which is equal to a nontrivial, convex linear combination of elements of Δ(ℤ²) and of the projection onto constant functions. We prove that in this case, Δ and Π are also conjugate to each other. Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 13, No. 8, pp. 193–212, 2007.     

Hypergraph list coloring and Euclidean Ramsey theory

A hypergraph is simple if it has no two edges sharing more than a single vertex. It is s‐list colorable (or s‐choosable) if for any assignment of a list of s colors to each of its vertices, there is a vertex coloring assigning to each vertex a color from its list, so that no edge is monochromatic. We prove that for every positive integer r, there is a function d_r(s) such that no r‐uniform simple hypergraph with average degree at least d_r(s) is s‐list‐colorable. This extends a similar result for graphs, due to the first author, but does not give as good estimates of d_r(s) as are known for d₂(s), since our proof only shows that for each fixed r ≥ 2, d_r(s) ≤ 2 We use the result to prove that for any finite set of points X in the plane, and for any finite integer s, one can assign a list of s distinct colors to each point of the plane so that any coloring of the plane that colors each point by a color from its list contains a monochromatic isometric copy of X. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

Embedding vector‐valued Besov spaces into spaces of γ ‐radonifying operators

It is shown that a Banach space E has type p if and only for some (all) d ≥ 1 the Besov space B^{(1/p – 1/2)d} _p,p (?^d ; E) embeds into the space γ (L²(?^d ), E) of γ ‐radonifying operators L²(?^d ) → E. A similar result characterizing cotype q is obtained. These results may be viewed as E ‐valued extensions of the classical Sobolev embedding theorems. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

The Projection Median of a Set of Points in ℝ<Superscript><Emphasis Type="Italic">d</Emphasis></Superscript>

The projection median of a finite set of points in ℝ² was introduced by Durocher and Kirkpatrick [Computational Geometry: Theory and Applications, Vol. 42 (5), 364–375, 2009]. They proved that the projection median in ℝ² provides a better approximation of the two-dimensional Euclidean median than the center of mass or the rectilinear median, while maintaining a fixed degree of stability. In this paper we study the projection median of a set of points in ℝ ^d for d≥2. Using results from geometric measure theory we show that the d-dimensional projection median provides a (d/π)B(d/2,1/2)-approximation to the d-dimensional Euclidean median, where B(α,β) denotes the Beta function. We also show that the stability of the d-dimensional projection median is at least \frac1(d/p)B(d/2, 1/2)\frac{1}{(d/\pi)B(d/2, 1/2)}, and its breakdown point is 1/2. Based on the stability bound and the breakdown point, we compare the d-dimensional projection median with the rectilinear median and the center of mass, as a candidate for approximating the d-dimensional Euclidean median. For the special case of d=3, our results imply that the three-dimensional projection median is a (3/2)-approximation of the three-dimensional Euclidean median, which settles a conjecture posed by Durocher.     

Condition number estimates for combined potential integral operators in acoustics and their boundary element discretisation

We consider the classical coupled, combined‐field integral equation formulations for time‐harmonic acoustic scattering by a sound soft bounded obstacle. In recent work, we have proved lower and upper bounds on the L² condition numbers for these formulations and also on the norms of the classical acoustic single‐ and double‐layer potential operators. These bounds to some extent make explicit the dependence of condition numbers on the wave number k, the geometry of the scatterer, and the coupling parameter. For example, with the usual choice of coupling parameter they show that, while the condition number grows like k^1/3 as k →∞, when the scatterer is a circle or sphere, it can grow as fast as k^7/5 for a class of “trapping” obstacles. In this article, we prove further bounds, sharpening and extending our previous results. In particular, we show that there exist trapping obstacles for which the condition numbers grow as fast as exp(γk), for some γ > 0, as k →∞ through some sequence. This result depends on exponential localization bounds on Laplace eigenfunctions in an ellipse that we prove in the appendix. We also clarify the correct choice of coupling parameter in 2D for low k. In the second part of the article, we focus on the boundary element discretisation of these operators. We discuss the extent to which the bounds on the continuous operators are also satisfied by their discrete counterparts and, via numerical experiments, we provide supporting evidence for some of the theoretical results, both quantitative and asymptotic, indicating further which of the upper and lower bounds may be sharper. © 2010 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2010     

Counting the onion

Iteratively computing and discarding a set of convex hulls creates a structure known as an “onion.” In this paper, we show that the expected number of layers of a convex hull onion for n uniformly and independently distributed points in a disk is Θ(n^2/3). Additionally, we show that in general the bound is Θ(n^2/(d+1)) for points distributed in a d‐dimensional ball. Further, we show that this bound holds more generally for any fixed, bounded, full‐dimensional shape with a nonempty interior. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004