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.     

Eigenvalues of the derangement graph

We consider the Cayley graph on the symmetric group Sn generated by derangements. It is well known that the eigenvalues of this graph are indexed by partitions of n. We investigate how these eigenvalues are determined by the shape of their corresponding partitions. In particular, we show that the sign of an eigenvalue is the parity of the number of cells below the first row of the corresponding Ferrers diagram. We also provide some lower and upper bounds for the absolute values of these eigenvalues.     

2-Adic valuations of certain ratios of products of factorials and applications

We prove the conjecture of Falikman-Friedland-Loewy on the parity of the degrees of projective varieties of n×n complex symmetric matrices of rank at most k. We also characterize the parity of the degrees of projective varieties of n×n complex skew symmetric matrices of rank at most 2p. We give recursive relations which determine the parity of the degrees of projective varieties of m×n complex matrices of rank at most k. In the case the degrees of these varieties are odd, we characterize the minimal dimensions of subspaces of n×n skew symmetric real matrices and of m×n real matrices containing a nonzero matrix of rank at most k. The parity questions studied here are also of combinatorial interest since they concern the parity of the number of plane partitions contained in a given box, on the one hand, and the parity of the number of symplectic tableaux of rectangular shape, on the other hand.     

Partition and composition matrices

This paper introduces two matrix analogues for set partitions. A composition matrix on a finite set X is an upper triangular matrix whose entries partition X, and for which there are no rows or columns containing only empty sets. A partition matrix is a composition matrix in which an order is placed on where entries may appear relative to one-another.We show that partition matrices are in one-to-one correspondence with inversion tables. Non-decreasing inversion tables are shown to correspond to partition matrices with a row ordering relation. Partition matrices which are s-diagonal are classified in terms of inversion tables. Bidiagonal partition matrices are enumerated using the transfer-matrix method and are equinumerous with permutations which are sortable by two pop-stacks in parallel.We show that composition matrices on X are in one-to-one correspondence with (2+2)-free posets on X. Also, composition matrices whose rows satisfy a column-ordering relation are shown to be in one-to-one correspondence with parking functions. Finally, we show that pairs of ascent sequences and permutations are in one-to-one correspondence with (2+2)-free posets whose elements are the cycles of a permutation, and use this relation to give an expression for the number of (2+2)-free posets on {1,…,n}.     

Alternating sign matrices and descending plane partitions

An alternating sign matrix is a square matrix such that (i) all entries are 1, ?1, or 0, (ii) every row and column has sum 1, and (iii) in every row and column the nonzero entries alternate in sign. Striking numerical evidence of a connection between these matrices and the descending plane partitions introduced by Andrews (Invent. Math.53 (1979), 193–225) have been discovered, but attempts to prove the existence of such a connection have been unsuccessful. This evidence, however, did suggest a method of proving the Andrews conjecture on descending plane partitions, which in turn suggested a method of proving the Macdonald conjecture on cyclically symmetric plane partitions (Invent. Math.66 (1982), 73–87). In this paper is a discussion of alternating sign matrices and descending plane partitions, and several conjectures and theorems about them are presented.     

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.     

The conjugate trace and trace of a plane partition

The conjugate trace and trace of a plane partition are defined, and the generating function for the number of plane partitions π of n with ?r rows and largest part ?m, with conjugate trace t (or trace t, when m = ∞), is found. Various properties of this generating function are studied. One consequence of these properties is a formula which can be regarded as a q-analog of a well-known result arising in the representation theory of the symmetric group.     

Non-P-recursiveness of numbers of matchings or linear chord diagrams with many crossings

The number con_n counts matchings X on {1,2,…,2n}, which are partitions into n two-element blocks, such that the crossing graph of X is connected. Similarly, cro_n counts matchings whose crossing graph has no isolated vertex. (If it has no edge, Catalan numbers arise.) We apply generating functions techniques and prove, using a more generally applicable criterion, that the sequences (con_n) and (cro_n) are not P-recursive. On the other hand, we show that the residues of con_n and cro_n modulo any fixed power of 2 can be determined P-recursively. We consider also the numbers sco_n of symmetric connected matchings. Unfortunately, their generating function satisfies a complicated differential equation which we cannot handle.     

