Average site perimeter of directed animals on the two-dimensional lattices

We introduce new combinatorial (bijective) methods that enable us to compute the average value of three parameters of directed animals of a given area, including the site perimeter. Our results cover directed animals of any one-line source on the square lattice and its bounded variants, and we give counterparts for most of them in the triangular lattices. We thus prove conjectures by Conway and Le Borgne. The techniques used are based on Viennot’s correspondence between directed animals and heaps of pieces (or elements of a partially commutative monoid).     

Haruspicy 3: The anisotropic generating function of directed bond-animals is not D-finite

While directed site-animals have been solved on several lattices, directed bond-animals remain unsolved on any nontrivial lattice. In this paper we demonstrate that the anisotropic generating function of directed bond-animals on the square lattice is fundamentally different from that of directed site-animals in that it is not differentiably finite. We also extend this result to directed bond-animals on hypercubic lattices. This indicates that directed bond-animals are unlikely to be solved by similar methods to those used in the solution of directed site-animals. It also implies that a solution cannot be conjectured using computer packages such as Gfun [A Maple package developed by B. Salvy, P. Zimmermann, E. Murray at INRIA, France, available from http://algo.inria.fr/libraries/ at time of submission; B. Salvy, P. Zimmermann, Gfun: A Maple package for the manipulation of generating and holonomic functions in one variable, ACM Trans. Math. Software 20 (2) (1994) 163-177] or differential approximants [A.J. Guttmann, Asymptotic analysis of coefficients, in: C. Domb, J. Lebowitz (Eds.), Phase Transit. Crit. Phenom., vol. 13, Academic Press, London, 1989, pp. 1-234, programs available from http://www.ms.unimelb.edu.au/~tonyg].     

Families of prudent self-avoiding walks

A self-avoiding walk (SAW) on the square lattice is prudent if it never takes a step towards a vertex it has already visited. Prudent walks differ from most classes of SAW that have been counted so far in that they can wind around their starting point.Their enumeration was first addressed by Préa in 1997. He defined 4 classes of prudent walks, of increasing generality, and wrote a system of recurrence relations for each of them. However, these relations involve more and more parameters as the generality of the class increases.The first class actually consists of partially directed walks, and its generating function is well known to be rational. The second class was proved to have an algebraic (quadratic) generating function by Duchi (2005). Here, we solve exactly the third class, which turns out to be much more complex: its generating function is not algebraic, nor even D-finite.The fourth class—general prudent walks—is the only isotropic one, and still defeats us. However, we design an isotropic family of prudent walks on the triangular lattice, which we count exactly. Again, the generating function is proved to be non-D-finite.We also study the asymptotic properties of these classes of walks, with the (somewhat disappointing) conclusion that their endpoint moves away from the origin at a positive speed. This is confirmed visually by the random generation procedures we have designed.     

Some properties of characteristic polynomials and applications to T-lattices

Some intersection results for the characteristic polynomial of locally finite inf-semilattices are given; furthermore, we use these results to exhibit some characterizations and some enumeration formulas for lattices of triangular type.     

Singularity of full scaling limits of planar nearcritical percolation

We consider full scaling limits of planar nearcritical percolation in the Quad-Crossing-Topology introduced by Schramm and Smirnov. We show that two nearcritical scaling limits with different parameters are singular with respect to each other. The results hold for percolation models on rather general lattices, including bond percolation on the square lattice and site percolation on the triangular lattice.     

A Formal Calculus for the Enumerative System of Sequences—I. Combinatorial Theorems

The enumeration of sequences plays an important part in combinatorial enumeration since sequences may be used as a means for encoding combinatorial structures. In the main, the enumeration of sequences has been treated by a collection of methods individually applied in particular cases. We present here a uniform constructive method for dealing with a large class of sequence problems. We obtain the generating function as the trace of an expression involving certain incidence matrices, expressions which are obtainable immediately from the combinatorial structure of a problem. The method relies on certain properties of matrices whose rank is equal to one. We demonstrate that these properties may be used to derive the required generating functions explicitly or, in more complex cases, as solutions to systems of linear equations. Results for permutations may be derived from those for sequences, and in certain frequently encountered special cases this operation may be carried out by a straightforward substitution. Applications of the method presented here will be given in Part II.     

Density of wavelet frames

Density conditions for wavelet systems with arbitrary sampling points to be frames are studied. We show that for a wavelet system generated by admissible functions with irregular affine lattices to be a frame, the sampling points must have a positive lower affine Beurling density. The same is true for wavelet systems with arbitrary sampling points and nice generating functions.     

Enumeration of polyominoes inscribed in a rectangle

We develop a number of formulas and generating functions for the enumeration of general polyominoes inscribed in a rectangle of given size according to their area. These formulae are then used for the enumeration of lattice trees inscribed in a rectangle with minimum area plus one.     

Generating All Vertices of a Polyhedron Is Hard

We show that generating all negative cycles of a weighted graph is a hard enumeration problem, in both the directed and undirected cases. More precisely, given a family of negative (directed) cycles, it is an NP-complete problem to decide whether this family can be extended or there are no other negative (directed) cycles in the graph, implying that (directed) negative cycles cannot be generated in polynomial output time, unless P=NP. As a corollary, we solve in the negative two well-known generating problems from linear programming: (i) Given an infeasible system of linear inequalities, generating all minimal infeasible subsystems is hard. Yet, for generating maximal feasible subsystems the complexity remains open. (ii) Given a feasible system of linear inequalities, generating all vertices of the corresponding polyhedron is hard. Yet, in the case of bounded polyhedra the complexity remains open. Equiva lently, the complexity of generating vertices and extreme rays of polyhedra remains open.     

Tree Growth Parameter in the Eden Model on Face-Centered Hypercubic Lattices

In the Eden model, we investigate how the tree growth parameter depends on the space dimension d for face-centered hypercubic lattices. We find the first three terms of the 1/d-expansion for this parameter directly from the generating function without calculating the number of trees because the growth parameter is the reciprocal coordinate of the singular point of the tree generating function. The same growth parameter was calculated by computer experiment where the ratios between the numbers of trees without intersections and trees without restrictions in the dimensions 3, 4, 6, 8, and 10 were estimated by the Monte Carlo method on face-centered cubic lattices. The results of the two methods agree well. Comparing with the previously performed computer experiment for simple hypercubic lattices, we observe that the values of the singular exponents for the tree generating functions are close for two different types of lattices.__________Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 144, No. 3, pp. 564–576, September, 2005.     

Spectral Properties of Schrödinger Operators on Perturbed Lattices

We study the spectral properties of Schrödinger operators on perturbed lattices. We shall prove the non-existence or the discreteness of embedded eigenvalues, the limiting absorption principle for the resolvent, construct a spectral representation, and define the S-matrix. Our theory covers the square, triangular, diamond, Kagome lattices, as well as the ladder, the graphite and the subdivision of square lattice.     

Probabilistic analysis of column-convex and directed diagonally-convex animals

Using asymptotic analysis of generating functions, we consider stochastic properties of parameters of some directed animals. For column-convex animals and directed diagonally-convex animals with fixed large area, we obtain asymptotic distribution for the number of columns and the size of a column. We also consider the generation of such random animals, based on a (weighted) Markov process. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 , 151–178 (1997)     

Restricted words by adjacencies

A recurrence, a determinant formula, and generating functions are presented for enumerating words with restricted letters by adjacencies. The main theorem leads to refinements (with up to two additional parameters) of known results on compositions, polyominoes, and permutations. Among the examples considered are (1) the introduction of the ascent variation on compositions, (2) the enumeration of directed vertically convex polyominoes by upper descents, area, perimeter, relative height, and column number, (3) a tri-variate extension of MacMahon's determinant formula for permutations with prescribed descent set, and (4) a combinatorial setting for an entire sequence of bibasic Bessel functions.     

Application of an idea of Voronoĭ to lattice zeta functions

A major problem in the geometry of numbers is the investigation of the local minima of the Epstein zeta function. In this article refined minimum properties of the Epstein zeta function and more general lattice zeta functions are studied. Using an idea of Voronoĭ, characterizations and sufficient conditions are given for lattices at which the Epstein zeta function is stationary or quadratic minimum. Similar problems of a duality character are investigated for the product of the Epstein zeta function of a lattice and the Epstein zeta function of the polar lattice. Besides Voronoĭ type notions such as versions of perfection and eutaxy, these results involve spherical designs and automorphism groups of lattices. Several results are extended to more general lattice zeta functions, where the Euclidean norm is replaced by a smooth norm.     

Two-grid discretization schemes for nonlinear Schrödinger equations

We study efficient two-grid discretization schemes with two-loop continuation algorithms for computing wave functions of two-coupled nonlinear Schrödinger equations defined on the unit square and the unit disk. Both linear and quadratic approximations of the operator equations are exploited to derive the schemes. The centered difference approximations, the six-node triangular elements and the Adini elements are used to discretize the PDEs defined on the unit square. The proposed schemes also can compute stationary solutions of parameter-dependent reaction–diffusion systems. Our numerical results show that it is unnecessary to perform quadratic approximations.     

Partition inequalities for capacitated survivable network design based on directed p-cycles

We study the design of capacitated survivable networks using directed p-cycles. A p-cycle is a cycle with at least three arcs, used for rerouting disrupted flow during edge failures. Survivability of the network is accomplished by reserving sufficient slack on directed p-cycles so that if an edge fails, its flow can be rerouted along the p-cycles.

We describe a model for designing capacitated survivable networks based on directed p-cycles. We motivate this model by comparing it with other means of ensuring survivability, and present a mixed-integer programming formulation for it. We derive valid inequalities for the model based on the minimum capacity requirement between partitions of the nodes and give facet conditions for them. We discuss the separation for these inequalities and present results of computational experiments for testing their effectiveness as cutting planes when incorporated in a branch-and-cut algorithm. Our experiments show that the proposed inequalities reduce the computational effort significantly.     

On Estimating the Cumulant Generating Function of Linear Processes

We compare two estimates of the cumulant generating function of a stationary linear process. The first estimate is based on the empirical moment generating function. The second estimate uses the linear representation of the process and the empirical moment generating function of the innovations. Asymptotic expressions for the mean square errors are derived under short- and long-range dependence. For long-memory processes, the estimate based on the linear representation turns out to have a better rate of convergence. Thus, exploiting the linear structure of the process leads to an infinite gain in asymptotic efficiency.     

Binomial posets, Möbius inversion, and permutation enumeration

A unified method is presented for enumerating permutations of sets and multisets with various conditions on their descents, inversions, etc. We first prove several formal identities involving Möbius functions associated with binomial posets. We then show that for certain binomial posets these Möbius functions are related to problems in permutation enumeration. Thus, for instance, we can explain “why” the exponential generating function for alternating permutations has the simple form (1 + sin x)/(cos x). We can also clarify the reason for the ubiquitous appearance of e^x in connection with permutations of sets, and of ξ(s) in connection with permutations of multisets.     

Generating functions, Fibonacci numbers and rational knots

We describe rational knots with any of the possible combinations of the properties (a)chirality, (non-)positivity, (non-)fiberedness, and unknotting number one (or higher), and determine exactly their number for a given number of crossings in terms of their generating functions. We show in particular how Fibonacci numbers occur in the enumeration of fibered achiral and unknotting number one rational knots. Then we show how to enumerate rational knots of given crossing number depending on genus and/or signature. This allows to determine the asymptotical average value of these invariants among rational knots. We give also an application to the enumeration of lens spaces.     

A Renormalization Group Method by Harmonic Extensions and the Classical Dipole Gas

In this paper, we develop a new renormalization group method, which is based on conditional expectations and harmonic extensions, to study functional integrals of small perturbations of Gaussian fields. In this new method, one integrates Gaussian fields inside domains at all scales conditioning on the fields outside these domains, and by the variation principle solves local elliptic problems. It does not rely on an a priori decomposition of the Gaussian covariance. We apply this method to the model of classical dipole gas on the lattice, and show that the scaling limit of the generating function with smooth test functions is the generating function of the renormalized Gaussian free field.