Objects that cannot be taken apart with two hands

It has been conjectured that every configurationC of convex objects in 3-space with disjoint interiors can be taken apart by translation with two hands: that is, some proper subset ofC can be translated to infinity without disturbing its complement. We show that the conjecture holds for five or fewer objects and give a counterexample with six objects. We extend the counterexample to a configuration that cannot be taken apart with two hands using arbitrary isometries (rigid motions). The research of J. Snoeyink was supported in part by an NSERC Research Grant. J. Stolfi was previously at DEC Systems Research Center, Palo Alto, CA, USA.     

Existence and characterization of product-form invariant distributions for state-dependent stochastic networks in the heavy-traffic diffusion limit

We consider state-dependent stochastic networks in the heavy-traffic diffusion limit represented by reflected jump-diffusions in the orthant ℝ₊ ⁿ with state-dependent reflection directions upon hitting boundary faces. Jumps are allowed in each coordinate by means of independent Poisson random measures with jump amplitudes depending on the state of the process immediately before each jump. For this class of reflected jump-diffusion processes sufficient conditions for the existence of a product-form stationary density and an ergodic characterization of the stationary distribution are provided. Moreover, such stationary density is characterized in terms of semi-martingale local times at the boundaries and it is shown to be continuous and bounded. A central role is played by a previously established semi-martingale local time representation of the regulator processes. F.J. Piera’s research supported in part by CONICYT, Chile, FONDECYT Project 1070797. R.R. Mazumdar’s research supported in part by NSF, USA, Grant 0087404 through Networking Research Program, and a Discovery Grant from NSERC, Canada.     

The exponential rates of convergence of posterior distributions

After the observations were observed, the posterior distribution under mild conditions becomes more concentrated in the neighbourhood of the mode of the posterior distribution as sample size n increase. In this paper, the exponential rate of convergence of posterior distribution around the mode is established by using the generalized Laplace method. An example is also given.This work was supported in part by the Natural Sciences and Engineering Research Council of Canada under Grant NSERC A-9216.     

Interpolation lattices in several variables

Principal lattices are classical simplicial configurations of nodes suitable for multivariate polynomial interpolation in n dimensions. A principal lattice can be described as the set of intersection points of n + 1 pencils of parallel hyperplanes. Using a projective point of view, Lee and Phillips extended this situation to n + 1 linear pencils of hyperplanes. In two recent papers, two of us have introduced generalized principal lattices in the plane using cubic pencils. In this paper we analyze the problem in n dimensions, considering polynomial, exponential and trigonometric pencils, which can be combined in different ways to obtain generalized principal lattices.We also consider the case of coincident pencils. An error formula for generalized principal lattices is discussed. Partially supported by the Spanish Research Grant BFM2003-03510, by Gobierno de Aragón and Fondo Social Europeo.     

Holey self-orthogonal Latin squares with symmetric orthogonal mates

We improve the existence results for holey self-orthogonal Latin squares with symmetric orthogonal mates (HSOLSSOMs) and show that the necessary conditions for the existence of a HSOLSSOM of typeh ⁿ are also sufficient with at most 28 pairs (h, n) of possible exceptions. Research supported in part by NSERC Grant A-5320 for the first author, NSF Grants CCR-9504205 and CCR-9357851 for the second author, and NSFC Grant 19231060-2 for the third author.     

A projection property

E. Corominas introduced recently this notion for posets:P is projective if every mapf fromP ² toP which is order preserving and idempotent (i.e.f(x, x)=x for allx P) is a projection. We consider extensions of this notion to other structures, as well as to maps withn variables. We prove thatn-projectivity forn2 is equivalent to 2-projectivity, with a single exception: the structure has the same morphisms as the collection of congruences associated with a vector space over /2, of dimension at least two. Focusing on relational structures, Arrow's Theorem is introduced as an example. We consider particular types of relational structures: posets, graphs and metric spaces, and discuss for these the specific examples of crowns, cycles and circles.Presented by G. McNultyAuthor supported by the French group PRC Math-Info, and NSERC of Canada.Author supported by NSERC Grant OGP 5407 and FCAR Québec grant Eq 0537.Author supported by NSERC Grant 69-3039.     

Approximate identities from Laguerre functions and singular integrals on the Heisenberg group

Suitably scaled Laguerre functions are an approximate identity for multiplicative convolution with test functions on the half line. As an application, we derive a precise connection between the Mikhlin-type expansion of a singular integral operator on a Heisenberg groupH _n and its natural restriction toH _n modulo the center. Research supported by NSF Grant DMS-9800605 and by NSERC Grant OGP0003017.     

