Search

The Morris constant term identity is known to be equivalent to the famous Selberg integral. In this paper, we regard Morris type constant terms as polynomials of a certain parameter. Thus, we can take the leading coefficients and obtain new identities. These identities happen to be crucial in finding lower bounds for cardinalities of some restricted sumsets, and in calculating the volume of a Tesler polytope.

An alternating sign matrix , or ASM, is a (0,±1)(0,±1)-matrix where the nonzero entries in each row and column alternate in sign, and where each row and column sum is 1. We study the convex cone generated by ASMs of order n , called the ASM cone, as well as several related cones and polytopes. Some decomposition results are shown, and we find a minimal Hilbert basis of the ASM cone. The notion of (±1)(±1)-doubly stochastic matrices and a generalization of ASMs are introduced and various properties are shown. For instance, we give a new short proof of the linear characterization of the ASM polytope, in fact for a more general polytope. Finally, we investigate faces of the ASM polytope, in particular edges associated with permutation matrices.

We give a combinatorial description of the toric ideal of invariants of the Cavender-Farris-Neyman model with a molecular clock (CFN-MC) on a rooted binary phylogenetic tree and prove results about the polytope associated to this toric ideal. Key results about the polyhedral structure include that the number of vertices of this polytope is a Fibonacci number, the facets of the polytope can be described using the combinatorial “cluster” structure of the underlying rooted tree, and the volume is equal to an Euler zig-zag number. The toric ideal of invariants of the CFN-MC model has a quadratic Grobner basis with squarefree initial terms. Finally, we show that the Ehrhart polynomial of these polytopes, and therefore the Hilbert series of the ideals, depends only on the number of leaves of the underlying binary tree, and not on the topology of the tree itself. These results are analogous to classic results for the Cavender-Farris-Neyman model without a molecular clock. However, new techniques are required because the molecular clock assumption destroys the toric fiber product structure that governs group-based models without the molecular clock.

We are interested in enumerating the integer points in certain polytopes that are naturally associated with directed graphs. These polytopes generalize Stanley's order polytopes and also ( P , ω ) -partitions. A classical result states that the number of integer points in any given rational polytope can be expressed by a formula that is piecewise a quasipolynomial in certain parameters of the polytope, and, remarkably, the domains of validity of the involved quasipolynomials overlap. In the case of our special polytopes, the quasipolynomials are shown to be polynomials. We investigate the domains of validity of these polynomials and demonstrate how the overlaps can be used to explore the zero set of the polynomials. We have a closer look at the counting of Gelfand-Tsetlin patterns, which can be phrased as the counting of integer points in a polytope associated with a particular directed graph. We conjecture that the zeros that can be deduced by studying the overlaps essentially determine the enumeration formula in this case.

Let $x_1,\ldots ,x_N$ be independent random points distributed according to an isotropic log-concave measure $\mu $ on ${\mathbb R}^n$, and consider the random polytope $$K_N:={\rm conv}\{ \pm x_1,\ldots ,\pm x_N\}.$$ We provide sharp estimates for the querma\ss{}integrals and other geometric parameters of $K_N$ in the range $cn\ls N\ls\exp (n)$; these complement previous results from \cite{DGT1} and \cite{DGT} that were given for the range $cn\ls N\ls\exp (\sqrt{n})$. One of the basic new ingredients in our work is a recent result of E.~Milman that determines the mean width of the centroid body $Z_q(\mu )$ of $\mu $ for all $1\ls q\ls n$.

