The Simplex, the Cyclic polytope, the Positroidron, the Amplituhedron, and Beyond

ampn

A quick schematic road-map to these new geometric objects. The  positroidron can be seen as a cellular structure on the nonnegative Grassmanian – the part of the real Grassmanian G(m,n) which corresponds to m by n matrices with all m by m minors non-negative. The cells in the cellular structure of the positroidron correspond to those matrices with the same (+,0) pattern for m by m minors. When m=1 we get a (spherical) simplex. When we project the positroidron using an n by k totally positive matrix we get for m=1 the cyclic polytope, and for general m the  amplituhedron. When we project using general matrices we obtain general polytopes for m=1, and an interesting extension of polytopes proposed by Thomas Lam for general m.   

Alex Postnikov’s recent lectures series in our Midrasha was an opportunity to understand slightly better some remarkable combinatorial objects that drew much attention recently. Continue reading

From Oberwolfach: The Topological Tverberg Conjecture is False

The topological Tverberg conjecture (discussed in this post), a holy grail of topological combinatorics, was refuted! The three-page paper “Counterexamples to the topological Tverberg conjecture” by Florian Frick gives a brilliant proof that the conjecture is false.

The proof is based on two major ingredients. The first is a recent major theory by Issak Mabillard and Uli Wagner which extends fundamental theorems from classical obstruction theory for embeddability to an obstruction theory for r-fold intersection of disjoint faces in maps from simplicial complexes to Euclidean spaces. An extended abstract of this work is Eliminating Tverberg points, I. An analogue of the Whitney trick. The second is a result  by Murad Özaydin’s from his 1987 paper Equivariant maps for the symmetric group, which showed that for the non prime-power case the topological obstruction vanishes.

It was commonly believed that the topological Tverberg conjecture is correct. However, one of the motivations of Mabillard and Wagner for studying elimination of higher order intersection was that this may lead to counterexamples via Özaydin result. Isaak and Uli came close but there was a crucial assumption of large codimension in their theory, which seemed to avoid applying the new theory to this case.  It turned out that a simple combinatorial argument allows to overcome the codimension problem!

Florian’s  combinatorial argument which allows to use Özaydin’s result in Mabillard-Wagner’s theory  is a beautiful example of a powerful combinatorial method with other applications by Pavle Blagojević, Florian Frick and Günter Ziegler.

ow

Both Uli and Florian talked about it here at Oberwolfach on Tuesday. I hope to share some more news items from Oberwolfach and from last week’s Midrasha in future posts.

Midrasha Mathematicae #18: In And Around Combinatorics

 

tahl2-mid

Tahl Nowik

photo (4) 17.8.14 midrasha poster 2015 poster

michal-mid mid-irit mid-david nati-mid mid-peter nica-mid   alex-mid2 midjoel mid-sam tami-mid zohar-mid tahl-mid

Update 3 (January 30): The midrasha ended today. Update 2 (January 28): additional videos are linked; Update 1 (January 23): Today we end the first week of the school. David Streurer and Peter Keevash completed their series of lectures and Alex Postnikov started his series.

___

Today is the third day of our winter school. In this page I will gradually give links to to various lectures and background materials. I am going to update the page through the two weeks of the Midrasha. Here is the web page of the midrasha, and here is the program. I will also present the posters for those who want me to: simply take a picture (or more than one) of the poster and send me. And also – links to additional materials, pictures, or anything else: just email me, or add a comment to this post.

Lecture series and lectures

Irit Dinur: Direct products of games and graphs

mid-irit Continue reading

When Do a Few Colors Suffice?

