Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: A short proof, based on mixed volumes, of Liggett’s theorem on the convolution of ultra-logconcave sequences. | A short proof based on mixed volumes of Liggett s theorem on the convolution of ultra-logconcave sequences Leonid Gurvits Los Alamos National Laboratory gurvits@ Submitted Aug 19 2008 Accepted Feb 10 2009 Published Feb 13 2009 Mathematics Subject Classification 05E99 Abstract R. Pemantle conjectured and T. M. Liggett proved in 1997 that the convolution of two ultra-logconcave is ultra-logconcave. Liggett s proof is elementary but long. We present here a short proof based on the mixed volume of convex sets. 1 Introduction Let a a0 am and b b0 bn be two real sequences. Their convolution c a b is defined as ck Pi j k aibj 0 k n m. A nonnegative sequence a a0 am is said to be logconcave if a2 aj-iaj i 1 i m 1 1 Following Permantle and 5 we say that a nonnegative sequence a a0 am is ultra-logconcave of order d m ULC d if the sequence d 0 i m is logconcave . 2 ai I ai-1 ai 1 I n Ta G . 1 i m - 1 2 d I d i d 7 ỵ i i_ 1 i 1 The next result was conjectured by R. Pemantle and proved by . Liggett in 1997 5 . Theorem The convolution of a ULC l sequence a and a ULC d sequence b is ULC l d . Remark It is easy to see by a standard perturbation argument that it is sufficient to consider a positive case a a0 a ai 0 0 i l and b b0 bd bi 0 0 i d THE ELECTRONIC JOURNAL OF COMBINATORICS 16 2009 N5 1 The relatively simple fact that the convolution of logconcave sequences is also logconcave was proved in 3 in 1949. I We present in this paper a short proof of Theorem . 2 The Minkowski sum and the mixed volume The Minkowski sum Definition 1. Let K1 K2 c Rn be two subsets of the Euclidean space Rn. Their Minkowski sum is defined as K1 K2 X Y X 2 K1 Y 2 K2 . The Minkowski sum is obviously commutative K1 K2 K2 K1 and associative K1 K2 K3 K1 K K3 . 2. Let A c R1 B c Rd. Their cartesian product is defined as A X B X Y 2 R1 d X 2 A Y 2 B . Define the next two subsets of R1 d Lift1 A X 0 2 R1 d X 2 A Lift2 B 0 Y 2 R1 d Y 2 B . 3 Then the next set .