A k-dissimilarity map on a finite set X is a function D : X \choose k \rightarrow R assigning a real value to each subset of X with cardinality k, k \geq 2. Such functions, also sometimes known as k-way dissimilarities, k-way distances, or k-semimetrics, are of interest in many areas of mathematics, computer science and classification theory, especially 2-dissimilarity maps (or distances) which are a generalisation of metrics. In this paper, we show how regular subdivisions of the kth hypersimplex can be used to obtain a canonical decomposition of a k-dissimilarity map into the sum of simpler k-dissimilarity maps arising from bipartitions or splits of X. In the special case k = 2, this is nothing other than the well-known split decomposition of a distance due to Bandelt and Dress [Adv. Math. 92 (1992), 47-105], a decomposition that is commonly to construct phylogenetic trees and networks. Furthermore, we characterise those sets of splits that may occur in the resulting decompositions of k-dissimilarity maps. As a corollary, we also give a new proof of a theorem of Pachter and Speyer [Appl. Math. Lett. 17 (2004), 615-621] for recovering k-dissimilarity maps from trees., 22 pages, 4 figures

Let P(M) be the matroid base polytope of a matroid M. A matroid base polytope decomposition of P(M) is a decomposition of the form P(M) =\cup_i=1P(Mi) where each P(Mi) is also a matroid base polytope for some matroid Mi, and for each 1\le i \neq j\le t, the intersection P(Mi)\P(Mj) is a face of both P(Mi) and P(Mj ). In this paper, we investigate hyperplane splits, that is, polytope decompositions when t = 2. We give suffcient conditions for M so P(M) has a hyperplane split and characterize when P(M1 +M2) has a hyperplane split where M1 +M2 denote the direct sum of matroids M1 and M2. We also prove that P(M) has not a hyperplane split if M is binary. Finally, we show that P(M) has not a decomposition if its 1-skeleton is the hypercube.

We describe a maximum entropy approach for computing volumes and counting integer points in polyhedra. To estimate the number of points from a particular set X⊂Rn in a polyhedron P⊂Rn, by solving a certain entropy maximization problem, we construct a probability distribution on the set X such that a) the probability mass function is constant on the set P∩X and b) the expectation of the distribution lies in P. This allows us to apply Central Limit Theorem type arguments to deduce computationally efficient approximations for the number of integer points, volumes, and the number of 0–1 vectors in the polytope. As an application, we obtain asymptotic formulas for volumes of multi-index transportation polytopes and for the number of multi-way contingency tables.

We show that if P is a lattice polytope in the nonnegative orthant of Rk and χ is a coloring of the lattice points in the orthant such that the color χ(a+b) depends only on the colors χ(a) and χ(b), then the number of colors of the lattice points in the dilation nP of P is for large n given by a polynomial (or, for rational P, by a quasipolynomial). This unifies a classical result of Ehrhart and Macdonald on lattice points in polytopes and a result of Khovanskiĭ on sumsets in semigroups. We also prove a strengthening of multivariate generalizations of Khovanskiĭ's theorem. Another result of Khovanskiĭ states that the size of the image of a finite set after n applications of mappings from a finite family of mutually commuting mappings is for large n a polynomial. We give a combinatorial proof of a multivariate generalization of this theorem.

Euler–Maclaurin formulas for a polytope express the sum of the values of a function over the lattice points in the polytope in terms of integrals of the function and its derivatives over faces of the polytope or its expansions. Exact Euler–Maclaurin formulas [A.G. Khovanskii, A.V. Pukhlikov, Algebra and Analysis 4 (1992) 188–216; S.E. Cappell, J.L. Shaneson, Bull. Amer. Math. Soc. 30 (1994) 62–69; C. R. Acad. Sci. Paris Sér. I Math. 321 (1995) 885–890; V. Guillemin, J. Differential Geom. 45 (1997) 53–73; M. Brion, M. Vergne, J. Amer. Math. Soc. 10 (2) (1997) 371–392] apply to exponential or polynomial functions; Euler–Maclaurin formulas with remainder [Y. Karshon, S. Sternberg, J. Weitsman, Proc. Natl. Acad. Sci. 100 (2) (2003) 426–433; Duke Math. J. 130 (3) (2005) 401–434] apply to more general smooth functions.In this paper we review these results and present proofs of the exact formulas obtained by these authors, using elementary methods. We then use an algebraic formalism due to Cappell and Shaneson to relate the different formulas.