When can we properly color the vertices of a graph with a few colors? This is a notoriously difficult problem. Things get a little better if we consider simultaneously a graph together with all its induced subgraphs. Recall that an induced subgraph of a graph G is a subgraph formed by a subset of the vertices of G together with all edges of G spanned  on these vertices.  An induced cycle of length larger than three is called a hole, and an induced subgraph which is a complement of a cycle of length larger than 3 is called an anti-hole. As usual, \chi (G) is the chromatic number of G and \omega (G) is the clique number of G (the maximum number of vertices that form a complete subgraph. Clearly, for every graph G

\chi(G) \ge \omega (G).

Perfect graphs

Question 1: Describe the class \cal G  of graphs closed under induced subgraphs, with the property that \chi(G)=\omega (G) for every G\in{\cal G}.

A graph G is called perfect if  \chi(H)=\omega (H) for every induced subgraph H of G. So Question 1 asks for a description of perfect graphs. The study of perfect graphs is among the most important areas of graph theory, and much progress was made along the years.

Interval graphs, chordal graphs, comparability graphs of POSETS  , … are perfect.

Two major theorems about perfect graphs, both conjectured by Claude Berge are:

The perfect graph theorem (Lovasz, 1972): The complement of a perfect graph is perfect

The strong perfect graph theorem (Chudnovsky, Robertson, Seymour and Thomas, 2002): A graph is perfect if and only if it does not contain  an odd hole and an odd anti-hole.

Mycielski Graphs

There are triangle-free graphs with arbitrary large chromatic numbers. An important construction by Mycielski goes as follows: Given a triangle graph G with n vertices v_1,v_2, \dots, v_n create a new graph  G’ as follows: add n new vertices u_1, u_2\dots u_n and a vertex w. Now add w to each u_i and for every i and j for which v_i and v_j are adjacent add also an edge between v_i and u_j (and thus also between u_i and v_j.)

Classes of Graphs with bounded chromatic numbers

Question 2: Describe classes of graphs closed under induced subgraphs with bounded chromatic numbers.

Here are three theorems in this direction. The first answers affirmatively a conjecture by Kalai and Meshulam. The second and third prove conjectures by Gyarfas.

Trinity Graphs

The Trinity graph theorem (Bonamy, Charbit and Thomasse, 2013): Graphs without induced cycles of  length divisible by three have bounded chromatic numbers.

(The paper: Graphs with large chromatic number induce 3k-cycles.)

trinity-youtique-logo

Steps toward Gyarfas conjecture

Theorem (Scott and Seymour, 2014):  Triangle-free graphs without odd induced cycles have bounded chromatic number.

(The paper:  Coloring graphs with no odd holes.)

Continue reading

Coloring Simple Polytopes and Triangulations

Coloring

Edge-coloring of simple polytopes

One of the equivalent formulation of the four-color theorem asserts that:

Theorem (4CT) : Every cubic bridgeless planar graph is 3-edge colorable

So we can color the edges by three colors such that every two edges sharing a vertex are colored by different colors.

Abby Thompson asked the following question:

Question: Suppose that G is the graph of a simple d-polytope with n vertices. Suppose also that n is even (this is automatic if d is odd). Can we always properly color the edges of G with d colors?

Vising theorem reminded

Vising’s theorem asserts that a graph with maximum degree D can be edge-colored by D+1 colors. This is one of the most fundamental theorems in graph theory. (One of my ambitions for the blog is to interactively teach the proof based on a guided way toward a proof, based on Diestel’s book, that I tried in a graph theory course some years ago.) Class-one graphs are those graphs with edge chromatic number equal to the maximum degree. Those graphs that required one more color are called class-two graphs.

Moving to triangulations

Thompson asked also a more general question:

Question: Let G be a dual graph of a triangulation of the (d-1)-dimensional sphere. Suppose that G has an even number of vertices.  Is G d-edge colorable?

Grunbaum’s question and counterexample

Branko Grunbaum proposed a beautiful generalization for the 4CT: He conjectured that the dual graph of a triangulation of every two-dimensional manifold is 3-edge colorable. This conjecture was refuted in 2009 by Martin Kochol.

Triangulations in higher dimensions

A third question, even more general, posed by Thompson is: Let G be a dual graph of a triangulation of a (d-1)-dimensional manifold, d ≥ 4. Suppose that G has an even number of vertices.  Is G d-edge colorable?

Hamiltonian cycles

Coloring graph is notoriously difficult but finding a Hamiltonian cycle is even more difficult.

Tait’s conjecture and Barnette’s conjectures

Peter Tait conjectured in 1884 that every 3-connected cubic planar graph is Hamiltonian. His conjecture was disproved by William Tutte in 1946. A cubic Hamiltonian graph must be of class I and therefore Tait’s conjecture implies the 4CT. David Barnette proposed two ways to save Tait’s conjecture: one for adding the condition that all faces have an even number of edges or, equivalently that the graph is bipartite, and another, by moving up in the dimension.

Barnette’s conjecture I: Planar 3-connected cubic bipartite graphs are Hamiltonian.

Barnette’s conjecture II: Graphs of simple d-polytopes d ≥ 4 are Hamiltonian.

Barnette’s hamiltonicity conjecture in high dimension does not imply a positive answer to Thompson’s quaestion. We can still ask for the following common strengthening:  does the graph of a simple d-polytope, d 4, with an even number of vertices contain [d/2] edge-disjoint Hamiltonian cycles?

There are few more things to mention: Peter Tait made also three beautiful conjectures about knots. They were all proved, but it took a century more or less. When we move to high dimensions there are other notions of coloring and other generalizations of “Hamiltonian cycles.” You can Test Your Imagination and try to think about such notions!

Update (Dec 7): Following rupeixu’s comment I asked a question over: generalizations-of-the-four-color-theorem.

A lecture by Noga

nogauriirit

Noga with Uri Feige among various other heroes

A few weeks ago I devoted a post to the 240-summit conference for Péter Frankl, Zoltán Füredi, Ervin Győri and János Pach, and today I will bring you the slides of Noga Alon’s lecture in the meeting. Noga is my genious twin academic brother – we both were graduate students under the supervision of Micha A. Perles in the same years and we both went to MIT as postocs in fall 1983.  The lecture starts with briefly mentioning four results by the birthday boys related to combinatorics and geometry and continues with recent startling results by Alon, Ankur Moitra, and Benny Sudakov. One out of many contributions of Noga over the years is building a large infrastructure of constructions and examples, often very surprising,  in combinatorics, graph theory, information theory,TOC, and related areas. And the new results add to this infrastructure. The slides are very clear. Enjoy!

noga240-1noga240-2240z240e240j240l

 

 

 

 

Jim Geelen, Bert Gerards, and Geoff Whittle Solved Rota’s Conjecture on Matroids

gcrota

Gian Carlo Rota

Rota’s conjecture

I just saw in the Notices of the AMS a paper by Geelen, Gerards, and Whittle where they announce and give a high level description of their recent proof of Rota’s conjecture. The 1970 conjecture asserts that for every finite field, the class of matroids representable over the field can be described by a finite list of forbidden minors. This was proved by William Tutte in 1938 for binary matroids (namely those representable over the field of two elements). For binary matroids Tutte found a single forbidden minor.  The ternary case was settled by by Bixby and by Seymour in the late 70s (four forbidden minors).  Geelen, Gerards and Kapoor proved recently that there are seven forbidden minors over a field of four elements.  The notices paper gives an excellent self-contained introduction to the conjecture.

This is a project that started in 1999 and it will probably take a couple more years to complete writing the proof. It relies on ideas from the Robertson-Seymour forbidden minor theorem for graphs. Congratulations to Jim, Bert, and Geoff!

Well, looking around I saw that this was announced in August 22’s post in a very nice group blog devoted by matroids- Matroid Union, with contributions by Dillon Mayhew, Stefan van Zwam, Peter Nelson, and Irene Pivotto. August 22? you may ask, yes! August 22, 2013. I missed the news by almost a year. It was reported also here and here  and here, and here, and here, and here!

This is a good opportunity to mention two additional conjectures by Gian-Carlo Rota. But let me ask you, dear readers, before that a little question.

Rota’s unimodality conjecture and June Huh’s work

Rota’s unimodality conjecture predicts that the coefficients of the characteristic polynomial of a matroid form a log-concave sequence. This implies that the coefficients are unimodal. A special case of the conjecture is an earlier famous conjecture (by Read) asserting that the coefficients of the chromatic polynomial of a graph are unimodal (and log-concave). This conjecture about matroids was made also around the same time by Heron and Welsh.

June Huh proved Reads’ unimodality conjecture for graphs and the more general Heron-Rota-Welsh conjecture for representable matroids for characteristic 0. Later Huh and  Eric Katz proved the case of  representable matroids for arbitrary characteristics. I already mentioned these startling results earlier and we may come back to them later.

Huh’s path to mathematics was quite amazing. He wanted to be a science-writer and accomponied Hironaka on whom he planned to write. Hironaka introduced him to mathematics in general and to algebraic geometry and this led June to study mathematics and a few years later to use deep connections between algebraic geometry and combinatorics to prove the conjecture.

Rota’s basis conjecture

Rota’s basis conjecture from the late 80’s appears to remain wide open. The problem first appeared in print in a paper by Rosa Huang and Rota. Here is a post about it also from “the matroid union.” It is the first problem in Rota’s article entitled “Ten Mathematics problems I will never solve“. Having access only to page one of the paper I can only guess what the other nine problems might be.

rota-fan

Rota’s portrait by Fan Chung Graham

 

 

Next Week in Jerusalem: Special Day on Quantum PCP, Quantum Codes, Simplicial Complexes and Locally Testable Codes

Special Quantum PCP and/or Quantum Codes: Simplicial Complexes and Locally Testable CodesDay

24 Jul 2014 – 09:30 to 17:00

room B-220, 2nd floor, Rothberg B Building

On Thursday, the 24th of July we will host a SC-LTC (simplicial complexes and classical and quantum locally testable codes) at the Hebrew university, Rothberg building B room 202 (second floor) in the Givat Ram campus. Please join us, we are hoping for a fruitful and enjoyable day, with lots of interactions. Coffee and refreshments will be provided throughout the day, as well as free “tickets” for lunch on campus
There is no registration fee, but please email dorit.aharonov@gmail.com preferably by next Tuesday if there is a reasonable probability that you attend –  so that we have some estimation regarding the number of people, for food planning

Program:SC-LTC day – simplicial complexes and locally testable classical and quantum codes -Rothberg building B202
9:00 gathering: coffee and refreshments

9:30 Irit Dinur: Locally testable codes, a bird’s eye view

10:15: coffee break

10:45 Tali Kaufman, High dimensional expanders and property testing

11:30 15 minutes break

11:45 Dorit Aharonov, quantum codes and local testability

12:30 lunch break

2:00 Alex Lubotzky: Ramanujan complexes

2:50 coffee break

3:15 Lior Eldar: Open questions about quantum locally testable codes and quantum entanglement

3:45 Guy Kindler: direct sum testing and relations to simplicial complexes ( Based on David, Dinur, Goldenberg, Kindler, and Shinkar, 2014)

4:15-5 free discussion, fruit and coffee

 

My Mathematical Dialogue with Jürgen Eckhoff

Jürgen Eckhoff, Ascona 1999

Jürgen Eckhoff is a German mathematician working in the areas of convexity and combinatorics. Our mathematical paths have met a remarkable number of times. We also met quite a few times in person since our first meeting in Oberwolfach in 1982. Here is a description of my mathematical dialogue with Jürgen Eckhoff:

Summary 1) (1980) we found independently two proofs for the same conjecture; 2) (1982) I solved Eckhoff’s Conjecture; 3) Jurgen (1988) solved my conjecture; 4) We made the same conjecture (around 1990) that Andy Frohmader solved in 2007,  and finally  5) (Around 2007) We both found (I with Roy Meshulam, and Jürgen with Klaus Peter Nischke) extensions to Amenta’s Helly type theorems that both imply a topological version.