Some universal graphs

It is shown that various classes of graphs have universal elements. In particular, for eachn the class of graphs omitting all paths of lengthn and the class of graphs omitting all circuits of length at leastn possess universal elements in all infinite powers. Research partially supported by Hungarian Science Research Fund No. 1805. Research partially supported by NSERC of Canada Grant #A8948.     

A generalized hypergreedy algorithm for weighted perfect matching

We give a generalization of the hypergreedy algorithm for minimum weight perfect matching on a complete edge weighted graph whose weights satisfy the triangle inequality. With a modified version of this algorithm we obtain a logn-approximate perfect matching heuristic for points in the Euclidean plane, inO(n log² n) time.This research was supported in part by the DIMACS Grant No. NSF-STC88-09648.This research was supported in part by the NSF under Grant No. CCR 88-07518.     

Worst case analysis of greedy and related heuristics for some min-max combinatorial optimization problems

Min-max problems on matroids are NP-hard for a wide variety of matroids. However, greedy type algorithms have data independent worst case performance guarantees, andn-enumerative algorithms yield-optimal solutions ifn is sufficiently close to the rank of the underlying matroid. Data dependent performance guarantees can be obtained for max-min problems over matroids.This research was partially supported by NSERC Grant A5543.     

On separating two simple polygons by a single translation

LetP andQ be two disjoint simple polygons havingn sides each. We present an algorithm which determines whetherQ can be moved by a single translation to a position sufficiently far fromP, and which produces all such motions if they exist. The algorithm runs in timeO(t(n)) wheret(n) is the time needed to triangulate ann-sided polygon. Since Tarjan and Van Wyk have recently shown thatt(n)=O(n log logn) this improves the previous best result for this problem which wasO(n logn) even after triangulation.This research was supported by NSERC Grant A9293, FCAR Grant EQ-1678, and a Killam Fellowship from the Canada Council.     

The Odd-Distance Plane Graph

The vertices of the odd-distance graph are the points of the plane ℝ². Two points are connected by an edge if their Euclidean distance is an odd integer. We prove that the chromatic number of this graph is at least five. We also prove that the odd-distance graph in ℝ² is countably choosable, while such a graph in ℝ³ is not. The research of J. Maňuch was supported in part by MITACS (Mathematics of Information Technology and Complex Systems). The research of M. Rosenfeld was supported in part by the Chancellor Research Grant and the Institute of Technology, UWT. The research of S. Shelah was supported by the United States-Israel Binational Science Foundation (Grant no. 2002323), and by NSF grant No. NSF-DMS 0600940. No. 923 on Shelah’s publication list. The research of L. Stacho was supported in part by NSERC (Natural Science and Engineering Research Council of Canada) grant.     

Exact and limiting distributions of the number of successions in a random permutation

Traditionally the distributions of the number of patterns and successions in a random permutation ofn integers 1,2, ..., andn were studied by combinatorial analysis. In this short article, a simple way based on finite Markov chain imbedding technique is used to obtain the exact distribution of successions on a permutation. This approach also gives a direct proof that the limiting distribution of successions is a Poisson distribution with parameter =1. Furthermore, a direct application of the main result, it also yields the waiting time distribution of a succession.This work was supported in part by the Natural Sciences and Engineering Research Council of Canada under Grant NSERC A-9216, and National Science Council of Republic of China under Grant 85-2121-M-259-003.     

Invariance and efficiency of convex representations

We consider two notions for the representations of convex cones G-representation and lifted-G-representation. The former represents a convex cone as a slice of another; the latter allows in addition, the usage of auxiliary variables in the representation. We first study the basic properties of these representations. We show that some basic properties of convex cones are invariant under one notion of representation but not the other. In particular, we prove that lifted-G-representation is closed under duality when the representing cone is self-dual. We also prove that strict complementarity of a convex optimization problem in conic form is preserved under G-representations. Then we move to study efficiency measures for representations. We evaluate the representations of homogeneous convex cones based on the “smoothness” of the transformations mapping the central path of the representation to the central path of the represented optimization problem. Research of the first author was supported in part by a grant from the Faculty of Mathematics, University of Waterloo and by a Discovery Grant from NSERC. Research of the second author was supported in part by a Discovery Grant from NSERC and a PREA from Ontario, Canada.     

F-controllability and observability of linear retarded systems

