Lattices on simplicial partitions

In this paper, (d+1)-pencil lattices on simplicial partitions in R^d are studied. The barycentric approach naturally extends the lattice from a simplex to a simplicial partition, providing a continuous piecewise polynomial interpolant over the extended lattice. The number of degrees of freedom is equal to the number of vertices of the simplicial partition. The constructive proof of this fact leads to an efficient computer algorithm for the design of a lattice.     

Orthogonal splitting and class numbers of quadratic forms

Orthogonal splitting for lattices on quadratic spaces over algebraic number fields is studied. It is seen that if the rank of a lattice is sufficiently large, then its spinor genus must contain a decomposable lattice. Also, splitting theory is used to obtain a lower bound for the class number of a lattice (in the definite case) in terms of its rank, via the partition function.     

The Least-Perimeter Partition of a Sphere into Four Equal Areas

We prove that the least-perimeter partition of the sphere into four regions of equal area is a tetrahedral partition.     

Graphical algebras — a new approach to congruence lattices

In 1970, H. Werner considered the question of which sublattices of partition lattices are congruence lattices for an algebra on the underlying set of the partition lattices. He showed that a complete sublattice of a partition lattice is a congruence lattice if and only if it is closed under a new operation called graphical composition. We study the properties of this new operation, viewed as an operation on an abstract lattice. We obtain some necessary properties, and we also obtain some sufficient conditions for an operation on an abstract lattice L to be this operation on a congruence lattice isomorphic to L. We use this result to give a new proof of Grätzer and Schmidt’s result that any algebraic lattice occurs as a congruence lattice.     

State matrix recursion method and monomer–dimer problem

The exact enumeration of pure dimer coverings on the square lattice was obtained by Kasteleyn, Temperley and Fisher in 1961. In this paper, we consider the monomer–dimer covering problem (allowing multiple monomers) which is an outstanding unsolved problem in lattice statistics. We have developed the state matrix recursion method that allows us to compute the number of monomer–dimer coverings and to know the partition function with monomer and dimer activities. This method proceeds with a recurrence relation of so-called state matrices of large size. The enumeration problem of pure dimer coverings and dimer coverings with single boundary monomer is revisited in partition function forms. We also provide the number of dimer coverings with multiple vacant sites. The related Hosoya index and the asymptotic behavior of its growth rate are considered. Lastly, we apply this method to the enumeration study of domino tilings of Aztec diamonds and more generalized regions, so-called Aztec octagons and multi-deficient Aztec octagons.     

Barycentric coordinates for Lagrange interpolation over lattices on a simplex

In this paper, a (d?+?1)-pencil lattice on a simplex in ${\mathbb{R}}^d$ is studied. The lattice points are explicitly given in barycentric coordinates. This enables the construction and the efficient evaluation of the Lagrange interpolating polynomial over a lattice on a simplex. Also, the barycentric representation, based on shape parameters, turns out to be appropriate for the lattice extension from a simplex to a simplicial partition.     

A TQFT of Turaev–Viro Type on Shaped Triangulations

A shaped triangulation is a finite triangulation of an oriented pseudo-three-manifold where each tetrahedron carries dihedral angles of an ideal hyperbolic tetrahedron. To each shaped triangulation, we associate a quantum partition function in the form of an absolutely convergent state integral which is invariant under shaped 3–2 Pachner moves and invariant with respect to shape gauge transformations generated by total dihedral angles around internal edges through the Neumann–Zagier Poisson bracket. Similarly to Turaev–Viro theory, the state variables live on edges of the triangulation but take their values on the whole real axis. The tetrahedral weight functions are composed of three hyperbolic gamma functions in a way that they enjoy a manifest tetrahedral symmetry. We conjecture that for shaped triangulations of closed three-manifolds, our partition function is twice the absolute value squared of the partition function of Techmüller TQFT defined by Andersen and Kashaev. This is similar to the known relationship between the Turaev–Viro and the Witten–Reshetikhin–Turaev invariants of three-manifolds. We also discuss interpretations of our construction in terms of three-dimensional supersymmetric field theories related to triangulated three-dimensional manifolds.     

Generating functions for vector partition functions and a basic recurrence relation

ABSTRACT

We define a generalized vector partition function and derive an identity for the generating series of such functions associated with solutions to basic recurrence relations of combinatorial analysis. As a consequence we obtain the generating function of the number of generalized lattice paths and a new version of the Chaundy-Bullard identity for the vector partition function.     

Cohen-Macaulay types of subgroup lattices of finite abelianp-groups

For a minimal free resolution of a Stanley-Reisner ring constructed from the order complex of a modular lattice. T. Hibi showed that its last Betti number (called the Cohen-Macaulay type) is computed by means of the Möbius function of the given modular lattice. Using this result, we consider the Stanley-Reisner ring of the subgroup lattice of a finite abelianp-group associated with a given partition, and show that its Cohen-Macaulay type is a polynomial inp with integer coefficients.     

A reduction of lattice tiling by translates of a cubical cluster

A cluster is the union of a finite number of cubes from the standard partition ofn-dimensional Euclidean space into unit cubes. If there is lattice tiling by translates of a cluster, then must there be a lattice tiling by translates of the cluster in which the translation vectors have only integer coordinates? In this article we prove that if the interior of the cluster is connected and the dimension is at most three, then the answer is affirmative.     

Chain enumeration and non-crossing partitions