(A 2009 KTH lecture based on this post or vice versa is announced here.)

Let me start from the end: 

5. 2007 – Eckhoff and I  both find related extensions to Amenta’s theorem.

Nina Amenta

Nina Amenta proved a remarkable extension of Helly’s theorem. Let \cal F be a finite family with the following property:

(a) Every member of \cal F is the union of at most r pairwise disjoint compact convex sets.

(b) So is every intersection of members of \cal F.

(c) |{\cal F}| > r(d+1).

If every r(d+1) members of \cal F has a point in common, then all members of \cal F have a point in common!

The case r=1 is Helly’s theorem, Grünbaum and Motzkin proposed this theorem as a conjecture and proved the case r=2. David Larman  proved the case r=3.

roy

Roy Meshulam

Roy Meshulam and I studied a topological version of the theorem, namely you assume that every member of F is the union of at most r pairwise disjoint contractible compact sets in $R^d$ and that all these sets together form a good cover – every nonempty intersection is either empty or contractible. And we were able to prove it!

Eckhoff and Klaus Peter Nischke looked for a purely combinatorial version of Amenta’s theorem which is given by the old proofs (for r=2,3) but not by Amenta’s proof. An approach towards such a proof was already proposed by Morris in 1968, but it was not clear how to complete Morris’s work. Eckhoff and Nischke were able to do it! And this also implied the topological version for good covers.

