Alternating-Sign Matrices and Domino Tilings (Part I)

We introduce a family of planar regions, called Aztec diamonds, and study tilings of these regions by dominoes. Our main result is that the Aztec diamond of order n has exactly 2 ^n(n+1)/2 domino tilings. In this, the first half of a two-part paper, we give two proofs of this formula. The first proof exploits a connection between domino tilings and the alternating-sign matrices of Mills, Robbins, and Rumsey. In particular, a domino tiling of an Aztec diamond corresponds to a compatible pair of alternating-sign matrices. The second proof of our formula uses monotone triangles, which constitute another form taken by alternating-sign matrices; by assigning each monotone triangle a suitable weight, we can count domino tilings of an Aztec diamond.     

The factorization of the permanent of a matrix with minimal rank in prime characteristic

It is known that any square matrix A of size n over a field of prime characteristic p that has rank less than n/(p − 1) has a permanent that is zero. We give a new proof involving the invariant X _p . There are always matrices of any larger rank with non-zero permanents. It is shown that when the rank of A is exactly n/(p − 1), its permanent may be factorized into two functions involving X _p .     

Symmetric latin square and complete graph analogues of the evans conjecture

With the proof of the Evans conjecture, it was established that any partial latin square of side n with a most n ? 1 nonempty cells can be completed to a latin square of side n. In this article we prove an analogous result for symmetric latin squares: a partial symmetric latin square of side n with an admissible diagonal and at most n ? 1 nonempty cells can be completed to a symmetric latin square of side n. We also characterize those partial symmetric latin squares of side n with exactly n or n + 1 nonempty cells which cannot be completed. From these results we deduce theorems about completing edge-colorings of complete graphs K_2m and K_{2m ? 1} with 2m ? 1 colors, with m + 1 or fewer edges getting prescribed colors. © 1994 John Wiley & Sons, Inc.     

Some New Results on Circulant Weighing Matrices

We obtain a few structural theorems for circulant weighing matrices whose weight is the square of a prime number. Our results provide new schemes to search for these objects. We also establish the existence status of several previously open cases of circulant weighing matrices. More specifically we show their nonexistence for the parameter pairs (n, k) (here n is the order of the matrix and k its weight) = (147, 49), (125, 25), (200, 25), (55, 25), (95, 25), (133, 49), (195, 25), (11 w, 121) for w < 62.     

Self-affine Lattice Reptiles with Two Pieces in IRn

We prove that for every number n ≥ 1, there is a finite number of affine types of self-affine lattice tilings in ?ⁿ, such that the expansion carries each tile onto the union of two tiles.     

Null ideals and spanning ranks of matrices

Let Rbe a commutative ring and A?M _m×n . The spanning rank of Ais the smallest positive integer s for which A=PQ(m×s s×n) The spanning rank of the zero matrix is set equal to zero. If Ris a field, then the spanning rank of Ais just the classical rank of A. In the first section of this paper, various theorems and examples are given which indicate how much of the classical theory of rank is still valid for spanning rank over a commutative ring. If A= PQ(n×s s×n) is a spanning rank factorization of a square matrix and D= QP, then Dis called a spanning rank partner of A. In the second part of this paper, the null ideals N _Aand N _Dof Aand Drespectively are compared. For instance, we show N _A=N _Dif s= nand N _A= XN _Dif s<nwhenever Ris a PIDand A≠0. This result sometimes (e.g. s<<n) makes the computation of N _Aeasy.     

Variations on Tilings in the Manhattan Metric

We investigate tilings of the integer lattice in the Euclidean n-dimensional space. The tiles considered here are the union of spheres defined by the Manhattan metric. We give a necessary condition for the existence of such a tiling for Z ⁿ when n 2. We prove that this condition is sufficient when n=2. Finally, we give some tilings of Z ⁿ when n 3.     

Symmetry classes of spanning trees of Aztec diamonds and perfect matchings of odd squares with a unit hole

