Edge-isoperimetric inequalities in the grid

The grid graph is the graph on [k] ⁿ ={0,...,k–1} ⁿ in whichx=(x _i ) ₁ ⁿ is joined toy=(y _i ) ₁ ⁿ if for somei we have |x _i –y _i |=1 andx _j =y _j for allji. In this paper we give a lower bound for the number of edges between a subset of [k] ⁿ of given cardinality and its complement. The bound we obtain is essentially best possible. In particular, we show that ifA[k] ⁿ satisfiesk ⁿ /4|A|3k ⁿ /4 then there are at leastk ^n–1 edges betweenA and its complement.Our result is apparently the first example of an isoperimetric inequality for which the extremal sets do not form a nested family.We also give a best possible upper bound for the number of edges spanned by a subset of [k] ⁿ of given cardinality. In particular, forr=1,...,k we show that ifA[k] ⁿ satisfies |A|r ⁿ then the subgraph of [k] ⁿ induced byA has average degree at most 2n(1–1/r).Research partially supported by NSF Grant DMS-8806097     

On the Chromatic Number of the Square of the Kneser Graph <Emphasis Type="Italic">K</Emphasis>(2<Emphasis Type="Italic">k</Emphasis>+1, <Emphasis Type="Italic">k</Emphasis>)

The Kneser graph K(n, k) is the graph whose vertices are the k-element subsets of an n-element set, with two vertices adjacent if the sets are disjoint. The chromatic number of the Kneser graph K(n, k) is n–2k+2. Zoltán Füredi raised the question of determining the chromatic number of the square of the Kneser graph, where the square of a graph is the graph obtained by adding edges joining vertices at distance at most 2. We prove that (K²(2k+1, k))4k when k is odd and (K²(2k+1, k))4k+2 when k is even. Also, we use intersecting families of sets to prove lower bounds on (K²(2k+1, k)), and we find the exact maximum size of an intersecting family of 4-sets in a 9-element set such that no two members of the family share three elements.This work was partially supported by NSF grant DMS-0099608Final version received: April 23, 2003     

Homotopy of Non-Modular Partitions and the Whitehouse Module

We present a class of subposets of the partition lattice _n with the following property: The order complex is homotopy equivalent to the order complex of _n – 1, and the S _n -module structure of the homology coincides with a recently discovered lifting of the S _n – 1-action on the homology of _n – 1. This is the Whitehouse representation on Robinson's space of fully-grown trees, and has also appeared in work of Getzler and Kapranov, Mathieu, Hanlon and Stanley, and Babson et al.One example is the subposet P _n ⁿ – 1 of the lattice of set partitions _n , obtained by removing all elements with a unique nontrivial block. More generally, for 2 k n – 1, let Q _n ^k denote the subposet of the partition lattice _n obtained by removing all elements with a unique nontrivial block of size equal to k, and let P _n ^k = _{i = 2} ^k Q _n ⁱ . We show that P _n ^k is Cohen-Macaulay, and that P _n ^k and Q _n ^k are both homotopy equivalent to a wedge of spheres of dimension (n – 4), with Betti number . The posets Q _n ^k are neither shellable nor Cohen-Macaulay. We show that the S _n -module structure of the homology generalises the Whitehouse module in a simple way.We also present a short proof of the well-known result that rank-selection in a poset preserves the Cohen-Macaulay property.     

Multiple lattice packings and coverings of spheres

Let be a lattice inR ⁿ . Consider the systemS of unit spheres centered at the lattice points of .S is called ak-fold lattice packing (covering) if each point inR ⁿ lies in at most (least)k of the open (closed) spheres ofS. Letd _k ⁿ (D _k ⁿ ) be the density of the closest (thinnest)k-fold lattice packing (covering) ofR ⁿ . After dealing several cases left by G. Fejes Tóth and A. Florian, we have concluded thatd _k ⁿ >kd ₁ ⁿ for all (n, k) (n2,k2) except (2, 2), (2, 3), (2, 4); andD _k ³ <k D ₁ ³ for allk2.     

Invariance Principle Under Self-Normalization for Nonidentically Distributed Random Variables

Let V _n ^–1 _n be the adaptive process of self-normalized partial sums S _k of independent random variables X _i , defined by linear interpolation between the points (V _k ²/V _n ²,S _k /V _n ), kn, where V _k ²= _ik X _i ². We prove that if the X _k 's are symmetric, V _n ^–1 _n converges weakly to the Brownian motion W in each Hölder space supporting W if and only if V _n ^–1 max _kn |X _k |=o _P (1). We give some partial extension to the non symmetric case.     

