Rademacher chaos: tail estimates versus limit theorems

We study Rademacher chaos indexed by a sparse set which has a fractional combinatorial dimension. We obtain tail estimates for finite sums and a normal limit theorem as the size tends to infinity. The tails for finite sums may be much larger than the tails of the limit.     

Infinite,highly connected digraphs with no two arc-disjoint spanning trees

We present a construction of countably infinite, highly connected graphs and digraphs, which shows that several basic connectivity results on finite graphs, including Edmondsapos;s branching theorem, cannot be extended to the infinite case.     

Bounds for arrays of dots with distinct slopes or lengths

Ann×m sonar sequence is a subset of then×m grid with exactly one point in each column, such that the vectors determined by them are all distinct. We show that for fixedn the maximalm for which a sonar sequence exists satisfiesn–Cn ^11/20<m<n+4n ^2/3 for alln andm>n+c logn log logn for infinitely manyn.Another problem concerns the maximal numberD of points that can be selected from then×m grid so that all the vectors have slopes. We proven ^1/2Dn ^4/5 Supported by Hungarian National Foundation for Scientific Research, Grant No. 1901Research conducted by Herbert Taylor was sponsored in part by the Office of Naval Research under ONR Contract No. N00014-90-J-1341.     

Counting colorful multi-dimensional trees

LetV be a disjoint union ofr finite setsV ₁,...,V _r (colors). A collectionT of subsets ofV iscolorful if each member ifT contains at most one point of each color. Ak-dimensional colorful tree is a colorful collectionT of subsets ofV, each of sizek+1, such that if we add toT all the colorful subsets ofV of sizek or less, we get aQ-acyclic simplicial complex _T We count (using the Binet-Cauchy theorem) thek-dimensional colorful trees onV (for allk), where each treeT is counted with weight . The result confirms, in a way, a formula suggested by Bolker. (fork-r–1). It extends, on one hand, a result of Kalai on weighted counting ofk-dimensional trees and, on the other hand, enumeration formulas for multi-partite (1-dimensional) trees. All these results are extensions of Cayley's celebrated treecounting formula, now 100 years old.     

On the product of sign vectors and unit vectors

