From propp(at-sign)math.mit.edu Fri Jan 7 16:41:35 1994 To: combinatorics(at-sign)math.mit.edu The MIT combinatorics seminar will resume in February. Six speakers have already been scheduled, so it's definitely not too soon for you to let me know if you'd like to give a talk this semester. Jim Propp From propp(at-sign)math.mit.edu Tue Jan 25 11:20:59 1994 To: combinatorics(at-sign)math.mit.edu Subject: Combinatorics Seminar: February Schedule COMBINATORICS SEMINAR Here is a list of all talks currently scheduled for the month of February. Wednesday, February 2, 4:15 p.m.: Igor Pak, A resolution for skew-hook S_n-modules and combinatorial applications Friday, February 4, 4:15 p.m.: Gadi Moran, The r-majority action on 0-1 sequences Wednesday, February 9, 4:15 p.m.: Sergio Rajsbaum, Cycle-pancyclism in tournaments Friday, February 11, 4:15 p.m.: Andrei Zelevinsky, Representations of quivers of type A and the multisegment duality Wednesday, February 16, 4:15 p.m.: Francois Bergeron, Fourier transform formulas for descent algebras Friday, February 18, 4:15 p.m.: David Jackson, Some connections between maps on surfaces and symmetric functions Wednesday, February 23, 4:15 p.m.: Sergey Yuzvinsky, Combinatorial generators for logarithmic forms with poles along an arrangement of hyperplanes All talks, as usual, will meet in room 2-338. From propp(at-sign)math.mit.edu Thu Jan 27 12:53:39 1994 To: combinatorics(at-sign)math.mit.edu SEMINAR ON COMBINATORICS (HARVARD) Asymptotics of the Plancherel measure of the symmetric group Sergei Kerov (Visiting Harvard) Starting date: Tuesday, Feb 1, 1994 Time: 4:15 p.m. Place: Science Center 530. Sergei Kerov is visiting Harvard this term. We will run a weekly seminar on topics related to the celebrated results on limiting shape of Young diagrams. This relates the Plancherel measure on S_\infty to the hook formulae and hook walks. These in turn are related to Markov's moment problem and the distribution of zeros of the orthogonal polynomials. Nantel Bergeron and Persi Diaconis From propp(at-sign)math.mit.edu Sat Jan 29 14:30:15 1994 To: combinatorics(at-sign)math.mit.edu A new talk for February is being scheduled; Douglas Rogers will speak on February 25th. Details will be forthcoming. On another matter: A member of this mailing-list has asked to be removed from it, complaining about the amount of traffic unrelated to the MIT combinatorics seminar. My impression is that most people don't mind the other announcements that have been sent. (Correct me if I'm wrong!) Still, people should keep in mind the original purpose of this mailing-list. Jim Propp From propp(at-sign)math.mit.edu Mon Jan 31 15:46:55 1994 To: combinatorics(at-sign)math.mit.edu Subject: Pak, 2/2 Wednesday, February 2, 4:15 p.m.; MIT, room 2-338 Igor Pak (New York) A resolution for skew-hook S_n-modules and combinatorial applications Let F_n (x) be an inversion polynomial. It is well known that F_n (-1) = #{ sigma in S_n | sigma(1) < sigma(2) > sigma(3) < ... } Our main result is a generalization of this identity to symmetric functions. We also generalize this identity to any type of permutation. Our proof is based on a direct involution on a set of skew tableaux. Applications to tree-enumeration are given. From propp(at-sign)math.mit.edu Mon Jan 31 16:31:18 1994 To: combinatorics(at-sign)math.mit.edu Subject: Moran, 2/4 Friday, February 4, 4:15 p.m.; MIT, room 2-338 Gadi Moran (Haifa) The r-majority action on 0-1 sequences The r-majority action on a cyclic 0-1 sequence simultaneously replaces each digit by the majority digit of the 2r+1 (cyclic) interval it centers. The ultimate patterns obtained by iterating this action puzzled for a while its users - theoretical biologists. The talk will focus on the puzzle and its solution. From propp(at-sign)math.mit.edu Tue Feb 1 15:20:32 1994 To: combinatorics(at-sign)math.mit.edu Subject: Extended abstract of Gadi Moran's talk (February 4) Gadi Moran University of Haifa THE r-MAJORITY ACTION ON 0-1 SEQUENCES The r-majority action on a cyclic 0-1 sequence replaces simultaneously each digit by the majority digit of the 2r+1 (cyclic) interval it centers. The ultimate patterns obtained by iterating this action puzzled for a while its users - theorettcal biologists. The talk will focus on the puzzle and its solution. _________________________________________________________________________ Consider first an analogous linear operation of averaging an entry over the 2r+1 segment it centers. When this operation is iterated on any initial numerical cyclic sequence, an 'exponential' decay to a fixed-value-sequence occurs, the fixed value being the average value of the initial sequence. s When the liberty of averaging is replaced by the more restrictive (and not linear anymore) requirement of forcing one to choose one of two possible values, namely the more frequent one, we obtain the r-majority operation. As one would expect in passing into a quantized realm, the fixed ultimate sequences are replaced by a well defined hierarchy of r+1 "energy" levels into which the ultimate patterns of the r-majority split, labeled 0,...,r , with the population of the levels decreasing from 0 to r (the top level having only the two alternating sequences, ...0101..., ...1010...). We actually deal with this action on two way infinite sequences, and obtain all possible periodic (in time) patterns, all of which have period at most 2, and all but those of 0 energy are also space-periodic (with period bounded by 2r(r-1)). This time periodicity property - The Period Two Property (p2p) - is studied for the iteration of the majority operation on an arbitray (possibly infinite) locally finite graph (here one transforms an 0-1 vertex-labeled-graph into another one by simultaneously relabeling each vertex by the majority digit of its neighbors, leaving it unchanged in case of a tie). We come up with 'as wide as possible' class of graphs with this property. It turns out that the p2p is associated with two graph-theoretic properties, namely, a universal finite bound on the degrees and subexponential growth. Examples show that these two conditions are in fact indispensable in general. (A kind of "phase transition" seems to occur as you change your graph so that one of the above mentioned properties is lost). From propp(at-sign)math.mit.edu Mon Feb 7 15:15:23 1994 To: combinatorics(at-sign)math.mit.edu Subject: Rajsbaum, 2/9 Wednesday, February 9, 4:15 p.m.; MIT, room 2-338 Sergio Rajsbaum (UNAM and MIT) Cycle-pancyclism in tournaments Let T be a tournament of n vertices with a hamiltonian cycle gamma. The main result is that for any k, 3 leq k leq n, there exists a directed cycle C_k of length k with at most 4 arcs not in gamma. Depending on the relation between k and n even a larger intersection between C_k and gamma, denoted f(n,k), is guaranteed. In this work we characterize f(n,k). From propp(at-sign)math.mit.edu Mon Feb 7 15:44:17 1994 To: combinatorics(at-sign)math.mit.edu Subject: Zelevinsky, 2/11 Friday, February 11, 4:15 p.m.; MIT, room 2-338 Andrei Zelevinsky (Northeastern) Representations of quivers of type A and the multisegment duality In a joint work with A. Berenstein and H. Knight we study an involution which first appeared in the representation theory of reductive p-adic groups and affine Hecke algebras more than 10 years ago. More recently it was discovered to be related to quantum groups. This involution acts on the partitions of weights into the sum of positive roots of some root system. It can be defined in a quite elementary way, using only linear algebra (more specifically, representations of quivers). Our main result is an unexpectedly explicit formula for the involution: after some change of coordinates its every component is given as the minimum of a system of linear forms. The proof has a strong combinatorial flavor; it uses the "Max Flow = Min Cut" type theorem from the theory of network flows, and the results of S. Poljak describing the maximal rank of a power of a matrix with a given pattern of zeros. From propp(at-sign)math.mit.edu Tue Feb 8 13:18:49 1994 To: combinatorics(at-sign)math.mit.edu Subject: Gadi Moran preprints I have copies of Gadi Moran's extended one-page abstract, as well as copies of his articles: The r-Majority-Vote Action on 0-1 Sequences (preprint) On the Period-Two-Property of the Majority Operator in Infinite Graphs (preprint) Parametrization for Stationary Patterns of the r-Majority Operators on 0-1 sequences (preprint) Phase Transitions via Cellular Automata (manuscript, 3 Dec. 1993) Anyone who wants a copy (and has not already told me so) should contact me, by e-mail or by phone (253-6544), in the next few days. Jim From propp(at-sign)math.mit.edu Tue Feb 8 14:35:52 1994 To: combinatorics(at-sign)math.mit.edu Subject: Preview COMBINATORICS SEMINAR Here is a REVISED list of all remaining talks scheduled for the month of February. (Note the new talk on February 25.) Wednesday, February 9, 4:15 p.m.: Sergio Rajsbaum, Cycle-pancyclism in tournaments Friday, February 11, 4:15 p.m.: Andrei Zelevinsky, Representations of quivers of type A and the multisegment duality Wednesday, February 16, 4:15 p.m.: Francois Bergeron, Fourier transform formulas for descent algebras Friday, February 18, 4:15 p.m.: David Jackson, Some connections between maps on surfaces and symmetric functions Wednesday, February 23, 4:15 p.m.: Sergey Yuzvinsky, Combinatorial generators for logarithmic forms with poles along an arrangement of hyperplanes Friday, February 25, 4:15 p.m.: Douglas Rogers, title to be announced. All talks, as usual, will meet in room 2-338. From fomin(at-sign)math.mit.edu Tue Feb 8 19:41:37 1994 To: combinatorics(at-sign)math.mit.edu Subject: Bergeron, 2/14 MIT Applied Mathematics Colloquium Monday, February 14, 4:15 p.m.; MIT, room 2-105 Francois Bergeron (University of Quebec at Montreal) Standard Paths in the Composition Poset New results on path enumeration in the poset of compositions of integers will be presented, along with the steps that lead to establishing the statement and proofs of these results. These steps include computer algebra experiments, combinatorial constructions and solving differential equations for generating functions. Conjectures related to these questions will also be suggested. From propp(at-sign)math.mit.edu Fri Feb 11 16:07:01 1994 To: combinatorics(at-sign)math.mit.edu Subject: TODAY'S SEMINAR Andrei Zelevinsky's talk (originally scheduled for today) has been postponed until March 11. Jim Propp From propp(at-sign)math.mit.edu Fri Feb 11 16:57:34 1994 To: combinatorics(at-sign)math.mit.edu Subject: Bergeron, 2/16 Wednesday, February 16, 4:15 p.m.; MIT, room 2-338 Francois Bergeron (UQAM) Fourier transform formulas for descent algebras We present explicit Fourier transform formulas, with nice combinatorial interpretation involving eulerian numbers, for the center of Solomon's descent algebras for Coxeter groups of type An, Bn and some of the others. We illustrate how these results can be applied to card shuffling problems. From propp(at-sign)math.mit.edu Sun Feb 13 20:21:44 1994 To: combinatorics(at-sign)math.mit.edu Subject: Jackson, 2/18 Friday, February 18, 4:15 p.m.; MIT, room 2-338 David Jackson (Waterloo) Some connections between maps on surfaces and symmetric functions The genus series for maps is the generating series for embeddings of graphs on surfaces, with respect to the number of vertices, faces and edges. This series can be expressed as a character sum, and as an integral involving Hermitian complex matrices. Both representations of the genus series lead to combinatorial properties of maps. These maps arise independently in mathematical physics: for example, in connection with 2-dimensional quantum gravity, where vertex 4-regular maps are of particular interest. There is also interest in a seemingly unrelated question of determining a set of symmetric functions which have the same connection coefficients as the elements of the class algebra of the symmetric group. I will show how there is a relationship between this and the maps problem, and how information about one may assist the other. From propp(at-sign)math.mit.edu Wed Feb 16 18:06:10 1994 To: combinatorics(at-sign)math.mit.edu Subject: Jackson, 2/18 [Since connections with Harvard's computers have been down, I am re-sending this announcement; apologies to non-Harvard people.] Friday, February 18, 4:15 p.m.; MIT, room 2-338 David Jackson (Waterloo) Some connections between maps on surfaces and symmetric functions The genus series for maps is the generating series for embeddings of graphs on surfaces, with respect to the number of vertices, faces and edges. This series can be expressed as a character sum, and as an integral involving Hermitian complex matrices. Both representations of the genus series lead to combinatorial properties of maps. These maps arise independently in mathematical physics: for example, in connection with 2-dimensional quantum gravity, where vertex 4-regular maps are of particular interest. There is also interest in a seemingly unrelated question of determining a set of symmetric functions which have the same connection coefficients as the elements of the class algebra of the symmetric group. I will show how there is a relationship between this and the maps problem, and how information about one may assist the other. From propp(at-sign)math.mit.edu Fri Feb 18 14:40:21 1994 To: combinatorics(at-sign)math.mit.edu Subject: Yuzinsky, 2/23 Wednesday, February 23, 4:15 p.m.; MIT, room 2-338 Sergey Yuzvinsky (Oregon and Northeastern) Combinatorial generators for logarithmic forms with poles along an arrangement of hyperplanes If L is the intersection lattice of a central arrangement A of hyperplanes then every element X of L of rank 2 produces a logarithmic 1-form f(X) with poles along the union D of the hyperplanes. A neccessary and sufficient condition is given for these forms to generate the whole module of logarithmic 1-forms with poles along D. A free graded resolution of this module is exhibited. We also discuss cohomology of the complex of logarithmic forms with certain differentials. From propp(at-sign)math.mit.edu Fri Feb 18 15:05:15 1994 To: combinatorics(at-sign)math.mit.edu Subject: Rogers, 2/25 Friday, February 25, 4:15 p.m.; MIT, room 2-338 Douglas Rogers (Northern Territory and Bowling Green) A matrix method for counting Hamitonian cycles on grids The talk provides a general account of renewal sequences and the transfer matrix method, illustrated in the example of counting Hamitonian cycles on grids of fixed width. From propp(at-sign)math.mit.edu Wed Feb 23 18:27:18 1994 To: combinatorics(at-sign)math.mit.edu Subject: Combinatorics Seminar: March Schedule COMBINATORICS SEMINAR Here is a list of all talks currently scheduled for the month of March. Wednesday, March 2, 4:15 p.m.: Gabor Hetyei, Edge-orientable cubical polytopes and a conjecture of Eisenbud, Green and Harris Friday, March 4, 4:15 p.m.: Sergei Kerov, Random Young tableaux and Selberg integrals Wednesday, March 9, 4:15 p.m.: Richard Ehrenborg, Simple and multiplex juggling sequences Friday, March 11, 4:15 p.m.: Andrei Zelevinsky, Representations of quivers of type A and the multisegment duality Wednesday, March 16, 4:15 p.m.: George Andrews, q-Series and random graphs Wednesday, March 30, 4:15 p.m.: Jim Propp, Domino tilings and the arctic circle conjecture All talks will meet in room 2-338. From propp(at-sign)math.mit.edu Fri Feb 25 15:58:25 1994 To: combinatorics(at-sign)math.mit.edu Subject: Tardif, 2/28 Monday, February 28, 4:15 p.m.; MIT, room 2-338 Claude Tardif (Montreal) On graphs homomorphically equivalent to their cartesian powers Let G^n denote the n-th power of a graph G under the cartesian product. We investigate the properties of graphs admitting a homomorphism f: G^(n+1) --> G^n, for a certain integer n. These questions arise in the study of the ultimate independence ratio of a graph and other related parameters. Our findings are the following: Theorem 1: A graph G admits a homomorphism f: G^2 --> G if and only if it is homomorphically equivalent to a normal Cayley graph. Theorem 2: Let G be an edge-transitive graph. If there exists an n such that there is a homomorphism f: G^(n+1) --> G^n , then there is a homomorphism g: G^2 --> G. Theorem 3: For each n > 1, there exists a Cayley graph G such that there exists a homomorphism f: G^(n+1) --> G^n , but no homomorphism g: G^n --> G^(n-1). From propp(at-sign)math.mit.edu Fri Feb 25 16:06:56 1994 To: combinatorics(at-sign)math.mit.edu Subject: Hetyei, 3/2 Wednesday, March 2, 4:15 p.m.; MIT, room 2-338 Gabor Hetyei (M.I.T.) Edge-orientable cubical polytopes and a conjecture of Eisenbud, Green and Harris Consider a polynomial ring in n variables and an ideal of it which contains an n-element homogeneous system of parameters of degree two. Eisenbud, Green and Harris conjecture that the h-vector of the factor of the ring by such an ideal is the f-vector of a simplicial complex. They illustrate their conjecture with the ideal generated by the squares of the variables. We will see an infinite set of other examples which occur in the study of the Stanley ring of cubical polytopes. We show that the face ideal of the boundary complex of a convex cubical polytope is generated by homogeneous forms of degree two. Then we show a numbering of the vertices of an edge-orientable shellable cubical complex which allows us to construct a completely balanced triangulation of such cubical complexes. Finally we will use Stanley's result claiming that the h-vector of a completely balanced simplicial complex is the f-vector of another simplicial complex. Most of the proofs presented will be geometric and combinatorial, and the constructions might be of interest even for those unfamiliar with the commutative algebraic background. From propp(at-sign)math.mit.edu Mon Feb 28 15:30:27 1994 To: combinatorics(at-sign)math.mit.edu Subject: Kerov, 3/4 Friday, March 4, 4:15 p.m.; MIT, room 2-338 Sergei Kerov (St. Petersburg and Harvard) Random Young tableaux and Selberg integrals Let M_n denote the distribution of the fraction of black balls in a Polya urn after n balls were drawn (at each stage the extracted ball returns to the urn along with a new ball of the color drawn). If the initial urn contained A black and B white balls, the limit of M_n is well known to be the beta distribution. The beta integral follows: Gamma(A+B) ----------------- Integral_0^1 x^{A-1} (1-x)^{B-1} dx = 1 Gamma(A) Gamma(B) I will describe a Markov chain (similar to Polya urns) on the set of Young diagrams and use it to derive the following Selberg type integral: Integral_{Delta_m} Z_lambda (t; 1/theta) times Product_{1 leq i < j leq m} |t_i - t_j|^{2 theta} times Product_{j=1}^m t_j^{A-1} dt_1 ... dt_{m-1} = Z_lambda (1,...,1; 1/theta) ------------------------------ times Gamma(N + A m + (m-1) m theta) Gamma(lambda_j + A + (m-j) theta) Gamma(j theta + 1) Product_{j=1}^m ---------------------------------------------------- . Gamma(theta + 1) Here Z_lambda are zonal (Jack) symmetric polynomials, and Delta_m is the standard simplex Delta_m = {t=(t_1,...,t_m) in R_+^m: t_1+...+t_m = 1}. From propp(at-sign)math.mit.edu Mon Feb 28 15:42:01 1994 To: combinatorics(at-sign)math.mit.edu Subject: Dinner It's time once again for a Discrete Dinner together. This time, the venue will be Bertucci's, right near MIT; the cost will be $10 for grad students and undergraduates and $15 for professors (tax and tip included). I hope that the closeness to campus and the low cost of the meal will lead more graduate students and undergraduates to attend than has been the case in recent semesters. Proposed dates are March 9, March 16, and March 30. Send me your votes and I'll pick the most popular of the three dates. Jim Propp From propp(at-sign)math.mit.edu Mon Feb 28 18:02:41 1994 To: combinatorics(at-sign)math.mit.edu Subject: Re: dinner I've just realized that March 30 is during Passover, so that some people who would normally attend the dinner would not be able to. I'll put April 6 forward as an additional proposed day. Jim From propp(at-sign)math.mit.edu Tue Mar 1 14:42:50 1994 To: combinatorics(at-sign)math.mit.edu Subject: Discrete Dinner I've been proposing Wednesday dates, but several people have said that Wednesday is the one day of the week that's nearly always impossible for them, so I'd like to put Fridays under consideration, too. However, I don't know which Fridays yet. So, hold off for a bit, and don't send me any more replies about my proposed dinner-dates; I will have an emended list of proposed dates by the end of the week. Jim From propp(at-sign)math.mit.edu Fri Mar 4 15:31:14 1994 To: combinatorics(at-sign)math.mit.edu Subject: Ehrenborg, 3/9 Wednesday, March 9, 4:15 p.m.; MIT, room 2-338 Richard Ehrenborg (UQAM) Simple and multiplex juggling sequences We study juggling patterns where the juggler can only catch and throw one ball at a time (simple juggling), and patterns where the juggler can handle many balls at the same time (multiplex juggling). Using a crossing statistic, we obtain explicit q-enumeration formulas. Our techniques give a natural interpretation of the q-Stirling numbers of the second kind (equivalent to Garcia and Remmel's rook placements) and a bijective proof of an identity of Carlitz. This is joint work with Margaret Readdy. From propp(at-sign)math.mit.edu Fri Mar 4 15:38:02 1994 To: combinatorics(at-sign)math.mit.edu Subject: Zelevinsky, 3/11 (this time for sure!) Friday, February 11, 4:15 p.m.; MIT, room 2-338 Andrei Zelevinsky (Northeastern) Representations of quivers of type A and the multisegment duality In a joint work with A. Berenstein and H. Knight we study an involution which first appeared in the representation theory of reductive p-adic groups and affine Hecke algebras more than 10 years ago. More recently it was discovered to be related to quantum groups. This involution acts on the partitions of weights into the sum of positive roots of some root system. It can be defined in a quite elementary way, using only linear algebra (more specifically, representations of quivers). Our main result is an unexpectedly explicit formula for the involution: after some change of coordinates its every component is given as the minimum of a system of linear forms. The proof has a strong combinatorial flavor; it uses the "Max Flow = Min Cut" type theorem from the theory of network flows, and the results of S. Poljak describing the maximal rank of a power of a matrix with a given pattern of zeros. From propp(at-sign)math.mit.edu Fri Mar 4 15:45:36 1994 To: combinatorics(at-sign)math.mit.edu Subject: Discrete Dinner; revised list of dates The REVISED proposed dates for the Discrete Dinner at Bertucci's are: Friday, March 11 Wednesday, March 16 Wednesday, March 30 Friday, April 1 Wednesday, April 6 Friday, April 8 Please let me know which days you prefer, and which days are simply impossible for you. Jim From propp(at-sign)math.mit.edu Tue Mar 8 11:13:46 1994 To: combinatorics(at-sign)math.mit.edu Subject: TODAY: counting lattice points in polytopes The following may be of interest to some subscribers to this mailing list: (MOSTLY) SYMPLECTIC GEOMETRY SEMINAR Tuesday, March 8, 3 pm MIT, Room 4-153 James Pommersheim (M.I.T.) "The Todd Class of a Toric Variety" ABSTRACT: Finding formulas for the Todd class of a toric variety is an interesting problem partly because such formulas allow one to give formulas for the number of lattice points in an integral convex polytope. In this talk, we show that Todd class of a simplicial toric variety has a canonical expression in terms of products of torus- invariant divisors. The coefficients in this expression, which generalize the classical Dedekind sum, are shown to satisfy a reciprocity relatio which characterizes them uniquely. From propp(at-sign)math.mit.edu Wed Mar 9 13:57:50 1994 To: combinatorics(at-sign)math.mit.edu Subject: George Andrews' talk on 3/14 The Applied Mathematics Colloquium this coming Monday may be of interest to many subscribers to this list. George Andrews will speak in room 2-105 at 4:15 p.m. on Monday, March 14. His talk will be entitled "The Borwein Conjectures". Abstract: Several years ago Peter Borwein considered questions concerning the nonnegativity of coefficients of a family of modular forms. In his empirical studies of these questions he found several fascinating sequences of polynomials which converge to the forms he was treating and possessed this same nonnegativity property. In this talk we shall extend some of Borwein's original conjectures and indicate their relationship to classical Rogers- Ramanujan type identities. Unfortunately (or perhaps fortunately) the most interesting conjectures still remain open. From propp(at-sign)math.mit.edu Wed Mar 9 17:53:50 1994 To: combinatorics(at-sign)math.mit.edu Subject: schedule change The seminar speaker on March 30 will be Robert Calderbank (not Jim Propp as originally scheduled). Calderbank will speak on "The linearity of several notorious families of nonlinear codes". I will post an abstract for the talk when it becomes available. Jim Propp's lecture "Domino tilings and the arctic circle conjecture" will be postponed until early April. From propp(at-sign)math.mit.edu Wed Mar 9 17:55:15 1994 To: combinatorics(at-sign)math.mit.edu Subject: Discrete Dinner I plan to choose the date for the Discrete Dinner on Friday, so anyone who hasn't replied to my latest request for preferences (the one wher I specified three Wednesdays and three Fridays) should reply by Thursday afternoon at the latest. (It goes without saying that this coming Friday is no longer in the running as one of the possible days for the Dinner.) Jim Propp From propp(at-sign)math.mit.edu Fri Mar 11 14:45:08 1994 To: combinatorics(at-sign)math.mit.edu Subject: First talk by Robert Calderbank, 3/29 The following expository talk (to be given on Tuesday, March 29, under the auspices of the Electrical Engineering department) may be of interest to those who plan to attend Robert Calderbank's more technical talk in the Combinatorics Seminar on the following day: The Linearity of Several Notorious Families of Nonlinear Binary Codes A. R. Calderbank Mathematical Sciences Research Center AT&T Bell Labs, Murray Hill, NJ 07974 Abstract: Error-correcting and error-detecting codes play important roles in applications ranging from data networking to satellite communication to compact disks. Most coding theory emphasizes ``linear codes''. Here the codewords are vectors with entries in some finite field, and the code is closed under vector addition and multiplication by scalars from the finite field. Linear codes have a clean structure that makes them simpler to discover, to understand, and to encode and decode. However, in order to get the largest possible number of codewords with a fixed block size and correction capability (the most ``efficient'' code), it is sometimes necessary to consider more general codes, having little or no special structure to them. Some of the best known examples of nonlinear binary error-correcting codes that are better than any corresponding linear code are the Nordstrom- Robinson, Kerdock, and Preparata codes. The Nordstrom-Robinson and Preparata codes, for example, are twice as large as the best possible linear codes for the same parameters. The Kerdock and Preparata codes have long been known to be ``dual'' to one another in a particular formal sense, even though mathematically _duality_ is defined only for linear codes. The sense in which they ``look like duals'' is that the MacWilliams transform of the distance distribution of one yields the distance distribution of the other. (This property is known always to hold for linear codes that actually are duals of one another.) For roughly 20 years this curious observation has left coding theorists with the open question of whether these non-linear codes might not be duals in some stronger sense. Roger Hammons (Hughes), Vijay Kumar (USC), Neil Sloane (AT\&T-BL), Patrick Sol\'{e} (CNRS) and the speaker have now resolved this question by showing that the Kerdock and Preparata codes are in fact linear, if one views them in the right way over the ring of integers mod 4 instead of the binary field, and that, over this larger ring, the two codes _are_ mathematical duals. The mappings between the binary and mod 4 versions of the codes are extremely simple. Further implications of this revelation are under study. For details on place and time, contact Mitchell Trott (253-2359; trott(at-sign)lids.mit.edu). From propp(at-sign)math.mit.edu Fri Mar 11 16:15:59 1994 To: combinatorics(at-sign)math.mit.edu Subject: Second talk by Robert Calderbank, 3/30 Wednesday, March 30, 4:15 p.m.; MIT, room 2-338 Robert Calderbank (Bell Labs) Codes, geometries and extremal sets of Euclidean lines with prescribed angles We describe how Kerdock codes over the binary field Z_2 and over the ring Z_4 of integers modulo 4 determine extremal sets of lines in real and complex Euclidean space with only 2 angles. Extraspecial 2-groups will serve as the bridge between discrete and Euclidean geometries. These connections involve a correspondence between binary orthogonal and symplectic geometries that is expressed as a map between binary symmetric m-by-m matrices and binary skew-symmetric (m+1)-by-(m+1) matrices. From propp(at-sign)math.mit.edu Fri Mar 11 16:19:56 1994 To: combinatorics(at-sign)math.mit.edu Subject: Discrete Dinner By popular demand, this semester's discrete dinner will be on Friday, April 8. Stay tuned for further details. Jim Propp From propp(at-sign)math.mit.edu Mon Mar 14 13:00:32 1994 To: combinatorics(at-sign)math.mit.edu Subject: Discrete Dinner This semester's Discrete Dinner will be held on Friday, April 8 at 6 p.m. at Bertucci's Brick Oven Pizzeria (799 Main Street in Cambridge). The cost will be $10 for grad students and undergraduates and $15 for professors (tax and tip included). I hope that the closeness to campus and the low cost of the meal will lead more graduate students and undergraduates to attend than has been the case in recent semesters. Please let me know by April 1 (and preferably electronically) your probability of attendance. (The sum of these probabilities has proved to be a reliable indicator of the number of people who actually attend.) Jim Propp From propp(at-sign)math.mit.edu Mon Mar 14 14:07:58 1994 To: combinatorics(at-sign)math.mit.edu Subject: Andrews, 3/16 Wednesday, March 16, 4:15 p.m.; MIT, room 2-338 George Andrews (Penn State) q-Series and random graphs This talk describes joint work with Simon and Crippa (ETH, Zurich) on a probability distribution connected with random graphs. The study of the moments of the distribution requires some old and some new results in q-series. The talk concludes with comments on related work by Dilcher, and open questions. From propp(at-sign)math.mit.edu Fri Mar 18 17:21:17 1994 To: combinatorics(at-sign)math.mit.edu Subject: Combinatorics Seminar: April Schedule COMBINATORICS SEMINAR Here is a list of all talks scheduled for the month of April. Wednesday, April 6, 4:15 p.m.: Jim Propp, Domino tilings and the arctic circle conjecture Friday, April 8, 4:15 p.m.: Tom Sundquist, A 3-variable Pfaffian identity Wednesday, April 13, 4:15 p.m.: Gunter Ziegler, The random walks on digraphs corresponding to some interesting linear programs Friday, April 15, 4:15 p.m.: Peter McMullen, Face-vectors of simple convex polytopes Wednesday, April 20, 4:15 p.m.: Alexander Barvinok, Efficient counting of lattice points in polytopes Wednesday, April 27, 4:15 p.m.: Peter Shor, Keller's conjecture Friday, April 29, 4:15 p.m.: Lauren Rose, Splines on polyhedral complexes All talks will meet in room 2-338. From propp(at-sign)math.mit.edu Thu Mar 31 16:29:17 1994 To: combinatorics(at-sign)math.mit.edu Subject: Combinatorics Seminar: April Schedule (revised) COMBINATORICS SEMINAR Here is a revised list of all talks scheduled for the month of April. Note the new talk that has been added on Monday, April 25 at a non-standard time. Wednesday, April 6, 4:15 p.m.: Jim Propp, Domino tilings and the arctic circle conjecture Friday, April 8, 4:15 p.m.: Tom Sundquist, A 3-variable Pfaffian identity Wednesday, April 13, 4:15 p.m.: Gunter Ziegler, The random walks on digraphs corresponding to some interesting linear programs Friday, April 15, 4:15 p.m.: Peter McMullen, Face-vectors of simple convex polytopes Wednesday, April 20, 4:15 p.m.: Alexander Barvinok, Efficient counting of lattice points in polytopes Monday, April 25, 2:00 p.m.: Qiao Li, Restricted connectivity and restricted fault diameter of interconnection networks Wednesday, April 27, 4:15 p.m.: Peter Shor, Keller's conjecture Friday, April 29, 4:15 p.m.: Lauren Rose, Splines on polyhedral complexes All talks will meet in room 2-338. From propp(at-sign)math.mit.edu Mon Apr 4 13:28:13 1994 To: combinatorics(at-sign)math.mit.edu Subject: Dinner on Friday This is just a final reminder that those of you who haven't already notified me about the likelihood of your attending the Discrete Dinner on Friday should let me know today or tomorrow, unless your probability of attendance is very close to zero. Jim From propp(at-sign)math.mit.edu Mon Apr 4 15:47:51 1994 To: combinatorics(at-sign)math.mit.edu Subject: Propp, 4/6 Wednesday, April 6, 4:15 p.m.; MIT, room 2-338 Jim Propp (M.I.T.) Domino tilings and the arctic circle conjecture I will discuss some surprising recent discoveries concerning the behavior of domino tilings of certain finite regions. In particular, there is a sharply-defined boundary between the portion of the tiling that is likely to be purely orderly and the portion of the tiling that is likely to be jumbled, and the asymptotic shape of the boundary is a perfect circle. Related to this behavior is a rational function in three variables whose coefficients have an unusual fractal structure. No prior familiarity with domino tilings will be assumed. From propp(at-sign)math.mit.edu Mon Apr 4 16:20:35 1994 To: combinatorics(at-sign)math.mit.edu Subject: Sundquist, 4/8 Friday, April 8, 4:15 p.m.; MIT, room 2-338 Tom Sundquist (Dartmouth) A 3-variable Pfaffian identity In his 1990 paper ``Non-intersecting paths, Pfaffians and plane partitions'' John Stembridge mentions that the Pfaffian of a certain skew-symmetric matrix, whose entries are rational functions in the variables x_1,...,x_{2n}, has an evaluation which factors into linear factors. Interestingly, the numerator is exactly the evaluation of the Vandermonde determinant. Recent work has lead to a 2-variable generalization of this formula in which the numerator Vandermonde determinant is replaced by the skew-symmetrization of a certain monomial in the variables x_1,...,x_{2n}, and y_1,...,y_{2n}. More recently, a 3-variable generalization, involving x_1,...,x_{2n}, y_1,...,y_{2n}, and z_1,...,z_{2n}, has been discovered. We will present a sign-reversing involution proof of the 3-variable Pfaffian identity. We also discuss several variants of these identities, as well as some applications to symmetric function theory. From propp(at-sign)math.mit.edu Fri Apr 8 16:22:27 1994 To: combinatorics(at-sign)math.mit.edu Subject: Ziegler, 4/13 Wednesday, April 13, 4:15 p.m.; MIT, room 2-338 Gunter Ziegler (ZIB Berlin) The random walks on digraphs corresponding to some interesting linear programs Consider the following ``game'' KM(n), played on binary strings of length n: choose a random ``1'', and flip this bit together with all the bits to the right of it. What is the expected number of steps this game will take until it terminates with the zero-string? An upper bound of (n+1 choose 2) is easy, but better-than-linear lower bounds are surprisingly difficult to get. We obtain an Omega(n^2 / log(n)) lower bound. The game KM(n) corresponds a random walk on the cube graph (with edges directed according to a Hamilton path), and thus to the simplex algorithm on the n-dimensional ``Klee-Minty cube'' with a RANDOM pivot rule. Thus its analysis leads to super-linear lower bounds for the RANDOM pivot rule on linear programs. (Joint work with Bernd Gartner, Berlin) From propp(at-sign)math.mit.edu Fri Apr 8 17:52:30 1994 To: combinatorics(at-sign)math.mit.edu Subject: McMullen, 4/15 Friday, April 15, 4:15 p.m.; MIT, room 2-338 Peter McMullen (University College, London) Face-vectors of simple convex polytopes The monograph ``Convex Polytopes'' by Branko Grunbaum, published in 1967, considerably revitalized its eponymous subject. Much of the book was focussed on the problems of determining which sequences (f_0, f_1, ..., f_{d-1}) could be the _f-vectors_ of d-polytopes P, that is, f_j = f_j (P) is the number of j-faces of P, either in general, or in some special classes. In fact, since many such problems seemed hopelessly difficult at that time, rather more restricted questions were often asked, such as bounds for some of the f_{j} in terms of others. As one consequence of the book, in 1970 the present speaker conjectured an exact description of the f-vectors of simplicial (or, equivalently, simple) d-polytopes. Much subsequent research into polytopes was centred around this conjecture; it was finally confirmed around 1979--80. The sufficiency of the conditions of the conjecture (often now called _McMullen's_conditions_) was due to Billera and Lee, using a direct, if ingenious, geometric construction. The necessity was proved by Stanley; however, this involved deep results from algebraic geometry, namely the hard Lefschetz theorem applied to the cohomology ring of the toric variety associated with a rational simple polytope. There was thus considerable interest in finding a proof of the necessity which stuck more closely to polytope theory. In 1992, the present speaker found such a proof; it used his own recently invented _polytope_ _algebra_, which was originally devised to investigate translation-invariant valuations on polytopes, such as volume, surface area and the Euler characteristic. Even more recently, it has been becoming clear that a great deal of the complicated machinery of the polytope algebra can itself be discarded. For one thing, the construction of the polytope algebra can be simplified. But, even more usefully, only a certain amount of the framework of the polytope algebra appears to be needed. In the talk, we describe this new approach. From propp(at-sign)math.mit.edu Sun Apr 10 22:51:35 1994 To: combinatorics(at-sign)math.mit.edu Subject: Harvard Combinatorics Seminar, 4/12 SEMINAR ON COMBINATORICS (HARVARD) Domino tilings and the arctic circle conjecture Jim Propp (MIT) Date: Tuesday, Apr 12, 1994 Time: 4:15 p.m. Place: Science Center 530. Abstract: I will discuss some surprising recent discoveries concerning the behavior of domino tilings of certain finite regions. In particular, there is a sharply-defined boundary between the portion of the tiling that is likely to be purely orderly and the portion of the tiling that is likely to be jumbled, and the asymptotic shape of the boundary is a perfect circle. Related to this behavior is a rational function in three variables whose coefficients have an unusual fractal structure. No prior familiarity with domino tilings will be assumed. (This will be identical to the talk given at MIT last Wednesday, except that some mistakes have been corrected [and the speaker will arrive on time!].) From propp(at-sign)math.mit.edu Thu Apr 14 14:31:48 1994 To: combinatorics(at-sign)math.mit.edu Subject: Barvinok, 4/20 Wednesday, April 20, 4:15 p.m.; MIT, room 2-338 Alexander Barvinok (Cornell) Efficient counting of lattice points in polytopes We describe several algorithmic results concerning lattice point counting. These results include a polynomial time algorithm for counting lattice points in polytopes in a fixed dimension, a polynomial time algorithm for counting lattice points in totally unimodular polytopes given by their vertices, and a polynomial time reduction of the computation of the highest Ehrhart coefficients to the volume computation. The exposition is centered about Brion's formula for exponential sums over a polytope which reduces the original problem to ``counting'' lattice points in the supporting cones at the vertices of the polytope. The other ingredient is a procedure for ``resolution of singularities'', that is a representation of a given rational polyhedral cone as a linear combination of unimodular cones. From nantel(at-sign)math.harvard.edu Thu Apr 14 16:36:22 1994 To: combinatorics(at-sign)math.mit.edu Subject: Harvard Combinatorics SEMINAR ON COMBINATORICS at HARVARD Eric R. Rains (Harvard) Increasing Subsequences and the Unitary Group Tuesday, Apr. 19, 1994 4:15 PM Science Center 530 From fomin(at-sign)math.mit.edu Fri Apr 15 13:30:12 1994 To: combinatorics(at-sign)math.mit.edu Subject: Randall, 4/19 TUESDAY, APRIL 19, 1994, 3:30, NE43-518 Refreshments at 3:15 Counting in Lattices: Combinatorial Problems from Statistical Mechanics Dana Randall University of California, Berkeley We consider two classical combinatorial problems arising in statistical mechanics: counting matchings and self-avoiding walks in lattice graphs. The first problem arises in the study of the thermodynamical properties of monomers and dimers (diatomic molecules) in crystals. Fisher, Kasteleyn and Tem- perley discovered an elegant technique to exactly count the number of perfect matchings in two dimensional lattices, but it is not applicable for matchings of arbitrary size, or in higher dimensional lattices. We present the first efficient approx- imation algorithm for computing the number of matchings of any size in any d-dimensional periodic lattice. The algorithm is based on Monte Carlo simulation of a suitable Markov chain and has rigorously derived performance guarantees that do not rely on any assumptions. Counting self-avoiding walks in lattices arises in the study of the thermodynamics of long polymer chains in dilute solution. While there there are a number of Monte Carlo algorithms used to count self-avoiding walks in practice, these are heuristics and their correctness relies on unproven conjectures. In contrast, we present an efficient algorithm which relies on a single, widely- believed conjecture that is simpler than preceding assumptions and, more importantly, is one which the algorithm itself can test. Thus our algorithm is reliable, in the sense that it either outputs answers that are guaranteed, with high probability, to be correct, or finds a counterexample to the conjecture. (This is joint work with Claire Kenyon and Alistair Sinclair.) From propp(at-sign)math.mit.edu Thu Apr 21 13:15:22 1994 To: combinatorics(at-sign)math.mit.edu Subject: Li, 4/25 Monday, April 25, 2:00 p.m.; MIT, room 2-338 (note unusual date and time!) ^^^^^^^^^ Qiao Li (China) Restricted connectivity and restricted fault diameter of interconnection networks The restricted connectivity and restricted fault diameter are two reliability measures for interconnection networks, where we assume that all the neighbors of any vertex do not fail at the same time. By computing these two parameters for some well-known network families, we reaffirm that "These good network families are really good." Such recently proposed graph theoretical concepts as container and wide diameter prove to be useful in this investigation. Some open problems will also be presented. From propp(at-sign)math.mit.edu Thu Apr 21 13:22:43 1994 To: combinatorics(at-sign)math.mit.edu Subject: Shor, 4/27 Wednesday, April 27, 4:15 p.m.; MIT, room 2-338 Peter Shor (Bell Labs) Keller's conjecture In 1930, O. H. Keller conjectured that any tiling of Euclidean n-space by cubes always contains two cubes that meet in a complete n-1 dimensional facet. This was disproved in 1992 when Jeff Lagarias and I found a 10-dimensional counterexample. I will trace the history of Keller's conjecture for nearly 100 years, from a 1896 question of Minkowski on simultaneous approximation, of which Keller's conjecture is a generalization, through Hajos' resolution of Minkowski's conjecture via abelian groups, then Szabo's reduction of Keller's conjecture to a graph theory question that led to the counter-example and finally to a generalization of the counter-example, which appears to be related to coding theory. From nantel(at-sign)math.harvard.edu Thu Apr 21 15:35:50 1994 To: combinatorics(at-sign)math.mit.edu Subject: Re: Shor, 4/27 Cc: maia(at-sign)math.harvard.edu, nantel(at-sign)math.harvard.edu HARVARD SEMINAR on COMBINATORICS The Structure of the Universal Exponential Solution of the Yang-Baxter Equation Nantel Bergeron Tuesday Apr. 26 4:15 PM Science Center 530 From nantel(at-sign)math.harvard.edu Thu Apr 21 15:43:37 1994 To: combinatorics(at-sign)math.mit.edu Subject: HARVARD SEMINAR on COMBINATORICS Cc: nantel(at-sign)math.harvard.edu Oups!... Sorry, > HARVARD SEMINAR on COMBINATORICS > > The Structure of the Universal Exponential > Solution of the Yang-Baxter Equation > > Nantel Bergeron > > Tuesday Apr. 26 > 4:15 PM > Science Center 530 > From propp(at-sign)math.mit.edu Sun Apr 24 00:45:18 1994 To: combinatorics(at-sign)math.mit.edu Subject: Combinatorics Seminar: May Schedule COMBINATORICS SEMINAR Here is a preliminary list of talks scheduled for the end of the month of April and for the month of May. Wednesday, April 27, 4:15 p.m.: Peter Shor, Keller's conjecture Friday, April 29, 4:15 p.m.: Lauren Rose, Splines on polyhedral complexes Monday, May 2, 4:15 p.m.: Andrei Zelevinsky, Flows in networks and the multisegment duality Wednesday, May 4, 4:15 p.m.: Klaus Altmann, Minkowski sums and the versal deformation of toric singularities Friday, May 6, 4:15 p.m.: Erwin Lutwak, A discrete version of the Minkowski problem Wednesday, May 11, 4:15 p.m.: Alan Edelman, Hadamard matrices and the Gaussian elimination pivot conjecture Friday, May 13, 4:15 p.m.: George Markowsky, The poset of irreducibles: a basis for lattice theory Monday, May 16, 4:15 p.m.: Mike Hawrylycz, Geometric identities in invariant theory All talks will meet in room 2-338. From propp(at-sign)math.mit.edu Mon Apr 25 12:32:52 1994 To: combinatorics(at-sign)math.mit.edu Subject: Rose, 4/29 Friday, April 29, 4:15 p.m.; MIT, room 2-338 Lauren Rose (Wellesley, M.I.T., and Bunting Institute) Splines on polyhedral complexes For a polyhedral subdivision D of d-dimensional Euclidean space, we consider piecewise polynomial functions on D which are differential of order r. These functions are known as "splines" and are used in many areas of mathematics and applied mathematics. For a fixed r, the set of all r-splines on D is a module over the polynomial ring in d variables over the reals. The goal of this work is to study to what extent the algebraic properties of the module are determined by the topological and combinatorial properties of D. In particular, we will describe a large class of complexes for which freeness or homological dimension of the module is a topological or combinatorial property. We will also indicate how the geometry of D comes into play in the general case. From propp(at-sign)math.mit.edu Mon Apr 25 17:58:57 1994 To: combinatorics(at-sign)math.mit.edu Subject: May schedule (revised) COMBINATORICS SEMINAR Here is a revised list of talks scheduled for the month of May. * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Note that the talk by Andrei Zelevinsky originally scheduled * * for Monday, May 2 has been postponed to Monday, May 9. * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Wednesday, May 4, 4:15 p.m.: Klaus Altmann, Minkowski sums and the versal deformation of toric singularities Friday, May 6, 4:15 p.m.: Erwin Lutwak, A discrete version of the Minkowski problem Monday, May 9, 4:15 p.m.: Andrei Zelevinsky, Flows in networks and the multisegment duality Wednesday, May 11, 4:15 p.m.: Alan Edelman, Hadamard matrices and the Gaussian elimination pivot conjecture Friday, May 13, 4:15 p.m.: George Markowsky, The poset of irreducibles: a basis for lattice theory Monday, May 16, 4:15 p.m.: Mike Hawrylycz, Geometric identities in invariant theory All talks will meet in room 2-338. From propp(at-sign)math.mit.edu Thu Apr 28 16:18:13 1994 To: combinatorics(at-sign)math.mit.edu Subject: Altmann, 5/4 Wednesday, May 4, 4:15 p.m.; MIT, room 2-338 Klaus Altmann (Humboldt University and M.I.T.) Minkowski sums and the versal deformation of toric singularities Starting with a lattice polytope Q, we construct a non-linear system of equations in C^N (N is the number of 1-dimensional edges of Q). The associated algebraic set M of common zeros equals a union of planes encoding the several possibilities of splitting Q into a Minkowski sum of lattice polytopes. Moreover, even if M consists of a single point only, this algebraic set may carry a richer, non-reduced ring structure. This reflects the fact that certain lattice polytopes are splittable into a non-trivial Minkowski sum of non-lattice polytopes only. On the other hand, each polytope Q defines an affine toric variety Y. We construct an algebraic family with special fiber Y by regarding the cone C(Q) of Minkowski summands of positive multiples of Q and its tautological extension. Eventually, it is the algebraic set M which arises as base space of the maximal subfamily that can be regarded as being contineous (the versal deformation of Y). From propp(at-sign)math.mit.edu Thu Apr 28 17:37:20 1994 To: combinatorics(at-sign)math.mit.edu Subject: Lutwak, 5/6 Friday, May 6, 4:15 p.m.; MIT, room 2-338 Erwin Lutwak (Brooklyn Polytechnic) A discrete version of the Minkowski problem The discrete version of Minkowski's existence theorem is concerned with the existence and uniqueness of polytopes whose faces have preassigned areas and normals. Various extensions and open problems will be presented. From nantel(at-sign)math.harvard.edu Mon May 2 08:11:27 1994 To: combinatorics(at-sign)math.mit.edu Subject: Harvard Seminar on Combinatorics Harvard Seminar on Combinatorics Nathan A. M. Lulov Rim Hook Lattices and Random Walks on the Symmetric Group Tuesday May 3 1994 4:15 pm Science Center 530 From propp(at-sign)math.mit.edu Tue May 3 18:00:47 1994 To: combinatorics(at-sign)math.mit.edu Subject: May schedule (revised again) COMBINATORICS SEMINAR Here is what I hope is the final list of talks scheduled for the month of May. Note the two new talks scheduled for May 18 and 20. * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Note that the talk by Andrei Zelevinsky originally scheduled * * for Monday, May 2 has been postponed to Monday, May 9. * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Monday, May 9, 4:15 p.m.: Andrei Zelevinsky, Flows in networks and the multisegment duality Wednesday, May 11, 4:15 p.m.: Alan Edelman, Hadamard matrices and the Gaussian elimination pivot conjecture Friday, May 13, 4:15 p.m.: George Markowsky, The poset of irreducibles: a basis for lattice theory Monday, May 16, 4:15 p.m.: Mike Hawrylycz, Geometric identities in invariant theory Wednesday, May 18, 4:15 p.m.: Laura Anderson, Combinatorial differential manifolds Friday, May 20, 4:15 p.m.: Volkmar Welker, Lattices of partitions and their relevance in the study of spaces of polynomials All talks will meet in room 2-338. From nantel(at-sign)math.harvard.edu Wed May 4 09:27:31 1994 To: combinatorics(at-sign)math.mit.edu Subject: Harvard Combinatorics Seminar Harvard Combinatorics Seminar Sergey Fomin (M.I.T.) Schubert polynomials: an introduction Tuesday, May 10, Science Center 530 4:15 PM From nantel(at-sign)math.harvard.edu Wed May 4 09:27:31 1994 To: combinatorics(at-sign)math.mit.edu Subject: Harvard Combinatorics Seminar Harvard Combinatorics Seminar Sergey Fomin (M.I.T.) Schubert polynomials: an introduction Tuesday, May 10, Science Center 530 4:15 PM From propp(at-sign)math.mit.edu Sun May 8 16:54:43 1994 To: combinatorics(at-sign)math.mit.edu Subject: Zelevinsky, 5/9 The talk originally scheduled for May 2 has been postponed to May 9. The updated information is as follows: Monday, May 9, 4:15 p.m.; MIT, room 2-338 ^^^^^ Andrei Zelevinsky (Northeastern University) Flows in networks and the multisegment duality This is a continuation of the April 11 talk, but no knowledge of the previous material will be assumed. We shall discuss an application of the theory of flows in networks and of some recent results by S. Poljak to an explicit formula for the so-called multisegment duality for the representations of quivers of type A. As time allows, more recent results on the multisegment duality will be presented, obtained by the author jointly with A. Berenstein and S. Fomin. From propp(at-sign)math.mit.edu Sun May 8 17:03:45 1994 To: combinatorics(at-sign)math.mit.edu Subject: Edelman, 4/11 Wednesday, May 11, 4:15 p.m.; MIT, room 2-338 Alan Edelman (M.I.T.) Hadamard matrices and the Gaussian elimination pivot growth conjecture Wilkinson, Cryer, and Kahan asked whether Gaussian elimination with complete pivoting can yield a growth factor bigger than n. It was long thought that Hadamard matrices might serve as examples. Non-Hadamard examples were recently found by Gould with a small correction by the speaker. Nevertheless the question remains open whether a Hadamard example can be found. We will discuss the difficulty of finding an elegant proof that a 12x12 example can not be found. We will then challenge the combinatorics community to find a general proof. (We will review the elementary numerical analysis so that no special prerequisites are assumed for this talk.) From propp(at-sign)math.mit.edu Sun May 8 17:11:28 1994 To: combinatorics(at-sign)math.mit.edu Subject: Markowsky, 4/13 Friday, May 13, 4:15 p.m.; MIT, room 2-338 George Markowsky (Maine) The poset of irreducibles: a basis for lattice theory The poset of irreducibles is a extension of Garrett Birkhoff's classic construction of finite distributive lattices from their subposets of join-irreducibles. To describe arbitrary lattices, both the join-irreducibles and meet-irreducibles must be considered. The poset of irreducibles presents a lot of information about a lattice, often in a form much more compact than the original lattice. This talk will survey the basic ideas underlying the poset of irreducibles and will describe applications of these ideas in lattice theory, combinatorics, context analysis and biology. From propp(at-sign)math.mit.edu Thu May 12 16:27:56 1994 To: combinatorics(at-sign)math.mit.edu Subject: typo Markowsky's talk will of course be on 5/13, not 4/13. From propp(at-sign)math.mit.edu Thu May 12 21:13:37 1994 To: combinatorics(at-sign)math.mit.edu Subject: Hawrylycz, 5/16 Monday, May 16, 4:15 p.m.; MIT, room 2-338 Mike Hawrylycz (Los Alamos) Geometric identities in invariant theory The Grassmann-Cayley (GC) algebra has proven to be a useful setting for proving and verifying geometric propositions in projective space. A GC algebra is essentially the exterior algebra of a vector space, endowed with the natural dual to the wedge product, an operation which is called the meet. A geometric identity in a GC algebra is an identity between expressions $P({\cal A},\vee,\wedge)$ and $Q({\cal B},\vee,\wedge)$ where ${\cal A}$ and ${\cal B}$ are sets of anti-symmetric tensors, and $P$ and $Q$ contain no summations. The idea of a geometric identity is due to Barnabei, Brini and Rota. We show how the classic theorems of projective geometry such as the theorems of Desargues, Pappus, Mobius, as well as well as several higher dimensional analogs, can be realized as identities in this algebra. By exploiting properties of bipartite matchings in graphs, a class of expressions, called Desarguean Polynonials, is shown to yield a set of dimension independent identities in a GC algebra, representing the higher Arguesian laws, and a variety of theorems of arbitrary complexity in projective space. The class of Desarguean polynomials is also shown to be sufficiently rich to yield representations of the general projective conic and cubic. From nantel(at-sign)math.harvard.edu Mon May 16 11:12:37 1994 To: combinatorics(at-sign)math.mit.edu Subject: Harvard Combinatorics Seminar 5/17 David Grabiner, Harvard University will speak on "A combinatorial Correspondence for Random Walks in Weyl Chambers" The talk will be in Science Center 530 at 4:15 PM. From propp(at-sign)math.mit.edu Thu May 19 16:55:01 1994 To: combinatorics(at-sign)math.mit.edu Subject: Anderson, 5/18 Apologies to all for my failure to post this. (I'm sending it out now so that those who missed the talk can at least read the abstract.) Wednesday, May 18, 4:15 p.m.; MIT, room 2-338 Laura Anderson (M.I.T.) Combinatorial Differential Manifolds Combinatorial differential manifolds (CD manifolds) were introduced by Gelfand and MacPherson as a combinatorial analog to differential manifolds. Their application led to a combinatorial formula for the Pontrjagin classes of a smooth manifold, and they show promise for a number of applications in geometry and topology. Essentially, a CD manifold is a simplicial complex together with a collection of oriented matroids which play the role of tangent spaces. An open problem in the very new theory of CD manifolds is whether all CD manifolds are topological manifolds. This can be made into a purely combinatorial problem on the geometry of oriented matroids. We will discuss progress on the two equivalent questions: 1. Is every CD manifold a PL manifold? 2. If M is an oriented matroid, is every triangulation of M a PL sphere? From propp(at-sign)math.mit.edu Thu May 19 17:40:57 1994 To: combinatorics(at-sign)math.mit.edu Subject: Welker, 5/20 Friday, May 20, 4:15 p.m.; MIT, room 2-338 Volkmar Welker (Essen) Lattices of partitions and their relevance in the study of spaces of polynomials We describe some classes of sub-posets of the lattice of set partitions and outline the relevance of their combinatorial and homological properties in the study of spaces of polynomials and polynomial systems which are described by imposing certain conditions on their (common) roots --- the complement of the descriminant being the well studied and well known case. The connection is provided by the theory of arrangements of linear subspaces in complex n-space. We will show how to use combinatorial methods and representation theoretic methods to provide a uniform approach to some problems arising in the study of these spaces. Generalizations of results of Orlik and Solomon for the case of hyperplane-arrangements will be provided.