The full results of Eckhoff and Nischke and of Roy and me are independent. Roy and I showed that if the nerve of \cal G is d-Leray then the nerve of \cal F is ((d+1)r-1)-Leray. Eckhoff and showed that if the nerve of \cal G has Helly number d, then the nerve of \cal F has Helly number (d+1)r-1. Amenta’s argument can be used to show that if the nerve of \cal G is d-collapsible then the nerve of F is  ((d+1)r-1)-collapsible.

Here, a simplicial comples K is d-Leray if all homology groups H_i(L) vanishes for every i \ge d and every induced subcomplex L of K.

Roy and I were thinking about a common homological generalization which will include both results but so far could not prove it.

 

And now let me move to the beginning:

1. 1981 – we give different proofs for the Perles-Katchalski Conjecture

Continue reading

Happy Birthday Richard Stanley!

Richard_Stanley

This week we are celebrating in Cambridge MA , and elsewhere in the world, Richard Stanley’s birthday.  For the last forty years, Richard has been one of the very few leading mathematicians in the area of combinatorics, and he found deep, profound, and fruitful links between combinatorics and other areas of mathematics.  His works enriched and
influenced combinatorics as well as other areas of mathematics, and, in my opinion,
combinatorics matured greatly as a mathematical discipline thanks to his work.