A formula is established for the number of chains with designated ranks in the non-crossing partition lattice. As corollaries, certain results of Kreweras are obtained. Non-crossing partitions are then generalized in two ways, and similar problems are solved.     

Symmetric quadrature rules for tetrahedra based on a cubic close-packed lattice arrangement

A family of quadrature rules for integration over tetrahedral volumes is developed. The underlying structure of the rules is based on the cubic close-packed (CCP) lattice arrangement using 1, 4, 10, 20, 35, and 56 quadrature points. The rules are characterized by rapid convergence, positive weights, and symmetry. Each rule is an optimal approximation in the sense that lower-order terms have zero contribution to the truncation error and the leading-order error term is minimized. Quadrature formulas up to order 9 are presented with relevant numerical examples.     

C 1 Quintic Splines on Type-4 Tetrahedral Partitions

Starting with a partition of a rectangular box into subboxes, it is shown how to construct a natural tetrahedral (type-4) partition and associated trivariate C ¹ quintic polynomial spline spaces with a variety of useful properties, including stable local bases and full approximation power. It is also shown how the spaces can be used to solve certain Hermite and Lagrange interpolation problems.     

Symmetries of quadratic form classes and of quadratic surd continued fractions. Part I: A Poincaré tiling of the de Sitter world

The problem of classifying the indefinite binary quadratic forms with integer coefficients is solved by introducing a special partition of the de Sitter world, where the coefficients of the forms lie, into separate domains. Under the action of the special linear group acting on the integer plane lattice, each class of indefinite forms has a well-defined finite number of representatives inside each such domain. In the second part, we will show how to obtain the symmetry type of a class and also the number of its points in all domains from a single representative of that class.     

The many aspects of counting lattice points in polytopes

A wide variety of topics in pure and applied mathematics involve the problem of counting the number of lattice points inside a convex bounded polyhedron, for short called a polytope. Applications range from the very pure (number theory, toric Hilbert functions, Kostant’s partition function in representation theory) to the most applied (cryptography, integer programming, contingency tables). This paper is a survey of this problem and its applications. We review the basic structure theorems about this type of counting problem. Perhaps the most famous special case is the theory of Ehrhart polynomials, introduced in the 1960s by Eugène Ehrhart. These polynomials count the number of lattice points in the different integral dilations of an integral convex polytope. We discuss recent algorithmic solutions to this problem and conclude with a look at what happens when trying to count lattice points in more complicated regions of space.     

Modularity in random regular graphs and lattices

Given a graph G, the modularity of a partition of the vertex set measures the extent to which edge density is higher within parts than between parts; and the modularity of G is the maximum modularity of a partition.We give an upper bound on the modularity of r-regular graphs as a function of the edge expansion (or isoperimetric number) under the restriction that each part in our partition has a sub-linear numbers of vertices. This leads to results for random r-regular graphs. In particular we show the modularity of a random cubic graph partitioned into sub-linear parts is almost surely in the interval (0.66, 0.88).The modularity of a complete rectangular section of the integer lattice in a fixed dimension was estimated in Guimer et. al. [R. Guimerà, M. Sales-Pardo and L.A. Amaral, Modularity from fluctuations in random graphs and complex networks, Phys. Rev. E 70 (2) (2004) 025101]. We extend this result to any subgraph of such a lattice, and indeed to more general graphs.     

A Simple Proof of a Conjecture of Simion

Simion had a unimodality conjecture concerning the number of lattice paths in a rectangular grid with the Ferrers diagram of a partition removed. Hildebrand recently showed the stronger result that these numbers are log concave. Here we present a simple proof of Hildebrand's result.     

Region configurations for realizability of lattice Piecewise-Linear models

Continuous Piecewise-Linear (PWL) functions can be represented by a scheme that selects adequately the linear components of the function without considering explicitly the boundaries. The representation method based on the Lattice Theory, that we call the lattice PWL model, is a form that fits that scheme. In this paper, two domain partitions are proposed that give rise to region configurations practically meaningful for the realizability of lattice models. In one of those partitions, each region is uniquely determined by one of the linear function. The other region configuration is derived from the rearrangement in ascending order of the linear components. Both configurations are discussed and connected with the domain partition generated by the set of boundaries, frequently considered when dealing with PWL functions. The realization method of lattice models is adapted to the three region configurations, comparing the efficiency of the resulting versions.     

Planar lattice gases with nearest-neighbor exclusion

We discuss the hard-hexagon and hard-square problems, as well as the corresponding problem on the honeycomb lattice. The case when the activity is unity is of interest to combinatorialists, being the problem of counting binary matrices with no two adjacent 1's. For this case, we use the powerful corner transfer matrix method to numerically evaluate the partition function per site, density and some near-neighbor correlations to high accuracy. In particular, for the square lattice, we obtain the partition function per site to 43 decimal places.     

Monoid intervals in lattices of clones

Suppose A is a finite set. For every clone C over A, the family C⁽¹⁾ of all unary functions in C is a monoid of transformations of the set A. We study how the lattice of clones is partitioned into intervals, where two clones belong to the same partition iff they have the same monoids of unary functions. The problem of Szendrei concerning the power of such intervals is investigated. We give new examples of intervals which are continual, one-element, and finite but not one-element. Moreover, it is proved that every lattice that is not more than a direct product of countably many finite chains is isomorphic to some interval in the lattice of clones, establishing, in passing, the number of E-minimal algebras on a finite set. Translated fromAlgebra i Logika, Vol. 34, No. 3, pp. 288-310, May-June, 1995.