A Polytope Related to Empirical Distributions, Plane Trees, Parking Functions, and the Associahedron

Abstract. The volume of the n -dimensional polytope Π _n (x):= {y ∈ R ⁿ : y _i ≥ 0 and y ₁ + · · · + y _i ≤ x ₁ + · · ·+ x _i for all 1 ≤ i ≤ n } for arbitrary x:=(x ₁ , . . ., x _n ) with x _i >0 for all i defines a polynomial in variables x _i which admits a number of interpretations, in terms of empirical distributions, plane partitions, and parking functions. We interpret the terms of this polynomial as the volumes of chambers in two different polytopal subdivisions of Π _n (x) . The first of these subdivisions generalizes to a class of polytopes called sections of order cones. In the second subdivision the chambers are indexed in a natural way by rooted binary trees with n+1 vertices, and the configuration of these chambers provides a representation of another polytope with many applications, the associahedron .     

Derivations on a C1-algebra and its double dual

Let A be a C¹-algebra and X a Banach A-module. The module action of A on X gives rise to module actions of $\text{A}{}^7$ on $\text{X}{}^1$ and $\text{X}{}^7$, and derivations of A into X (resp. $\text{X}{}^1$) extend to derivations of $\text{A}{}^7$ into $\text{X}{}^7$ (resp. $\text{X}{}^1$). If A is nuclear, and X is a dual Banach A-module with $\text{X}{}^1$ weakly sequentially complete, then every derivation of A into X is inner. Under the same hypothesis on A, the extension to the finite part of $\text{A}{}^7$ of any derivation of A into any dual Banach A-module is inner, as are all derivations of A into $\text{A}{}^1$. Every derivation of a semifinite von Neumann algebra into its predual is inner.     

A note on Ki-perfect graphs

Ki-perfect graphs are a special instance of F - G perfect graphs, where F and G are fixed graphs with F a partial subgraph of G. Given S, a collection of G-subgraphs of graph K, an F - G cover of S is a set of T of F-subgraphs of K such that each subgraph in S contains as a subgraph a member of T. An F - G packing of S is a subcollection S′? S such that no two subgraphs in S′ have an F-subgraph in common. K is F - G perfect if for all such S, the minimum cardinality of an F - G cover of S equals the maximum cardinality of an F - G packing of S. Thus K_i-perfect graphs are precisely K_i-1 - K_i perfect graphs. We develop a hypergraph characterization of F - G perfect graphs that leads to an alternate proof of previous results on K_i-perfect graphs as well as to a characterization of F - G perfect graphs for other instances of F and G.     

Arithmetical properties of the number of t-core partitions

Let Λ={λ ₁≥⋅⋅⋅≥λ _s ≥1} be a partition of an integer n. Then the Ferrers-Young diagram of Λ is an array of nodes with λ _i nodes in the ith row. Let λ _j ′ denote the number of nodes in column j in the Ferrers-Young diagram of Λ. The hook number of the (i,j) node in the Ferrers-Young diagram of Λ is denoted by H(i,j):=λ _i +λ _j ′−i−j+1. A partition of n is called a t-core partition of n if none of the hook numbers is a multiple of t. The number of t-core partitions of n is denoted by a(t;n). In the present paper, some congruences and distribution properties of the number of 2 ^t -core partitions of n are obtained. A simple convolution identity for t-cores is also given.      

2-Normalization of lattices

Let τ be a type of algebras. A valuation of terms of type τ is a function v assigning to each term t of type τ a value v(t) ⩾ 0. For k ⩾ 1, an identity s ≈ t of type τ is said to be k-normal (with respect to valuation v) if either s = t or both s and t have value ⩾ k. Taking k = 1 with respect to the usual depth valuation of terms gives the well-known property of normality of identities. A variety is called k-normal (with respect to the valuation v) if all its identities are k-normal. For any variety V, there is a least k-normal variety N _k (V) containing V, namely the variety determined by the set of all k-normal identities of V. The concept of k-normalization was introduced by K. Denecke and S. L. Wismath in their paper (Algebra Univers., 50, 2003, pp.107–128) and an algebraic characterization of the elements of N _k (V) in terms of the algebras in V was given in (Algebra Univers., 51, 2004, pp. 395–409). In this paper we study the algebras of the variety N ₂(V) where V is the type (2, 2) variety L of lattices and our valuation is the usual depth valuation of terms. We introduce a construction called the 3-level inflation of a lattice, and use the order-theoretic properties of lattices to show that the variety N ₂(L) is precisely the class of all 3-level inflations of lattices. We also produce a finite equational basis for the variety N ₂(L). This research was supported by Research Project MSM6198959214 of the Czech Government and by NSERC of Canada.     