Trivia Quiz

Correct or incorrect?

(1) Richard drove cross-country at least 8 times

(2) In his youth, at a wild party, Richard Stanley found  a proof of FLT consisting of a few mathematical symbols.

(3) Richard  jumped at least once from an airplane

(4) Richard is actively interested in the study of consciousness

(5) Richard found a mathematical way to divide by zero

 

Seven Early Papers by Richard Stanley That You Must Read.

cobcom

Richard’s Green book: Combinatorics and Commutative Algebra

Combinatorics and Commutative Algebra

(1) R. P. Stanley, The upper bound conjecture and Cohen-Macaulay rings.
Studies in Appl. Math. 54 (1975), no. 2, 135–142.

The two seminal papers (1) and (3) (below) showed remarkable and unexpected applications of commutative algebra to combinatorics. In each of these papers a central
conjecture in combinatorics was solved in a completely unexpected way which was the basis for a later remarkable theory. Paper (1) is the starting point for the interrelation between commutative algebra and combinatorics of simplicial complexes and their
topology. In this work Richard Stanley proved the Motzkin-Klee upper bound conjecture for triangulations of spheres. This conjecture asserts that the maximum number
of k-faces for a triangulation of a (d-1)-dimensional sphere with n vertices is attained by the boundary complex of the cyclic d-dimensional polytope with
n vertices. Peter McMullen proved this conjecture for simplicial polytopes and Richard Stanley proved it for arbitrary triangulations of spheres. The key point was that a certain ring (the Stanley-Reisner ring) associated with a simplicial polytope has the Cohen-Macaulay property.

The connection between combinatorics and commutative algebra is
far reaching, and in subsequent works combinatorial problems led to
developments in commutative algebra and techniques from the two areas were
combined.  A more recent important paper by Richard on applications of commutative algebra for the study of face numbers is: R. P. Stanley, Subdivisions and local h-vectors. J. Amer. Math. Soc. 5 (1992), no. 4, 805–851.

