Ordered partitions and drawings of rooted plane trees

We study the bounded regions in a generic slice of the hyperplane arrangement in Rⁿ${\mathbb{R}}^n$ consisting of the hyperplanes defined by _xi$x_i$ and _xi+_xj$x_i+x_j$. The bounded regions are in bijection with several classes of combinatorial objects, including the ordered partitions of [n]$\left[n\right]$ all of whose left-to-right minima occur at odd locations and the drawings of rooted plane trees with n+1$n+1$ vertices. These are sequences of rooted plane trees such that each tree in a sequence can be obtained from the next one by removing a leaf.     

Enumeration of plane partitions

Using some recent results involving Young tableaux and matrices of non-negative integers [10], it is possible to enumerate various classes of plane partitions by actual construction. One of the results is a simple proof of MacMahon's [12] generating function for plane partitions. Previous results of this type [12, 4, 3, 8, 7] involved complicated algebraic methods which did not reveal any intrinsic “reason” why the corresponding generating functions have such a simple form.     

Shuffling algorithm for boxed plane partitions

We introduce discrete time Markov chains that preserve uniform measures on boxed plane partitions. Elementary Markov steps change the size of the box from a×b×c to (a−1)×(b+1)×c or (a+1)×(b−1)×c. Algorithmic realization of each step involves O((a+b)c) operations. One application is an efficient perfect random sampling algorithm for uniformly distributed boxed plane partitions.Trajectories of our Markov chains can be viewed as random point configurations in the three-dimensional lattice. We compute the bulk limits of the correlation functions of the resulting random point process on suitable two-dimensional sections. The limiting correlation functions define a two-dimensional determinantal point processes with certain Gibbs properties.     

On the weighted enumeration of alternating sign matrices and descending plane partitions

We prove a conjecture of Mills, Robbins and Rumsey [Alternating sign matrices and descending plane partitions, J. Combin. Theory Ser. A 34 (3) (1983) 340-359] that, for any n, k, m and p, the number of n×n alternating sign matrices (ASMs) for which the 1 of the first row is in column k+1 and there are exactly m −1?s and m+p inversions is equal to the number of descending plane partitions (DPPs) for which each part is at most n and there are exactly k parts equal to n, m special parts and p nonspecial parts. The proof involves expressing the associated generating functions for ASMs and DPPs with fixed n as determinants of n×n matrices, and using elementary transformations to show that these determinants are equal. The determinants themselves are obtained by standard methods: for ASMs this involves using the Izergin-Korepin formula for the partition function of the six-vertex model with domain-wall boundary conditions, together with a bijection between ASMs and configurations of this model, and for DPPs it involves using the Lindström-Gessel-Viennot theorem, together with a bijection between DPPs and certain sets of nonintersecting lattice paths.     

Bäcklund transformations for the difference Hirota equation and the supersymmetric Bethe ansatz

We consider GL(K|M)-invariant integrable supersymmetric spin chains with twisted boundary conditions and demonstrate the role of Bäcklund transformations in solving the difference Hirota equation for eigenvalues of their transfer matrices. We show that the nested Bethe ansatz technique is equivalent to a chain of successive Bäcklund transformations “undressing” the original problem to a trivial one.     

Four-vertex model and random tilings

We consider the exactly solvable four-vertex model on a square lattice with different boundary conditions. Using the algebraic Bethe ansatz method allows calculating the partition function of the model. For fixed boundary conditions, we establish the connection between the scalar product of the state vectors and the generating function of the column-and row-strict boxed plane partitions. We discuss the tiling model on a periodic lattice. __________ Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 155, No. 1, pp. 25–38, April, 2008.     

Enumeration of maps on the projective plane