Rates of Best Uniform Rational Approximation of Analytic Functions by Ray Sequences of Rational Functions

In this paper, problems related to the approximation of a holomorphic function f on a compact subset E of the complex plane C by rational functions from the class of all rational functions of order (n,m) are considered. Let ρ _n,m = ρ _n,m (f;E) be the distance of f in the uniform metric on E from the class . We obtain results characterizing the rate of convergence to zero of the sequence of the best rational approximation { ρ _n,m(n) } _n=0 ^∞ , m(n)/n → θ ∈ (0,1] as n → ∞ . In particular, we give an upper estimate for the liminf _{n →∞} ρ _n,m(n) ^1/(n+m(n)) in terms of the solution to a certain minimum energy problem with respect to the logarithmic potential. The proofs of the results obtained are based on the methods of the theory of Hankel operators. June 16, 1997. Date revised: December 1, 1997. Date accepted: December 1, 1997. Communicated by Ronald A. DeVore.     

Signed graphs and the freeness of the Weyl subarrangements of type Bℓ

A Weyl arrangement is the hyperplane arrangement defined by a root system. Saito proved that every Weyl arrangement is free. The Weyl subarrangements of type $A_{\ell }$ are represented by simple graphs. Stanley gave a characterization of freeness for this type of arrangements in terms of their graph. In addition, the Weyl subarrangements of type $B_{\ell }$ can be represented by signed graphs. A characterization of freeness for them is not known. However, characterizations of freeness for a few restricted classes are known. For instance, Edelman and Reiner characterized the freeness of the arrangements between type $A_{\ell -1}$ and type $B_{\ell }$. In this paper, we give a characterization of the freeness and supersolvability of the Weyl subarrangements of type $B_{\ell }$ under certain assumption.     

A Generalization of the Erdos - Szekeres Theorem to Disjoint Convex Sets

Let F denote a family of pairwise disjoint convex sets in the plane. F is said to be in convex position if none of its members is contained in the convex hull of the union of the others. For any fixed k≥ 3 , we estimate P _k (n) , the maximum size of a family F with the property that any k members of F are in convex position, but no n are. In particular, for k=3 , we improve the triply exponential upper bound of T. Bisztriczky and G. Fejes Tóth by showing that P ₃ (n) < 16 ⁿ . <lsiheader> <onlinepub>26 June, 1998 <editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; <pdfname>19n3p437.pdf <pdfexist>yes <htmlexist>no <htmlfexist>no <texexist>yes <sectionname> </lsiheader> Received March 27, 1997, and in revised form July 10, 1997.     

The moduli space of curves of genus two covering elliptic curves

We consider the moduli spaceS _n of curvesC of genus 2 with the property:C has a “maximal” mapf of degreen to an elliptic curveE. Here, the term “maximal” means that the mapf∶C→E doesn't factor over an unramified cover ofE. By Torelli mapS _n is viewed as a subset of the moduli spaceA ₂ of principally polarized abelian surfaces. On the other hand the Humbert surfaceH _Δ of invariant Δ is defined as a subvariety ofA ₂(C), the set of C-valued points ofA ₂. The purpose of this paper is to releaseS _n withH _Δ.     

Simple vertices of maximal minor polytopes

Themaximal minor polytope Π _{m, n} is the Newton polytope of the product of all maximal minors of anm×n matrix of indeterminates. The family of polytopes {Π _{m, n} } interpolates between the symmetric transportation polytope (form=n−1) and the permutohedron (form=2). Both transportation polytope and the permutohedron aresimple polytopes but in general Π _{m, n} is not simple. The main result of this paper is an explicit construction of a class of simple vertices of Π _{m, n} for generalm andn. We call themvertices of diagonal type. For every such vertexv we explicitly describe all the edges and facets of Π _{m, n} which containv. Simple vertices of Π _{m, n} have an interesting algebro-geometric application: they correspond tononsingular extreme toric degenerations of the determinantal variety ofm×n matrices not of full rank. Andrei Zelevinsky was partially supported by the NSF under Grant DMS-9104867.     

On certain spaces of lattice diagram determinants