Consensus of partitions : a constructive approach

Given a profile (family) ?? of partitions of a set of objects or items X, we try to establish a consensus partition containing a maximum number of joined or separated pairs in X that are also joined or separated in the profile. To do so, we define a score function, S _?? associated to any partition on X. Consensus partitions for ?? are those maximizing this function. Therefore, these consensus partitions have the median property for the profile and the symmetric difference distance. This optimization problem can be solved, in certain cases, by integer linear programming. We define a polynomial heuristic which can be applied to partitions on a large set of items. In cases where an optimal solution can be computed, we show that the partitions built by this algorithm are very close to the optimum which is reached in practically all the cases, except for some sets of bipartitions.     

Tropical decomposition of Young’s partition lattice

Young’s partition lattice L(m,n) consists of integer partitions having m parts where each part is at most n. Using methods from complex algebraic geometry, R. Stanley proved that this poset is rank-symmetric, unimodal, and strongly Sperner. Moreover, he conjectured that it has a symmetric chain decomposition, which is a stronger property. Despite many efforts, this conjecture has only been proved for min(m,n)≤4. In this paper, we decompose L(m,n) into level sets for certain tropical polynomials derived from the secant varieties of the rational normal curve in projective space, and we find that the resulting subposets have an elementary raising and lowering algorithm. As a corollary, we obtain a symmetric chain decomposition for the subposet of L(m,n) consisting of “sufficiently generic” partitions.     

(−1)-enumeration of plane partitions with complementation symmetry

We compute the weighted enumeration of plane partitions contained in a given box with complementation symmetry where adding one half of an orbit of cubes and removing the other half of the orbit changes the weight by −1 as proposed by Kuperberg in [Electron. J. Combin. 5 (1998) R46, pp. 25, 26]. We use nonintersecting lattice path families to accomplish this for transpose-complementary, cyclically symmetric transpose-complementary and totally symmetric self-complementary plane partitions. For symmetric transpose-complementary and self-complementary plane partitions we get partial results. We also describe Kuperberg's proof for the case of cyclically symmetric self-complementary plane partitions.     

Minimum norm problems over transportation polytopes

We consider the problem of updating input-output matrices, i.e., for given (m,n) matrices A ? 0, W ? 0 and vectors u ? $\text{R}$^m, v?$\text{R}$ⁿ, find an (m,n) matrix X ? 0 with prescribed row sums Σⁿ_j=1X_ij = u_i (i = 1,…,m) and prescribed column sums Σ^m_i=1X_ij = v_j (j = 1,…,n) which fits the relations X_ij = A_ij + λ_iW_ij + W_ij + W_ijμ_j for all i,j and some λ?$\text{R}$^m, μ?$\text{R}$ⁿ. Here we consider the question of existence of a solution to this problem, i.e., we shall characterize those matrices A, W and vectors u,v which lead to a solvable problem. Furthermore we outline some computational results using an algorithm of [2].     

Cycloidal algebras

In this paper we introduce for an arbitrary algebra (groupoid, binary system) (X; *) a sequence of algebras (X; *) _n = (X; °), where x ° y = [x * y] _n = x * [x * y] _n?1, [x * y]₀ = y. For several classes of examples we study the cycloidal index (m, n) of (X; *), where (X; *) _m = (X; *) _n for m > n and m is minimal with this property. We show that (X; *) satisfies the left cancellation law, then if (X; *) _m = (X; *) _n , then also (X; *) _m?n = (X; *)₀, the right zero semigroup. Finite algebras are shown to have cycloidal indices (as expected). B-algebras are considered in greater detail. For commutative rings R with identity, x * y = ax + by + c, a, b, c ∈ ? defines a linear product and for such linear products the commutativity condition [x * y] _n = [y * x] _n is observed to be related to the golden section, the classical one obtained for ?, the real numbers, n = 2 and a = 1 as the coefficient b.     

Nombres de ramsey dans le cas orienté