And here is, a few weeks old important development in this theory: Relative Stanley-Reisner theory and Upper Bound Theorems for Minkowski sums, by Karim A. Adiprasito and Raman Sanyal.

The Cohen-Macaulay property, magic squares and lattice points in polytopes

(2) R. P. Stanley, Magic labelings of graphs, symmetric magic squares,
systems of parameters, and Cohen-Macaulay rings. Duke Math. J. 43 (1976),
no. 3, 511–531.

This paper starts with a theorem about enumeration of certain magic squares. Solving a long-standing open problem, Stanley proved that the generating function for the
number of k by k integer matrices (k- fixed) with nonnegative entries and row sums and column sums equal to nis rational. This is the starting
point of a deep algebraic theory of integral points in polyhedra.

Enters the Hard-Lefshetz Theorem: McMullen’s g-conjecture

(3) R. P. Stanley, The number of faces of a simplicial convex polytope. Adv. in Math. 35 (1980), no. 3, 236–238.

The g-conjecture proposes a complete characterization of face numbers of d-dimensional polytopes. One linear equality that holds among face numbers is, of course, the Euler-Poincaré relation. This relation implies additional [d/2] equalities called the Dehn-Sommerville relations. Peter McMullen proposed an additional system of linear and nonlinear inequalities as a complete characterization of face numbers of polytopes. The sufficiency part of this conjecture was proved by Billera and Lee. Richard Stanley’s brilliant proof for McMullen’s inequalities that established the g-conjecture was based on the Hard Lefschetz Theorem from algebraic topology. Starting from a simplicial polytope P (with rational vertices) we associate to it a toric variety T(P). It turned out that the cohomology ring of this variety is closely related to the Stanley-Reisner ring mentioned above. The Hard Lefschetz Theorem implies an algebraic property of the Stanley-Reisner ring from which McMullen inequalities can be deduced by direct combinatorial reasoning. Richard found a number of other combinatorial applications of the Hard Lefschetz theorem (including the solution of the Erdos-Moser conjecture).

Here is the abstract of Lou Billera’s lecture

LOUIS BILLERA (CORNELL)

Even more intriguing, if rather less plausible…

The title is how Peter McMullen described his own conjectured characterization of the f-vectors of simplicial polytopes in his 1971 lecture notes on the upper bound conjecture written with Geoffrey Shephard. Yet by the end of that decade, the so-called g-conjecture would become the g-theorem, and algebraic combinatorics (as practiced at MIT) would have attracted the attention of mainstream mathematics, almost entirely due to the startling proof given by Richard Stanley.

I will briefly describe some of the events leading to this proof and some of its still developing consequences.

Enumeration

Enumeration is Richard’s true mathematical love.

 

ec1

Richard’s monumental books EC1 and EC2 (The picture is of EC1 and a young fan)

(4) A baker’s dozen of conjectures concerning plane partitions, in Combinatoire Énumérative (G. Labelle and P. Leroux, eds.), Lecture Notes in Math., no. 1234, Springer-Verlag, Berlin/Heidelberg/New York, 1986, pp. 285-293.

13 beautiful conjectures on counting plane partitions with various forms of symmetry.

(5) Generating functions, in Studies in Combinatorics (G.-C. Rota, ed.), Mathematical Association of America, 1978, pp 100-141.

For me this was the best introduction to generating functions, clear and inspiring. The entire MAA 1978 Rota’s blue little volume on combinatorics is great. Buy it!

Posets everywhere

(5) Supersolvable latticesAlgebra Universalis 2 (1972), 197-217.

This paper provides a profound link between group theory and the study of
partially ordered sets. It can be seen as a starting point of Stanley’s own work on the Cohen-Macaulay property and it had much influence on later works on combinatorial properties of lattices of subgroups by Quillen and many others, and also on the study of POSETS (=partially ordered sets) arising from arrangements of hyperplanes. The algebraic notion of supersolvable groups is translated to an important combinatorial notion for partially ordered sets. (There is a more detailed paper which I could not find online: R. P. Stanley, Supersolvable semimodular lattices. Mobius algebras (Proc. Conf., Univ. Waterloo, Waterloo, Ont., 1971), pp. 80–142. Univ. Waterloo, Waterloo, Ont., 1971.)

 Combinatorics and representation theory