For a fixed unit vectora=(a ₁,...,a _n )S ^n-1, consider the 2 ⁿ sign vectors=(₁,..., _n ){±1{ ⁿ and the corresponding scalar products^·a = _n ⁱ⁼¹ = _i a _i . The question that we address is: for how many of the sign vectors must^.a lie between–1 and 1. Besides the straightforward interpretation in terms of the sums ±a ₂ , this question has appealing reformulations using the language of probability theory or of geometry.The natural conjectures are that at least 1/2 the sign vectors yield |.a|1 and at least 3/8 of the sign vectors yield |.a|<1 (the latter excluding the case when |a _i |=1 for somei). These conjectured lower bounds are easily seen to be the best possible. Here we prove a lower bound of 3/8 for both versions of the problem, thus completely solving the version with strict inequality. The main part of the proof is cast in a more general probabilistic framework: it establishes a sharp lower bound of 3/8 for the probability that |X+Y|<1, whereX andY are independent random variables, each having a symmetric distribution with variance 1/2.We also consider an asymptotic version of the question, wheren along a sequence of instances of the problem satisfying ||a||0. Our result, best expressed in probabilistic terms, is that the distribution of .a converges to the standard normal distribution, and in particular the fraction of sign vectors yielding .a between –1 and 1 tends to 68%.This research was supported in part by the Institute for Mathematics and its Applications with funds provided by the National Science Foundation.     

New coordination modes of iminodiacetamide type ligands in palladium(II) complexes: crystallographic and DFT studies

The reactions of N-alkyliminodiacetamide derivatives, namely N-ethyliminodiacetamide (CH₃CH₂N(CH₂CONH₂)₂; Etimda) and N-isopropyliminodiacetamide (CH₃)₂CHN(CH₂CONH₂)₂; i-Primda), with sodium tetrachloropalladate(II) in aqueous solutions were investigated. Three new palladium(II) complexes, [Pd(Etimda_?H)₂]?2H₂O (1), [Pd(i-Primda_?H)₂]?2H₂O (2) and [PdCl₂(i-Primda)] (3), were obtained and characterized by X-ray structural analysis, infrared spectroscopy and thermal analysis (TGA). The square planar coordination environments around the palladium(II) ions in complexes 1 and 2 consist of two N,N′-bidentate N-alkyliminodiacetamidato ligands, with imino N atoms in trans-position. The complex 3 also exhibits a square planar coordination environment around Pd(II), but with two chloride ions and one neutral N-isopropyliminodiacetamide ligand bound in an N,O′-bidentate coordination mode. The described coordination modes, as well as the presence of deprotonated amide groups in ligands in 1 and 2, are found for the first time in palladium(II) complexes with iminodiacetamide type ligands. The molecular geometries and infrared spectra of these three complexes were also modelled using DFT calculations, at the BP86-D3/def2-TZVPP/PCM level of theory. The RMSD values suggest a good agreement of the calculated and experimental geometries. A QTAIM analysis suggests a qualitative correlation between bond lengths and energy densities, also supported by an NBO analysis. The dimer interaction energy between complex units was estimated at about ?15 kcal/mol for all complexes.     

On a theorem of lovász on covers inr-partite hypergraphs

A theorem of Lovász asserts that (H)/*(H)r/2 for everyr-partite hypergraphH (where and * denote the covering number and fractional covering number respectively). Here it is shown that the same upper bound is valid for a more general class of hypergraphs: those which admit a partition (V ₁, ...,V _k ) of the vertex set and a partitionp ₁+...+p _k ofr such that |eV _i |p _i r/2 for every edgee and every 1ik. Moreover, strict inequality holds whenr>2, and in this form the bound is tight. The investigation of the ratio /* is extended to some other classes of hypergraphs, defined by conditions of similar flavour. Upper bounds on this ratio are obtained fork-colourable, stronglyk-colourable and (what we call)k-partitionable hypergraphs.Supported by grant HL28438 at MIPG, University of Pennsylvania, and by the fund for the promotion of research at the Technion.This author's research was supported by the fund for the promotion of research at the Technion.     

Strictly positive definite functions on spheres in Euclidean spaces

In this paper we study strictly positive definite functions on the unit sphere of the -dimensional Euclidean space. Such functions can be used for solving a scattered data interpolation problem on spheres. Since positive definite functions on the sphere were already characterized by Schoenberg some fifty years ago, the issue here is to determine what kind of positive definite functions are actually strictly positive definite. The study of this problem was initiated recently by Xu and Cheney (Proc. Amer. Math. Soc. 116 (1992), 977--981), where certain sufficient conditions were derived. A new approach, which is based on a critical connection between this problem and that of multivariate polynomial interpolation on spheres, is presented here. The relevant interpolation problem is subsequently analyzed by three different complementary methods. The first is based on the de Boor-Ron general ``least solution for the multivariate polynomial interpolation problem'. The second, which is suitable only for , is based on the connection between bivariate harmonic polynomials and univariate analytic polynomials, and reduces the problem to the structure of the integer zeros of bounded univariate exponentials. Finally, the last method invokes the realization of harmonic polynomials as the polynomial kernel of the Laplacian, thereby exploiting some basic relations between homogeneous ideals and their polynomial kernels.

     

Patterns and Structures in Disk Packings

Using a computational procedure that imitates tightening of an assembly of billiard balls, we have generated a number of packings of n equal and non-equal disks in regions of various shapes. Our experiments are of three major types. In the first type, the values of n are in thousands, the initial disk configuration is random and a priori one expects the generated packings to be random. In fact, the packings turn out to display non-random geometric patterns and regular features, including polycrystalline textures with "rattlers" typically trapped along the grain boundaries. An experiment of the second type begins with a known or conjectured optimal disk packing configuration, which is then "frustrated" by a small perturbation such as variation of the boundary shape or a relative increase of the size of a selected disk with respect to the sizes of the other disks. We present such frustrated packings for both large n (~ 10, 000) and small n (~ 50 to 200). Motivated by applications in material science and physics, the first and second type of experiments are performed for boundary shapes rarely discussed in the literature on dense packings: torus, a strip cut from a cylinder, a regular hexagon with periodic boundaries. Experiments of the third type involve the shapes popular among mathematicians: circles, squares, and equilateral triangles the boundaries of which are hard reflecting walls. The values of n in these experiments vary from several tens to few hundreds. Here the obtained configurations could be considered as candidates for the densest packings, rather than random ones. Some of these conjecturally optimal packings look regular and the regularity often extends across different values of n. Specifically, as n takes on an increasing sequence of values, n = n(1), n(2), ...n(k), ..., the packings follow a well-defined pattern. This phenomenon is especially striking for packings in equilateral triangles, where (as far as we can tell from our finite computational experiments), not only are there an infinite number of different patterns, each with its own different sequence n(1), n(2), ...n(k), ..., but many of these sequences seem to continue indefinitely. For other shapes, notably squares and circles, the patterns either cease to be optimal or even cease to exist (as packings of non-overlapping disks) above some threshold value n(k0) (depending on the pattern). In these cases, we try to identify the values of n(k0).     

Experimental investigations in combining primal dual interior point method and simplex based LP solvers

The use of a primal dual interior point method (PD) based optimizer as a robust linear programming (LP) solver is now well established. Instead of replacing the sparse simplex algorithm (SSX), the PD is increasingly seen as complementing it. The progress of PD iterations is not hindered by the degeneracy or stalling problem of SSX, indeed it reaches the near optimum solution very quickly. The SSX algorithm, in contrast, is not affected by the numeral instabilities which slow down the convergence of the PD near the optimal face. If the solution to the LP problem is non-unique, the PD algorithm converges to an interior point of the solution set while the SSX algorithm finds an extreme point solution. To take advantage of the attractive properties of both the PD and the SSX, we have designed a hybrid framework whereby crossover from PD to SSX can take place at any stage of the PD optimization run. The crossover to SSX involves the partition of the PD solution set to active and dormant variables. In this paper we examine the practical difficulties in partitioning the solution set, we discuss the reliability of predicting the solution set partition before optimality is reached and report the results of combining exact and inexact prediction with SSX basis recovery.