Higher-dimensional Dedekind sums are defined as a generalization of a recent 1-dimensional probability model of Dilcher and Girstmair to a d-dimensional cube. The analysis of the frequency distribution of marked lattice points leads to new formulae in certain special cases, and to new bounds for the classical Dedekind sums. Upper bounds for the generalized Dedekind sums are defined in terms of 1-dimensional moments. In the classical two-dimensional case, the ratio of these sums to their upper bounds are cosines of angles between certain vectors of n-dimensional cones, conjectured to have a largest spacial angle of pi/6., Comment: 24 pages, 8 figures

When the standard representation of a crystallographic Coxeter group @C is reduced modulo an odd prime p, a finite representation in some orthogonal space over Z"p is obtained. If @C has a string diagram, the latter group will often be the automorphism group of a finite regular polytope. In Part I we described the basics of this construction and enumerated the polytopes associated with the groups of rank 3 and the groups of spherical or Euclidean type. In this paper, we investigate such families of polytopes for more general choices of @C, including all groups of rank 4. In particular, we study in depth the interplay between their geometric properties and the algebraic structure of the corresponding finite orthogonal group.

Let V be an n-dimensional real vector space endowed with a rank-n lattice Γ . The dual lattice Γ ∗ = Hom(Γ.Z) is naturally a subset of the dual vector space V ∗. Let Φ = [β1, β2, . . . , βN ] be a sequence of not necessarily distinct elements of Γ ∗, which span V ∗ and lie entirely in an open halfspace of V ∗. In what follows, the order of elements in the sequence will not matter. The closed cone C(Φ) generated by the elements of Φ is an acute convex cone, divided into open conic chambers by the (n− 1)-dimensional cones generated by linearly independent (n−1)-tuples of elements of Φ . Denote by ZΦ the sublattice of Γ ∗ generated by Φ . Pick a vector a ∈ V ∗ in the cone C(Φ), and denote by ΠΦ(a) ⊂ R+ the convex polytope consisting of all solutions x = (x1, x2, . . . , xN) of the equation ∑Nk=1 xkβk = a in nonnegative real numbers xk . This is a closed convex polytope called the partition polytope associated to Φ and a. Conversely, any closed convex polytope can be realized as a partition polytope. If λ ∈ Γ ∗, then the vertices of the partition polytope ΠΦ(λ) have rational coordinates. We denote by ιΦ(λ) the number of points with integral coordinates in ΠΦ(λ). Thus ιΦ(λ) is the number of solutions of the equation ∑N k=1 xkβk = λ in nonnegative integers xk . The function λ → ιΦ(λ) is called the vector partition function associated to Φ . Obviously, ιΦ(λ) vanishes if λ does not belong to C(Φ) ∩ZΦ .

We define a partition of the unit hypercube into polytopes. These polytopes correspond to arrangements of a sequence of objects into bins in the next fit solution to the one-dimensional bin packing problem. The probability that an arrangement appears is given by the volume of the corresponding polytope in the partition. We show that this volume can be calculated as the solution to a problem of permutation enumeration and apply this technique to analyze the behavior of the next fit algorithm.

A corner cut in dimension d is a finite subset of N"0^d that can be separated from its complement in N"0^d by an affine hyperplane disjoint from N"0^d. Corner cuts were first investigated by Onn and Sturmfels [Adv. Appl. Math. 23 (1999) 29-48], their original motivation stemmed from computational commutative algebra. Let us write N"0^dk"c"u"t for the set of corner cuts of cardinality k; in the computational geometer's terminology, these are the k-sets of N"0^d. Among other things, Onn and Sturmfels give an upper bound of O(k^2^d^(^d^-^1^)^/^(^d^+^1^)) for the size of N"0^dk"c"u"t when the dimension is fixed. In two dimensions, it is known (see [Corteel et al., Adv. Appl. Math. 23 (1) (1999) 49-53]) that #N"0^dk"c"u"[email protected](klogk). We will see that in general, for any fixed dimension d, the order of magnitude of #N"0^dk"c"u"t is between k^d^-^1logk and (klogk)^d^-^1. (It has been communicated to me that the same bounds have been found independently by G. Remond.) In fact, the elements of N"0^dk"c"u"t correspond to the vertices of a certain polytope, and what our proof shows is that the above upper bound holds for the total number of flags of that polytope.