On a Turán type problem of Erdös

Let L ^k be the graph formed by the lowest three levels of the Boolean lattice B _k , i.e.,V(L ^k )={0, 1,...,k, 12, 13,..., (k–1)k} and 0is connected toi for all 1ik, andij is connected toi andj (1i<jk).It is proved that if a graph G overn vertices has at leastk ^3/2 n ^3/2 edges, then it contains a copy of L ^k .Research supported in part by the Hungarian National Science Foundation under Grant No. 1812     

Random Walks Crossing High Level Curved Boundaries

Let {S _n} be a random walk, generated by i.i.d. increments X _i which drifts weakly to in the sense that as n . Suppose k0, k1, and E|X ₁|^1\k = if k>1. Then we show that the probability that S. crosses the curve nan ^K before it crosses the curve n –an ^k tends to 1 as a . This intuitively plausible result is not true for k = 1, however, and for 1/2 <k<1, the converse results are not true in general, either. More general boundaries g(n) than g(n) = n ^k are also considered, and we also prove similar results for first passages out of regions like { (n, y): n1, |y| (a + n) ^k } as a .     

Random walks supported on random points ofZ/nZ

Summary This paper considers random walks on the integers modn supported onk points and asks how long does it take for these walks to get close to uniformly distributed. Ifk is a constant, Greenhalgh showed that at least some constant timesn ^2/(k–1) steps are necessary to make the distance of the random walk from the uniform distribution small; here we show that ifn is prime, some constant timesn ^2/(k–1) steps suffice to make this distance small for almost all choices ofk points. The proof uses the Upper Bound Lemma of Diaconis and Shahshahani and some averaging techniques. This paper also explores some cases wherek varies withn. In particular, ifk=(logn) ^a , we find different kinds of results for different values ofa, and these results disprove a conjecture of Aldous and Diaconis.Research Supported in Part by a Rackham Faculty Fellowship at the University of Michigan     

On convergence subsystems of orthonormal systems

It is proved that for any sequence {R _k} _k=1 of real numbers satisfyingR _kk (k1) andR _k=o(k log₂ k),k, there exists an orthonormal system {n _k(x)} _n=1 ,x (0;1), such that none of its subsystems {n _k(x)} _k=1 withn _kR_k (k1) is a convergence subsystem.     

Bessel Potentials with Logarithmic Components and Sobolev-Type Embeddings

In a recent paper Edmunds, Gurka, and Opic [5] showed that Sobolev spaces of order k, based on the Zygmund spaces L ^n/k (log L) (R ⁿ ), are continuously embedded into L (R ⁿ ) if > 1/p, p n/k. In this paper we replace L ^n/k (log L) (R ⁿ ) by the Lebesgue space L ^n/k (R ⁿ ) and increase the smoothness of the functions involved by a "logarithmic" order > 1/p to obtain the continuous embedding into L (R ⁿ ). Both approaches turn out to be equivalent. We also derive results of Trudinger-type [16] on embeddings into Orlicz spaces in the limit case k = n/p as well as results of Brézis-Wainger-type [2] on almost Lipschitz continuity in the superlimiting case k = n/p + 1.     

Cylindricity of tangent bundles of strongly parabolic metrics and strongly parabolic surfaces

It is proved that if the intrinsic zero-index of the Sasaki metric of a tangent bundleTM ⁿ isk, thenk is even andM ⁿ is the metric product of a Riemannian manifoldM ^n–k/2 by a Euclidean spaceE ^k/2, whileTM ⁿ is the metric product ofTM ^n–k/2 byE ^k . An expression is obtained for the second fundamental forms of the imbeddingTF ^l TM ⁿ in terms of the second fundamental forms of the imbeddingF ^l M ⁿ and the curvature tensor ofM ⁿ . It is proved thatTF ^l is totally geodesic inTM ⁿ if and only ifF ^l is totally geodesic inM ⁿ .Translated from Ukrainskií Geometricheskií Sbornik, Issue 28, 1985, pp. 12–32.     

Some simple in-place merging algorithms

The theoretical presentation and analysis is given for two families of simple in-place merging algorithms and their limiting cases. The first family merges stably inO(k·n) time andO(n ^1/k ) additional space with a limiting case running inO(n logn) time and constant space. The second family merges unstably inO (k ·n) time andO(log ^k n) space with a limiting case running inO(nG(n)) time and constant space. HereG(n) is the leastk such thatF(k) n whereF(0)=1 andF(i)=2 ^F(i–1) fori1. Each algorithm gives rise to a corresponding merge sort.     