(6) On the number of reduced decompositions of elements of Coxeter groupsEuropean J. Combinatorics 5 (1984), 359-372.

This paper gives an important result proved using representation theory. It is one of
many results by Stanley on connections between enumerative combinatorics,
representation theory, and invariant theory. Again, this paper represents an exciting area of research about the connection of enumerative combinatorics and representation theory that I am less familiar with.  A very inspiring survey paper is: Invariants of finite groups and their applications to combinatoricsBull. Amer. Math. Soc. (new series) 1 (1979), 475-511.

Here are abstracts of two lectures from the meeting on some recent developments in combinatorial representation theory and symmetric functions.

 

GRETA PANOVA (UCLA)

The Kronecker coefficients: an unexpected journey

Kronecker coefficients live at the intersection of representation theory, algebraic combinatorics and, most recently, complexity theory. They count the multiplicities of irreducible representations in the tensor product of two other irreducible representations of the symmetric group. While their journey started 75 years ago, they still haven’t found their explicit positive combinatorial formula, and present a major open problem in algebraic combinatorics. Recently, they were given a new role in the field of Geometric Complexity Theory, initiated by Mulmuley and Sohoni, where certain conjectures on the complexity of computing and deciding positivity of Kronecker coefficients are part of a program to prove the “”P vs NP”” problem.

We will take the Kronecker coefficients to asymptotics land and bound them. As an unexpected consequence of this trip, we find bounds for the difference of consecutive coefficients in the q-binomial coefficients (as polynomial in q), generalizing Sylvester’s unimodality theorem and connecting with results of Richard Stanley.
Joint work with Igor Pak.

THOMAS LAM (U MICHIGAN)

Truncations of Stanley symmetric functions and amplituhedron cells

Stanley symmetric functions were invented (by Stanley) with applications to the enumeration of reduced words in the symmetric group in mind. Recently, the “amplituhedron” was introduced in the study of scattering amplitudes in N=4 super Yang Mills. I will talk about a formula for the cohomology class of a (tree) amplituhedron variety as the truncation of an affine Stanley symmetric function.

Two combinatorial applications of the Aleksandrov-Fenchel inequalities;

(7)  Two combinatorial applications of the Aleksandrov-Fenchel inequalitiesJ. Combinatorial Theory (A) 31 (1981), 56-65.

In this amazing paper Stanley used inequalities of classical convexity
to settle an important conjecture on probability of events in partially
ordered sets. A special case of the conjecture was settled earlier by Ron
Graham using the FKG inequality. The profound relation between classical
convexity inequalities, combinatorial structures, polytopes, and
probability theory was further studied by many authors including Stanley
himself and there is much more to be done.

I see that I ran out of my seven designated slots. Certainly you should read Richard’s combinatorial constructions of polytopes, like Two poset polytopesDiscrete Comput. Geom. 1 (1986), 9-23, and his papers on arrangements. Let me mention a more recent paper of Stanley in this general area:   A polytope related to empirical distributions, plane trees, parking functions, and the associahedron (with J. Pitman)Discrete Comput. Geom.27 (2002), 603-634.

More

(Mostly from RS’s homepage.)

Chess and Mathematics

(12 page  PDF file) An excerpt (version of 1 November 1999) from a book Richard is writing with Noam Elkies.

An unusual method for proving the Riemann hypothesis.

Professor Eubanks in Zetaland

Richard Stanley’s Mathoverflow question on MAGIC

Magic trick based on deep mathematics

 

Richard the Catalan

(From RS’s homepage)

Excerpt (27 page PDF file) from EC2  on problems related to Catalan numbers (including 66 combinatorial interpretations of these numbers).

Solutions to Catalan number problems from the previous link (23 page PDF file).

Catalan addendum (Postscript or PDF) (version of 25 May 2013; 96 pages). An addendum of new problems (and solutions) related to Catalan numbers. Current number of combinatorial interpretations of Cn207.

The material on Catalan numbers is being collected into a monograph, to be published by Cambridge University Press in late 2014 or early 2015.

 

bgs