The aim of this work is to study some lattice diagram determinants Δ_L(X,Y) as defined in (Adv. Math. 142 (1999) 244) and to extend results of Aval et al. (J. Combin. Theory Ser. A, to appear). We recall that M_L denotes the space of all partial derivatives of Δ_L. In this paper, we want to study the space M_i,j^k(X,Y) which is defined as the sum of M_L spaces where the lattice diagrams L are obtained by removing k cells from a given partition, these cells being in the “shadow” of a given cell (i,j) in a fixed Ferrers diagram. We obtain an upper bound for the dimension of the resulting space M_i,j^k(X,Y), that we conjecture to be optimal. This dimension is a multiple of n! and thus we obtain a generalization of the n! conjecture. Moreover, these upper bounds associated to nice properties of some special symmetric differential operators (the “shift” operators) allow us to construct explicit bases in the case of one set of variables, i.e. for the subspace M_i,j^k(X) consisting of elements of 0 Y-degree.     

Classification of small (0, 1) matrices

Denote by A_n the set of square (0, 1) matrices of order n. The set A_n, n ? 8, is partitioned into row/column permutation equivalence classes enabling derivation of various facts by simple counting. For example, the number of regular (0, 1) matrices of order 8 is 10160459763342013440. Let D_n, S_n denote the set of absolute determinant values and Smith normal forms of matrices from A_n. Denote by a_n the smallest integer not in D_n. The sets D₉ and S₉ are obtained; especially, a₉ = 103. The lower bounds for a_n, 10 ? n ? 19 (exceeding the known lower bound a_n ? 2f_n − 1, where f_n is nth Fibonacci number) are obtained. Row/permutation equivalence classes of A_n correspond to bipartite graphs with n black and n white vertices, and so the other applications of the classification are possible.     

Lattice Points, Dedekind Sums, and Ehrhart Polynomials of Lattice Polyhedra

   Abstract. Let σ be a simplex of R ^N with vertices in the integral lattice Z ^N . The number of lattice points of mσ (={mα : α ∈ σ}) is a polynomial function L(σ,m) of m ≥ 0 . In this paper we present: (i) a formula for the coefficients of the polynomial L(σ,t) in terms of the elementary symmetric functions; (ii) a hyperbolic cotangent expression for the generating functions of the sequence L(σ,m) , m ≥ 0 ; (iii) an explicit formula for the coefficients of the polynomial L(σ,t) in terms of torsion. As an application of (i), the coefficient for the lattice n -simplex of R ⁿ with the vertices (0,. . ., 0, a _j , 0,. . . ,0) (1≤ j≤ n) plus the origin is explicitly expressed in terms of Dedekind sums; and when n=2 , it reduces to the reciprocity law about Dedekind sums. The whole exposition is elementary and self-contained.     

p-Adic dynamical systems of Chebyshev polynomials

We study the behaviour of the iterates of the Chebyshev polynomials of the first kind in p-adic fields. In particular, we determine in the field of complex p-adic numbers for p > 2, the periodic points of the p-th Chebyshev polynomial of the first kind. These periodic points are attractive points. We describe their basin of attraction. The classification of finite field extensions of the field of p-adic numbers ? _p , enables one to locate precisely, for any integer ν ≥ 1, the ν-periodic points of T _p : they are simple and the nonzero ones lie in the unit circle of the unramified extension of ? _p , (p > 2) of degree ν. This generalizes a result, stated by M. Zuber in his PhD thesis, giving the fixed points of T _p in the field ? _p , (p > 2). As often happens, we consider separately the case p = 2. Also, if the integer n ≥ 2 is not divisible by p, then any fixed point w of T _n is indifferent in the field of p-adic complex numbers and we give for p ≥ 3, the p-adic Siegel disc around w.     

When Some Complement of a Submodule Is a Summand

A module M is said to satisfy the C ₁₁ condition if every submodule of M has a (i.e., at least one) complement which is a direct summand. It is known that the C ₁ condition implies the C ₁₁ condition and that the class of C ₁₁-modules is closed under direct sums but not under direct summands. We show that if M = M ₁ ⊕ M ₂, where M has C ₁₁ and M ₁ is a fully invariant submodule of M, then both M ₁ and M ₂ are C ₁₁-modules. Moreover, the C ₁₁ condition is shown to be closed under formation of the ring of column finite matrices of size Γ, the ring of m-by-m upper triangular matrices and right essential overrings. For a module M, we also show that all essential extensions of M satisfying C ₁₁ are essential extensions of C ₁₁-modules constructed from M and certain subsets of idempotent elements of the ring of endomorphisms of the injective hull of M. Finally, we prove that if M is a C ₁₁-module, then so is its rational hull. Examples are provided to illustrate and delimit the theory.     

The Dimension of Subsets of Moran Sets Determined by the Success Run Behaviour of Their Codings

 Let be a Moran set associated with the set . Let Γ be a non-empty subset of with non-empty complement. Associated with the behaviour of success run of symbols from Γ in the coding space is a decomposition of F such that