The paper gives new results onF-controllability of linear retarded functional differential equations. The concept ofF-controllability, weaker than the approximate controllability in the state space, has been introduced by this author in 1976. In the present paper new conditions are presented which, in the case of systems with one delay, become easily verifiable criteria ofF-controllability. A duality betweenF-controllability and observability is discussed, and several examples are given.This research has been supported in part from NSERC of Canada Grant A-9240 and in part from Grant FCAC 1978/79 and 1979/80 of the Quebec Ministry of Education.     

Assouad-Nagata dimension via Lipschitz extensions

In the first part of the paper we show how to relate several dimension theories (asymptotic dimension with Higson property, asymptotic dimension of Gromov and capacity dimension of Buyalo [7]) to Assouad-Nagata dimension. This is done by applying two functors on the Lipschitz category of metric spaces: microscopic and macroscopic. In the second part we identify (among spaces of finite Assouad-Nagata dimension) spaces of Assouad-Nagata dimension at most n as those for which the n-sphere S ⁿ is a Lipschitz extensor. Large scale and small scale analogues of that result are given. The author was partially supported by Grant No.2004047 from the United States-Israel Binational Science Foundation (BSF), Jerusalem, Israel. The author was supported by Grant AP2004-2494 from the Ministerio de Educacion y Ciencia, Spain. He thanks the Department of Mathematics of University of Tennessee for their hospitality.     

Amenability constants for semilattice algebras

For any finite commutative idempotent semigroup S, a semilattice, we show how to compute the amenability constant of its semigroup algebra ℓ ¹(S). This amenability constant is always of the form 4n+1. We then show that these give lower bounds to amenability constants of certain Banach algebras graded over semilattices. We also give example of a commutative Clifford semigroups G _n whose semigroup algebras ℓ ¹(G _n ) admit amenability constants of the form 41+4(n−1)/n. We also show there is no commutative semigroup whose semigroup algebra has an amenability constant between 5 and 9. N. Spronk’s research was supported by NSERC Grant 312515-05.     

An upper bound on the number of planarK-sets

Given a setS ofn points, a subsetX of sizek is called ak-set if there is a hyperplane that separatesX fromS–X. We prove thatO(nk/log*k) is an upper bound for the number ofk-sets in the plane, thus improving the previous bound of Erdös, Lovász, Simmons, and Strauss by a factor of log*k.The research of J. Pach was supported in part by NSF Grant CCR-8901484 and by Grant OTKA-1418 from the Hungarian Foundation for Scientific Research. The research of W. Steiger and E. Szemerédi was supported in part by NSF Grant CCR-8902522. All authors express gratitude to the NSF DIMACS Center at Rutgers.     

Characterization of Sobolev spaces of arbitrary smoothness using nonstationary tight wavelet frames

In this paper we shall characterize Sobolev spaces of an arbitrary order of smoothness using nonstationary tight wavelet frames for L ₂(ℝ). In particular, we show that a Sobolev space of an arbitrary fixed order of smoothness can be characterized in terms of the weighted ℓ₂-norm of the analysis wavelet coefficient sequences using a fixed compactly supported nonstationary tight wavelet frame in L ₂(ℝ) derived from masks of pseudosplines in [15]. This implies that any compactly supported nonstationary tight wavelet frame of L ₂(ℝ) in [15] can be properly normalized into a pair of dual frames in the corresponding pair of dual Sobolev spaces of an arbitrary fixed order of smoothness. Research supported in part by NSERC Canada under Grant RGP 228051. Research supported in part by Grant R-146-000-060-112 at the National University of Singapore.     

Dimension and enumeration of primitive ideals in quantum algebras

In this paper, we study the primitive ideals of quantum algebras supporting a rational torus action. We first prove a quantum analogue of a Theorem of Dixmier; namely, we show that the Gelfand-Kirillov dimension of primitive factors of various quantum algebras is always even. Next we give a combinatorial criterion for a prime ideal that is invariant under the torus action to be primitive. We use this criterion to obtain a formula for the number of primitive ideals in the algebra of 2×n quantum matrices that are invariant under the action of the torus. Roughly speaking, this can be thought of as giving an enumeration of the points that are invariant under the induced action of the torus in the “variety of 2×n quantum matrices”. The first author thanks NSERC for its generous support. This research was supported by a Marie Curie Intra-European Fellowship within the 6th European Community Framework Programme held at the University of Edinburgh, by a Marie Curie European Reintegration Grant within the 7th European Community Framework Programme and by Leverhulme Research Interchange Grant F/00158/X.