Algorithms for graphs of bounded treewidth via orthogonal range searching

We show that, for any fixed constant k3, the sum of the distances between all pairs of vertices of an abstract graph with n vertices and treewidth at most k can be computed in O(nlog^k−1n) time.We also show that, for any fixed constant k2, the dilation of a geometric graph (i.e., a graph drawn in the plane with straight-line segments) with n vertices and treewidth at most k can be computed in O(nlog^k+1n) expected time. The dilation (or stretch-factor) of a geometric graph is defined as the largest ratio, taken over all pairs of vertices, between the distance measured along the graph and the Euclidean distance.The algorithms for both problems are based on the same principle: data structures for orthogonal range searching in bounded dimension provide a compact representation of distances in abstract graphs of bounded treewidth.     

Powers of Sign Portraits of Real Matrices

The sign portrait S of a real n× n matrix is a matrix over the semiring with elements 0, 1, -1, and , where symbolizes indeterminateness. It is proved that if k is the least positive integer such that all the entries of S ^k are equal to , then k 2n ² – 3n + 2, and this bound is sharp. Bibliography: 6 titles.     

On the number of alignments ofk sequences

Numerous studies by molecular biologists concern the relationships between several long DNA sequences, which are listed in rows with some gaps inserted and with similar positions aligned vertically. This motivates our interest in estimating the number of possible arrangements of such sequences. We say that ak sequence alignment of sizen is obtained by inserting some (or no) 0's intok sequences ofn 1's so that every sequence has the same length and so that there is no position which is 0 in allk sequences. We show by a combinatorial argument that for any fixedk1, the numberf(k, n) ofk alignments of lengthn grows like (c _k ) ⁿ as n , wherec _k = (2^1/k – 1) ^-k . A multi-dimensional saddle-point method is used to give a more precise estimate forf(k, n). Research supported in part by the National Science FoundationResearch supported in part by the System Development FoundationResearch supported in part by the National Institute of Health     

Gauss-Tchebycheff quadrature formulas

Summary It is well known that the Tchebycheff weight function (1-x ²)^–1/2 is the only weight function (up to a linear transformation) for which then point Gauss quadrature formula has equal weights for alln. In this paper we describe explicitly all weight functions which have the property that then _k-point Gauss quadrature formula has equal weights for allk, where (n _k),n ₁<n ₂<..., is an arbitrary subsequence of . Furthermore results on the possibility of Tchebycheff quadrature on several intervals are given.     

Varieties of lattice ordered groups that contain no non-abelian o-groups are solvable

It is shown that the variety _n of lattice ordered groups defined by the identity x ⁿ y ⁿ =y ⁿ x ⁿ , where n is the product of k (not necessarily distinct primes) is contained in the (k+1)st power A ^k+1 of the variety A of all Abelian lattice ordered groups. This implies, in particular, that _n is solvable class k + 1. It is further established that any variety V of lattice ordered groups which contains no non-Abelian totally ordered groups is necessarily contained in _n , for some positive integer n.This work was supported in part, by NSERC Grant A4044.     

The k-record processes are i.i.d.

Let X ₁, X ₂, ... be i.i.d. positive random variables, and let _n be the initial rank of X _n (that is, the rank of X _n among X ₁, ..., X _n). Those observations whose initial rank is k are collected into a point process N ^k on ⁺, called the k-record process. The fact that {itN^k; k=1, 2, ... are independent and identically distributed point processes is the main result of the paper. The proof, based on martingales, is very rapid. We also show that given N ¹, ..., N ^k, the lifetimes in rank k of all observations of initial rank at most k are independent geometric random variables.These results are generalised to continuous time, where the analogue of the i.i.d. sequence is a time-space Poisson process. Initially, we think of this Poisson process as having values in ⁺, but subsequently we extend to Poisson processes with values in more general Polish spaces (for example, Brownian excursion space) where ranking is performed using real-valued attributes.     

A characterization of probability distributions by moments of sums of independent random variables

In this paper we investigate the conditions under which the distribution of i.i.d. random variables{X _k } _k=1 is determined by the sequence of momentsa _n =E| _k=1 ⁿ X _k | ^p (n=1, 2,...), where positivep is fixed.     

Manifolds with involution

In this paper, we determine the groups (k _i are odd), (k _i are odd and (k _i are even andn>k _l ), (k _i are even andn>k _l ), (k _i are even andn>k _l ,k _l 12),J _n ^1,2,J _n ^2,3,J _n ^1,4. And we obtain the relation Im _n ^k =J _n ^l,k .