1. IntroductionA lnap is rooted if an edge is distinguished togetl1er with an end and a side of the edge.An edge belo11ging to only one face is called double (or 8ingular by some author), al1 othersbelonging to exactly two faces are called s1ngle. The enumeration of rooted p1anar maps wasfirst introduced by Tutte['], Techniques originated by Tutte [2,3l for enumerating variousclasses of rooted Inaps on tIle sphere are here applied to the c1asses of alI rooted maps onthe projective plane. Th…     

Enumeration of M-partitions

An M-partition of a positive integer m is a partition of m with as few parts as possible such that every positive integer less than m can be written as a sum of parts taken from the partition. This type of partition is a variation of MacMahon's perfect partition, and was recently introduced and studied by O’Shea, who showed that for half the numbers m, the number of M-partitions of m is equal to the number of binary partitions of 2ⁿ⁺¹-1-m, where . In this note we extend O’Shea's result to cover all numbers m.     

Enumeration of lattice paths and generating functions for skew plane partitions

n-dimensional lattice paths not touching the hyperplanesX _i–X _i+1=–1,i=1,2,...,n, are counted by four different statistics, one of which is MacMahon's major index. By a reflection-like proof, heavily relying on Zeilberger's (Discrete Math. 44(1983), 325–326) solution of then-candidate ballot problem, determinantal expressions are obtained. As corollaries the generating functions for skew plane partitions, column-strict skew plane partitions, reverse skew plane plane partitions and column-strict reverse skew plane partitions, respectively, are evaluated, thus establishing partly new results, partly new proofs for known theorems in the theory of plane partitions.     

Enumeration of the doubles of the projective plane of order 4

A classification of the doubles of the projective plane of order 4 with respect to the order of the automorphism group is presented and it is established that, up to isomorphism, there are 1 746 461 307 doubles. We start with the designs possessing non-trivial automorphisms. Since the designs with automorphisms of odd prime orders have been constructed previously, we are left with the construction of the designs with automorphisms of order 2. Moreover, we establish that a 2-(21,5,2) design cannot be reducible in two inequivalent ways. This makes it possible to calculate the number of designs with only the trivial automorphism, and consequently the number of all double designs. Most of the computer results are obtained by two different approaches and implementations.     

Punctured plane partitions and the q-deformed Knizhnik-Zamolodchikov and Hirota equations

We consider partial sum rules for the homogeneous limit of the solution of the q-deformed Knizhnik-Zamolodchikov equation with reflecting boundaries in the Dyck path representation of the Temperley-Lieb algebra. We show that these partial sums arise in a solution of the discrete Hirota equation, and prove that they are the generating functions of τ²-weighted punctured cyclically symmetric transpose complement plane partitions where τ=−(q+q−1). In the cases of no or minimal punctures, we prove that these generating functions coincide with τ²-enumerations of vertically symmetric alternating sign matrices and modifications thereof.     

Nodal domains and spectral minimal partitions

We consider two-dimensional Schrödinger operators in bounded domains. We analyze relations between the nodal domains of eigenfunctions, spectral minimal partitions and spectral properties of the corresponding operator. The main results concern the existence and regularity of the minimal partitions and the characterization of the minimal partitions associated with nodal sets as the nodal domains of Courant-sharp eigenfunctions.     

Semiclassical geometry and integrability of the AdS/CFT correspondence

We discuss the semiclassical geometry and integrable systems related to the gauge—string duality. We analyze semiclassical solutions of the Bethe ansatz equations arising in the context of the AdS/CFT correspondence, comparing them to stationary phase equations for the matrix integrals. We demonstrate how the underlying geometry is related to the integrable sigma models of the dual string theory and investigate some details of this correspondence.Translated from Teoreticheskaya Matematicheskaya Fizika, Vol. 142, No. 2, pp. 265–283, February, 2005.     

乘法分拆的计数函数的估值

设f(n)表示自然数n的乘法分拆数。对于所有奇数，较大地改进了n的系数，证明了：若n为奇数，则f(n)≤n/15 7/5。     

On zero-sum partitions and anti-magic trees

We study zero-sum partitions of subsets in abelian groups, and apply the results to the study of anti-magic trees. Extension to the nonabelian case is also given.     

Dominance method for plane partitions. IV: Enumeration of flagged skew tableaux

Flagged skew tableaux are generalizations of Young tableaux in which each row (column) has an upper and lower bound on entries. It has been shown that they are enumerated by flagged skew Schur functions. In this note, we present an alternate proof of this result based on the dominance technique.     

Vertex partitions and maximum degenerate subgraphs

Let G be a graph with maximum degree d≥ 3 and ω(G)≤ d, where ω(G) is the clique number of the graph G. Let p₁ and p₂ be two positive integers such that d = p₁ + p₂. In this work, we prove that G has a vertex partition S₁, S₂ such that G[S₁] is a maximum order (p₁‐1)‐degenerate subgraph of G and G[S₂] is a (p₂‐1)‐degenerate subgraph, where G[S_i] denotes the graph induced by the set S_i in G, for i = 1,2. On one hand, by using a degree‐equilibrating process our result implies a result of Bollobas and Marvel [ 1 ]: for every graph G of maximum degree d≥ 3 and ω(G)≤ d, and for every p₁ and p₂ positive integers such that d = p₁ + p₂, the graph G has a partition S₁,S₂ such that for i = 1,2, Δ(G[S_i])≤ p_i and G[S_i] is (p_i‐1)‐degenerate. On the other hand, our result refines the following result of Catlin in [ 2 ]: every graph G of maximum degree d≥ 3 has a partition S₁,S₂ such that S₁ is a maximum independent set and ω(G[S₂])≤ d‐1; it also refines a result of Catlin and Lai [ 3 ]: every graph G of maximum degree d≥ 3 has a partition S₁,S₂ such that S₁ is a maximum size set with G[S₁] acyclic and ω(G[S₂])≤ d‐2. The cases d = 3, (d,p₁) = (4,1) and (d,p₁) = (4,2) were proved by Catlin and Lai [ 3 ]. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 227–232, 2007     

On the distribution of the summands of partitions in residue classes

Summary It is proved that the summands of almost all partitions of nare well-distributed modulo dfor dup to d= n^1/2-ε.     

Polychromatic colorings of rectangular partitions

A rectangular partition is a partition of a plane rectangle into an arbitrary number of non-overlapping rectangles such that no four rectangles share a corner. In this note, it is proven that every rectangular partition admits a vertex coloring with four colors such that every rectangle, except possibly the outer rectangle, has all four colors on its boundary. This settles a conjecture of Dinitz et al. [Y. Dinitz, M.J. Katz, R. Krakovski, Guarding rectangular partitions, in: Abstracts 23rd Euro. Workshop Comput. Geom., 2007, pp. 30-33]. The proof is short, simple and based on 4-edge-colorability of a specific class of planar graphs.