We say that two graphs are similar if their adjacency matrices are similar matrices. We show that the square grid G _n of order n is similar to the disjoint union of two copies of the quartered Aztec diamond QAD _n−1 of order n−1 with the path P _n ⁽²⁾ on n vertices having edge weights equal to 2. Our proof is based on an explicit change of basis in the vector space on which the adjacency matrix acts. The arguments verifying that this change of basis works are combinatorial. It follows in particular that the characteristic polynomials of the above graphs satisfy the equality P(G _n )=P(P _n ⁽²⁾)[P(QAD _n−1)]². On the one hand, this provides a combinatorial explanation for the “squarishness” of the characteristic polynomial of the square grid—i.e., that it is a perfect square, up to a factor of relatively small degree. On the other hand, as formulas for the characteristic polynomials of the path and the square grid are well known, our equality determines the characteristic polynomial of the quartered Aztec diamond. In turn, the latter allows computing the number of spanning trees of quartered Aztec diamonds. We present and analyze three more families of graphs that share the above described “linear squarishness” property of square grids: odd Aztec diamonds, mixed Aztec diamonds, and Aztec pillowcases—graphs obtained from two copies of an Aztec diamond by identifying the corresponding vertices on their convex hulls. We apply the above results to enumerate all the symmetry classes of spanning trees of the even Aztec diamonds, and all the symmetry classes not involving rotations of the spanning trees of odd and mixed Aztec diamonds. We also enumerate all but the base case of the symmetry classes of perfect matchings of odd square grids with the central vertex removed. In addition, we obtain a product formula for the number of spanning trees of Aztec pillowcases. Research supported in part by NSF grant DMS-0500616.     

On the Number of Tilings of a Square by Rectangles

We develop a recursive formula for counting the number of rectangulations of a square, i.e., the number of combinatorially distinct tilings of a square by rectangles. Our formula specializes to give a formula counting generic rectangulations, as analyzed by Reading in [5]. Our computations agree with [5] as far as was calculated and extend to the non-generic case. An interesting feature of the number of rectangulations is that it appears to have an 8-fold periodicity modulo 2. We verify this periodicity for small values of n, but the general result remains elusive, perhaps hinting at some unseen structure on the space of rectangulations, analogous to Reading’s discovery that generic rectangulations are in 1–1 correspondence with a certain class of permutations. Finally, we use discrete Morse theory to show that the space of tilings by ≤ n rectangles is homotopy-equivalent to a wedge of some number of (n?1)-dimensional spheres. Combining this result with the formulae for the number of tilings, the exact homotopy type is computed for n ≤ 28.     

Uniform estimates for spherical functions on complex semisimple Lie groups

We prove new estimates for spherical functions and their derivatives on complex semisimple Lie groups, establishing uniform polynomial decay in the spectral parameter. This improves the customary estimate arising from Harish-Chandra's series expansion, which gives only a polynomial growth estimate in the spectral parameter. In particular, for arbitrary positive-definite spherical functions on higher rank complex simple groups, we establish estimates for which are of the form in the spectral parameter and have uniform exponential decay in regular directions in the group variable a _t . Here is an explicit constant depending on G, and may be singular, for instance.?The uniformity of the estimates is the crucial ingredient needed in order to apply classical spectral methods and Littlewood—Paley—Stein square functions to the analysis of singular integrals in this context. To illustrate their utility, we prove maximal inequalities in L ^p for singular sphere averages on complex semisimple Lie groups for all p in . We use these to establish singular differentiation theorems and pointwise ergodic theorems in L ^p for the corresponding singular spherical averages on locally symmetric spaces, as well as for more general measure preserving actions. Submitted: May 2000, Revised version: October 2000.     

Cube-tilings of ℝ n and nonlinear codesand nonlinear codes

Families of nonlattice tilings of ℝ ⁿ by unit cubes are constructed. These tilings are specializations of certain families of nonlinear codes overGF(2). These cube-tilings provide building blocks for the construction of cube-tilings such that no two cubes have a high-dimensional face in common. We construct cube-tilings of ℝ ⁿ such that no two cubes have a common face of dimension exceeding .     

Combinatorial obstructions to the lifting of weaving diagrams

This paper deals with various connections of oriented matroids [3] and weaving diagrams of lines in space [9], [16], [27]. We encode the litability problem of a particular weaving diagramD onn lines by the realizability problem of a partial oriented matroid χ _D with2n elements in rank 4. We prove that the occurrence of a certain substructure inD implies that χD is noneuclidean in the sense of Edmonds, Fukuda, and Mandel [12], [14]. Using this criterion we construct an infinite class of minor-minimal noneuclidean oriented matroids in rank 4. Finally, we give an easy algebraic proof for the nonliftability of the alternating weaving diagram on a bipartite grid of 4×4 lines [16].     

n-Homeohedral types of tilings

For each n, there are only finitely many topological types of normal n-homeohedral tilings, and for every such type there is an n-isohedral representative which displays essentially the same symmetries.     

Divisibility in certain automorphism groups