Given two directed graphs G₁, G₂, the Ramsey number R(G₁,G₂) is the smallest integer n such that for any partition {U₁,U₂} of the arcs of the complete symmetric directed graph K¹_n, there exists an integer i such that the partial graph generated by U_i contains G_i as a subgraph. In this article, we determine R(P?_m,D?_n) and R(D?_m,D?_n) for some values of m and n, where P?_m denotes the directed path having m vertices and D?_m is obtained from P?_m by adding an arc from the initial vertex of P?_m to the terminal vertex.     

Diagonalizing matrices over C(X)

A complete characterization of those compact Hausdorff spaces is given such that for every n, each normal element in the algebra C(X)?M_n of continuous functions from X to $\text{M}$_n can be continuously diagonalized. The conditions are that X be a sub-Stonean space with dim X ? 2 and carries no nontrivial G-bundles over any closed subset, for G a symmetric group or the circle group. In particular, diagonalization is assured on every totally disconnected sub-Stonean space, but also on connected spaces of the form β(Y)/Y, where Y is a simply-connected (noncompact) graph.     

Ultimate boundedness results for a certain system of third-order non-linear differential equations

We present in this paper ultimate boundedness results for a third-order system of non-linear differential equations of the form $\text{·X + A}\text{X}\text{?}\text{+ B/.X + H(X) = P(t, X, /.X,}\text{X}\text{?}\text{)}$. where A, B are constant symmetric n × n matrices and X, H(X), P(t, X, X, X) are real n-vectors with H:R_n→R_n and P: RXR_nXR_nXR_nXR_n → XR_ncontinuous in their respective arguments. Our results give an n-dimensional analogue of an earlier result of Ezeilo in [1] and extend other earlier results for the case in which we do not necessarily require that H(X) be differentiable.     

A symmetrical plane partition correspondence

MacMahon conjectured the form of the generating function for symmetrical plane partitions, and as a special case deduced the following theorem. The set of partitions of a number n whose part magnitude and number of parts are both no greater than m is equinumerous with the set of symmetrical plane partitions of 2n whose part magnitude does not exceed 2 and whose largest axis does not exceed m. This theorem, together with a companion theorem for the symmetrical plane partitions of odd numbers, are proved by establishing 1-1 correspondences between the sets of partitions.     

Reconstruction from vertex-switching

Let X be a graph with vertices x₁ ,…, x_n. Let X_i be the graph obtained by removing all edges {x_i, x_j} of X and inserting all nonedges {x_i, x_k}. If n ? 0 (mod 4), then X can be uniquely reconstructed from the unlabeled graphs X₁.…, X_n. If n = 4 the result is false, while for n = 4m≥8 the result remains open. The proof uses linear algebra and does not explicitly describe the reconstructed graph X.     

Vertex Set Partitions Preserving Conservativeness

Let G be an undirected graph and ={X₁, …, X_n} be a partition of V(G). Denote by G/ the graph which has vertex set {X₁, …, X_n}, edge set E, and is obtained from G by identifying vertices in each class X_i of the partition . Given a conservative graph (G, w), we study vertex set partitions preserving conservativeness, i.e., those for which (G/ , w) is also a conservative graph. We characterize the conservative graphs (G/ , w), where is a terminal partition of V(G) (a partition preserving conservativeness which is not a refinement of any other partition of this kind). We prove that many conservative graphs admit terminal partitions with some additional properties. The results obtained are then used in new unified short proofs for a co-NP characterization of Seymour graphs by A. A. Ageev, A. V. Kostochka, and Z. Szigeti (1997, J. Graph Theory34, 357–364), a theorem of E. Korach and M. Penn (1992, Math. Programming55, 183–191), a theorem of E. Korach (1994, J. Combin. Theory Ser. B62, 1–10), and a theorem of A. V. Kostochka (1994, in “Discrete Analysis and Operations Research. Mathematics and its Applications (A. D. Korshunov, Ed.), Vol. 355, pp. 109–123, Kluwer Academic, Dordrecht).     

A Drazin inverse for rectangular matrices

The definition of the Drazin inverse of a square matrix with complex elements is extended to rectangular matrices by showing that for any B and W,m by n and n by m, respectively, there exists a unique matrix, X, such that (BW)^k=(BW)^k+1XW for some positive integer k, XWBWX = X, and BWX = XWB. Various expressions satisfied by B, W,X and related matrices are developed.