Computational Commutative Algebra and Combinatorics

ADVANCED STUDIESIN PURE MATHEMATICS
Chief Editor:

33

Eiichi Bannai (Kyushu University)

Computational CommutativeAlgebra and Combinatorics

Edited byTakayuki Hibi (Osaka University)

Mathematical Society of Japan

This book was typeset by AMS-TEX and AMS-LATEX, the TEX macro systemsof the American Mathematical Society, together with the style files aspm.styand aspmfm.sty for AMS-TEX written by Dr. Chiaki Tsukamoto andaspmproc.sty for AMS-LATEX written by Dr. Akihiro Munemasa.
TEX is a trademark of the American Mathematical Society.
c2002by the Mathematical Society of Japan.
All rights reserved. No part of this publication may be reproduced, stored ina retrieval system, or transmitted, in any form or by any means, electronic,mechanical, photocopying, recording or otherwise, without the prior permissionof the copyright owner.
Edited by the Mathematical Society of Japan.
Published by the Mathematical Society of Japan.
Distributed outside Japan by the American Mathematical Society.

ISBN 4-931469-17-5
2000 Mathematics Subject Classification.
Primary 05-06; Secondary 13-06.

Advanced Studies in Pure Mathematics 33
Chief Editor
Eiichi Bannai(Kyushu University)

Editorial Board of the Series
Hitoshi Arai

Eiichi Bannai

Yoshikazu Giga

(Univ. of Tokyo)(Kyushu Univ.)(Hokkaido Univ.)

Ki-ichiro Hashimoto

Kazuya KatoToshitake Kohno(Waseda Univ.)(Kyoto Univ.)(Univ. of Tokyo)

Yoichi Miyaoka

Seiki Nishikawa

Junjiro Noguchi(Univ. of Tokyo)(Tohoku Univ.)(Univ. of Tokyo)

Toshiyuki Tanisaki(Hiroshima Univ.)
PRINTED IN JAPANby Tokyo Shoseki Printing Co., Ltd.

Foreword
When the ﬁrst international conference on commutative algebra andcombinatorics was held in 1985 in Kyoto, the connections between combinatorics and commutative algebra were just becoming established. At
this meeting I had the pleasure of meeting a recently graduated studentof Professor Hideyuki Matsumura named Takayuki Hibi. One could not
fail to admire the tremendous enthusiasm and energy which he displayed
toward all aspects of mathematics, from his own research to the detailsof keeping the conference running smoothly. The conference turned out
to be a tremendous success and opened up many doorways to futurecollaboration between western and Japanese mathematicians in the exciting new area of “combinatorics and commutative algebra.” No one
has been a more tireless exponent of promoting this ﬁeld than Takayuki
Hibi. In particular, in addition to his proliﬁc and original research he has
been the main organizer of two subsequent highly successful meetings inJapan on combinatorics and commutative algebra.
The present volume constitutes the proceedings of the second ofthese two meetings and conﬁrms that the subject has lost none of its
original vitality. New techniques such as toric varieties and Gröbner
bases have greatly expanded the connections between combinatorics andcommutative algebra. For instance, there is now a well-developed theory of the set of all triangulations of a set of points in Euclidean spacethat uses sophisticated recent developments in both commutative algebra and combinatorics. A further important development of the subject
is the introduction of exterior algebra techniques, especially the theoryof algebraic shifting pioneered by Gil Kalai. His contribution to thepresent volume should become the deﬁnitive overview of this theory.
Just a glance through the titles of the papers contained here will show
the extent to which commutative algebra has pervaded other areas ofmathematics. Readers of all or part of these proceedings owe a debtof gratitude to Takayuki Hibi and his students Hidefumi Ohsugi andTomonori Kitamura for bringing together a plethora of diverse experts
in commutative algebra to Osaka and for arranging for so many of themto contribute high-quality articles to these proceedings. I look forward tomany future beautiful results stimulated by the contents of this volume.
18 April 2001
Richard Stanley
Cambridge, MassachusettsPreface
The 8th Mathematical Society of Japan International Research Institute “Computational Commutative Algebra and Combinatorics” washeld in Osaka University, Toyonaka Campus, Osaka, Japan, July 21 –July 30, 1999. The organizing committee consisted of Jürgen Herzog,Takayuki Hibi and Richard Stanley. The present volume ﬁlls the role ofthe proceedings of the meeting.
The meeting was devoted to informing participants of recent progress
and to stimulating new research in the computational aspects of combinatorics, commutative algebra, and related ﬁelds. Topics discussed included Hilbert functions, generic initial ideals, Gröbner bases, algebraic
shifting, toric varieties, convex polytopes, triangulations, and partiallyordered sets. More than a hundred participants, including 26 international participants from Bulgaria, Canada, Germany, India, Sweden, US,and Vietnam, attended the meeting.
Part I of the meeting, July 21 – 24, consisted of expository lecture
series for graduate students given by the ﬁve speakers, Jürgen Herzog,
Gil Kalai, Claudio Procesi, Vasudevan Srinivas, and Richard Stanley.
Each speaker gave three one-hour lectures. Part II of the meeting, July
26 – 30, consisted of 22 one-hour invited research talks.
The fascinating research area “combinatorics and commutative algebra” originates from a pioneered work by Richard Stanley in 1975 on aproof of the Upper Bound Conjecture for spheres by means of the theoryof Cohen–Macaulay rings. Since 1980, the geometry of toric variety has
played important roles to develop combinatorics on convex polytopes.
Moreover, in the early 90’s, the technique on Gröbner bases turned out
to be indispensable to study discrete structures on convex polytopes.
In Japan, there had been two international conferences on commutative algebra and combinatorics in the past; the US–Japan joint seminar on commutative algebra and combinatorics, Kyoto, 1985, and theICM 90 satellite conference on commutative algebra and combinatorics,Nagoya, 1990. The proceedings of the ﬁrst one were published in thisseries of the Advanced Studies in Pure Mathematics (volume 11, “Commutative Algebra and Combinatorics” (H. Matsumura and M. Nagata,Eds.), 1987). We hope the present volume will stimulate further developments in the computational aspects of combinatorics and commutativealgebra.
We wish to thank the Mathematical society of Japan for choosing
our research plan to be the topic of 1999 International Research Instituteand to thank the Japanese Associations of Mathematical Sciences forﬁnancial support to invite young researchers from several countries.

1 May 2001
Takayuki Hibi

All papers in this volume have been refereed and are in final form.
No version of any of them will be submitted for publication elsewhere.

CONTENTS
Winfried Bruns and Joseph Gubeladze — Polyhedral Algebras,
Arrangements of Toric Varieties, and their Groups

1Art M. Duval — Algebraic Shifting and Spectral Sequences

53

Vesselin Gasharov, Irena Peeva and Volkmar Welker — Coordinate Subspace Arrangements and Monomial Ideals

65Jürgen Herzog — Generic Initial Ideals and Graded Betti Numbers
75
Gil Kalai — Algebraic Shifting

121

Kayo Masuda — Certain Moduli of Algebraic G-vector Bundles
over Aﬃne G-varieties
165
Masayoshi Miyanishi — Completely Parametrized A1∗ -ﬁbrations
on the Aﬃne Plane
185
Marko Petkovšek, James Pommersheim and Irena Swanson —The Zarankiewicz Problem via Chow Forms
203
Claudio Procesi — Notes on the Topology of Hyperplane Arrangements and Braid Groups
213
Vasudevan Srinivas — Some Geometric Methods in CommutativeAlgebra231