We study solvability of equations of the form x ⁿ = g in the groups of order automorphisms of archimedean-complete totally ordered groups of rank 2. We determine exactly which automorphisms of the unique abelian such group have square roots, and we describe all automorphisms of the general ones.     

New negative Latin square type partial difference sets in nonelementary abelian 2-groups and 3-groups

A partial difference set having parameters (n ², r(n − 1), n + r ² − 3r, r ² − r) is called a Latin square type partial difference set, while a partial difference set having parameters (n ², r(n + 1), − n + r ² + 3r, r ² + r) is called a negative Latin square type partial difference set. Nearly all known constructions of negative Latin square partial difference sets are in elementary abelian groups. In this paper, we develop three product theorems that construct negative Latin square type partial difference sets and Latin square type partial difference sets in direct products of abelian groups G and G′ when these groups have certain Latin square or negative Latin square type partial difference sets. Using these product theorems, we can construct negative Latin square type partial difference sets in groups of the form where the s _i are nonnegative integers and s ₀ + s ₁ ≥ 1. Another significant corollary to these theorems are constructions of two infinite families of negative Latin square type partial difference sets in 3-groups of the form for nonnegative integers s _i . Several constructions of Latin square type PDSs are also given in p-groups for all primes p. We will then briefly indicate how some of these results relate to amorphic association schemes. In particular, we construct amorphic association schemes with 4 classes using negative Latin square type graphs in many nonelementary abelian 2-groups; we also use negative Latin square type graphs whose underlying sets can be elementary abelian 3-groups or nonelementary abelian 3-groups to form 3-class amorphic association schemes.      

Non-periodic Tilings of ? n by Crosses

An n-dimensional cross consists of 2n+1 unit cubes: the “central” cube and reflections in all its faces. A tiling by crosses is called a Z-tiling if each cross is centered at a point with integer coordinates. Periodic tilings of ℝ ⁿ by crosses have been constructed by several authors for all n∈N. No non-periodic tiling of ℝ ⁿ by crosses has been found so far. We prove that if 2n+1 is not a prime, then the total number of non-periodic Z-tilings of ℝ ⁿ by crosses is 2^à₀2^{\aleph _{0}} while the total number of periodic Z-tilings is only ℵ₀. In a sharp contrast to this result we show that any two tilings of ℝ ⁿ ,n=2,3, by crosses are congruent. We conjecture that this is the case not only for n=2,3, but for all n where 2n+1 is a prime.     

A variational principle for domino tilings

We formulate and prove a variational principle (in the sense of thermodynamics) for random domino tilings, or equivalently for the dimer model on a square grid. This principle states that a typical tiling of an arbitrary finite region can be described by a function that maximizes an entropy integral. We associate an entropy to every sort of local behavior domino tilings can exhibit, and prove that almost all tilings lie within (for an appropriate metric) of the unique entropy-maximizing solution. This gives a solution to the dimer problem with fully general boundary conditions, thereby resolving an issue first raised by Kasteleyn. Our methods also apply to dimer models on other grids and their associated tiling models, such as tilings of the plane by three orientations of unit lozenges.

     

Local ergodic theorems for K-spherical averages on the Heisenberg group

Given a Gelfand pair where is the Heisenberg group and K is a compact subgroup of the unitary group U(n) we consider the sphere and ball averages of certain K-invariant measures on . We prove local ergodic theorems for these measures when . We also consider averages over annuli in the case of reduced Heisenberg group and show that when the functions have zero mean value the maximal function associated to the annulus averages behave better than the spherical maximal function. We use square function arguments which require several properties of the K-spherical functions. Received September 1, 1998; in final form July 9, 1999     

Null spaces and ranges for the classical and spherical Radon transforms

Let R be the classical Radon transform that integrates a function over hyperplanes in Rⁿ and let SM be the transform that integrates a function over spheres containing the origin in Rⁿ. We prove continuity results for both transforms and explicitly give the null space of R for a class of square integrable functions on the exterior of a ball in Rⁿ as well as the null space of SM for square integrable functions on a ball. We show SM: L²(Rⁿ) → L²(Rⁿ) is one-one, and we characterize the range of SM on classes of smooth functions and square integrable functions by certain moment conditions. If g(x) is a Schwartz function on Rⁿ that is zero to infinite order at x = 0, we prove moment conditions sufficient for g to be in the range of SM(C^∞(Rⁿ)). We apply our results on SM to existence and uniqueness theorems for solutions to a characteristic initial value problem for the Darboux partial differential equation.