Complex groups generated by involutory reflexions arise naturally in the modern theory of abstract regular polytopes. The paper investigates this relationship and explains how the enumeration of certain finite universal regular polytopes can be accomplished through the enumeration of certain types of finite complex reflexion groups. In particular, the paper enumerates all the finite groups and their diagrams which arise in this context, and describes the corresponding regular polytopes.

Viro's construction of real smooth hypersurfaces uses regular (also called convex or coherent) subdivisions of Newton polytopes. Nevertheless, Viro's construction, sometimes calledpatchworking, can be applied as well to arbitrary subdivisions as a purely combinatorial procedure. Are the schemes coming from nonregular subdivisions, still topological types of some real smooth hypersurfaces? In the first part of this paper we prove a combinatorial version of Hilbert's Lemma (a consequence of Bezout's Theorem) that bounds the depth of nests in aT-curve, and we use this result and a previous work by I. Itenberg to answer the question affirmatively forT-curves of degree less than 6.According to V. A. Rokhlin, a real algebraic scheme has complex orientation of type I (alternatively of type II) if any curve with this real scheme divides (does not divide) its complexification. A real algebraic scheme hasindefinite typeif there are type I and type II curves with that particular scheme. In the second part of this paper, we describe a combinatorial algorithm, due to I. Itenberg and O. Viro, that allows one to determine the type of aT-curve. We then present a partial list of indefinite schemes forT-curves of degrees 7 and 8.

This is an expository paper on connections between enumerative combinatorics and convex polytopes. It aims to give an essentially self-contained overview of five specific instances when enumerative combinatorics and convex polytopes arise jointly in problems whose initial formulation lies in only one of these two subjects. These examples constitute only a sample of such instances occurring in the work of several authors. On the enumerative side, they involved ordered graphical sequences, combinatorial statistics on the symmetric and hyperoctahedral groups, lattice paths, Baxter, André, and simsun permutations,q-Catalan andq-Schröder numbers. From the subject of polytopes, the examples involve the Ehrhart polynomial, the permutohedron, the associahedron, polytopes arising as intersections of cubes and simplices with half-spaces, and thecd-index of a polytope.

The aim of this paper is to compute all isolated solutions to symmetric polynomial systems. Recently, it has been proved that modelling the sparse structure of the system by its Newton polytopes leads to a computational breakthrough in solving the system. In this paper, it will be shown how the Lifting Algorithm, proposed by Huber and Sturmfels, can be applied to symmetric Newton polytopes. This symmetric version of the Lifting Algorithm enables the efficient construction of the symmetric subdivision, giving rise to a symmetric homotopy, so that only the generating solutions have to be computed. Efficiency is obtained by combination with the product homotopy. Applications illustrate the practical significance of the presented approach.

The Loomis–Whitney inequality is a sharp estimate from above of the volume of a compact subset of Rn in terms of the product of the areas of its projections along the coordinate directions.This paper deals with estimates from above of intrinsic volumes of a convex body in terms of sums of intrinsic volumes of finitely many orthogonal projections of the body itself.We show that suitable polytopes maximize the surface area in the class of convex bodies whose projections along fixed directions have assigned surface area. A sharp estimate of the mean width of a convex body in terms of the mean widths of the coordinate projections is proved. An analogous estimate for intrinsic volumes of any order is conjectured and discussed. We prove that the conjecture holds true under the assumption that the coordinate projections satisfy an equilibrium condition and we show that such a condition is fulfilled in special classes of convex bodies.