Combinatorial results without known combinatorial proofs - MathOverflow

Combinatorial results without known combinatorial proofs

2009-11-13T22:42:44Z

Stanley likes to keep a list of combinatorial results for which there is no known combinatorial proof. For example, until recently I believe the explicit enumeration of the de Brujin sequences fell into this category (but now see arXiv:0910.3442v1). Many unimodality results also fall into this category. Do you know of any other results of this kind, especially results that look frustratingly like they ought to have simple combinatorial proofs?

For the purposes of this question, "combinatorial result" should be interpreted as meaning some kind of exact enumeration, and "combinatorial proof" should be interpreted as meaning, more or less, "bijective proof." (So for example I am not interested in bounds on Ramsey numbers.)

Answer by Qiaochu Yuan for Combinatorial results without known combinatorial proofs

2009-11-13T22:44:11Z

For example, according to Stanley the identity $n \cdot \text{pp}(n) = \sum_{i=1}^{n} \sigma_2(i) \text{pp}(n-i)$ has no known bijective proof, where $\text{pp}(n)$ denotes the number of plane partitions of $n$.

Answer by Tom Leinster for Combinatorial results without known combinatorial proofs

2009-11-14T00:17:25Z

This isn't exactly an answer, but since this is community wiki I hope it's in the spirit of things if I add a twist to the question.

One of the excellent things about the excellent theory of species is that it has at its heart a notion of natural bijective proof. Let me sketch the basic idea. A species is simply a functor from the category $$ \mathcal{B} = (\mbox{finite sets } + \mbox{ bijections}) $$ to the category of sets. One thinks of a species as a way of decorating a finite set with some extra combinatorial structure. For example, there is a species $L$ defined by $$ L(X) = \{ \mbox{linear orders on } X\} $$ for finite sets $X$ (and defined in the obvious way on morphisms). Thus $L(X)$ is the set of ways of "decorating" $X$ with a linear order. Or, there is another species $P$ defined by $$ P(X) = \{ \mbox{permutations on }X\} $$ for finite sets $X$ (and defined in the obvious way on morphisms).

You can think of species as categorified generating functions. More exactly, for any species $S$ that is finite (takes values in finite sets), you can form its exponential generating function $\sum_n s_n x^n/n!$, where $s_n$ is the cardinality of $S(X)$ for any $n$-element set $X$. By passing from a species to its generating function (decategorification), you lose some information. I'll give a non-trivial example of this in a moment.

There's an obvious notion of isomorphism of species, namely, natural isomorphism of functors. Are the species $L$ and $P$ above isomorphic? We have $L(X) \cong P(X)$ for all $X$, since an $n$-element set admits both $n!$ linear orders and $n!$ permutations. But you can show that there is no natural isomorphism $L \cong P$. So no, $L$ and $P$ are not isomorphic. The intuition is this: in order to match up permutations and orders, you'd have to choose an order to correspond to the identity permutation; but an abstract finite set carries no canonical linear order, so you'd have to make a random choice. Hence there's no canonical correspondence between them.

In particular, this implies that species with the same generating function ($\sum_n n! x^n/n! = 1/(1-x)$, here) need not be isomorphic. So yes, passing to the generating function can lose information.

Moral: one notion of "bijective proof" is "existence of an isomorphism of species". It's quite a demanding notion, as the permutation/order example shows. One might consider compiling a list of all the pairs of species that have the same generating function but are not isomorphic. This list could usefully be compared to Stanley's list.

Answer by Greg Kuperberg for Combinatorial results without known combinatorial proofs

2009-11-14T06:37:28Z

This is a very common theme in enumerative combinatorics. You can find a lot of examples with the Google search "no bijective proof" (with quotes).

First, I can say something about why you might care about bijective proofs. Combinatorial species are certainly a nice theory, but they are a fairly specific and elaborate answer related to generating functions. A more general reason is that a bijective proof categorifies an equality in combinatorics to the category of sets. In other words, it promotes an equality $|A| = |B|$ to an isomorphism $A \cong B$. In my opinion, it is just as important to find any other categorification, for instance to the category of vector spaces. Instead of showing that two sets are the same size with a bijection, you would show that they are the same size using an invertible matrix.

Second, of the many examples, I can name one that I encountered. This example is interesting because the objects in question seem very similar. Recall that an alternating sign matrix is a matrix whose non-zero entries in each row and column alternate between $1$ and $-1$, and such that the first and last non-zero entry in each row and column is $1$. One interesting subclass is the ASMs of order $2n+1$ which are symmetric about a vertical line. Another interesting subclass is the ASMs of order $2n$ which are diagonally symmetric and have 0s on the diagonal. (ASMs of either type of the opposite parity do not exist.) The first class was discovered by David Robbins and I found the second class. I proved David's product formula for the first class and I established the same product formula for the second class. So these two classes of ASMs are equinumerous, but no bijective proof is known.

Here is another interesting example in the same vein. A cyclically symmetric, self-complementary plane partition (CSSCPP) is equivalent to a tiling of a regular hexagon of order $2n$ by unit lozenges, which is invariant under 60 degree rotation. Here a unit lozenge is two unit equilateral triangles stuck together. A totally symmetric, self-complementary plane partition (TSSCPP) is the same thing except with full dihedral symmetry. (I make the size even because otherwise there aren't any plane partitions with the imposed symmetry.) The formulas for both classes were also conjectured by David Robbins; George Andrews proved his conjecture for TSSCPPs and I proved the conjecture for CSSCPPs. In particular, the number CSSCPPs of a fixed size is the square of the number of TSSCPPs, but no one knows a good bijection.

The single most striking thing that David Robbins found was that the number of TSSCPPs, which are plane partitions with full symmetry, equals the number of ASMs with no imposed symmetry. No bijective proof of that is known either. On the positive side, Doron Zeilberger's proof of the ASM conjecture, and his later paper on refined ASMs, could be steps towards one because they equate certain generalizations and refined enumerations. However, alternating-sign matrices look totally different from plane partitions. In my opinion, the most frustrating case is when we can't even match like to like.

Answer by Alon Amit for Combinatorial results without known combinatorial proofs

2009-11-14T07:28:03Z

Warning: this used to be a great example, but I'm afraid it no longer is.

Let $H(n)$ be the number of horizontally-convex polyominoes in the plane, where "horizontally convex" means just what you think it means, and equivalence is just up to translations (so mirror images and rotations are considered distinct). Using a sequence of manipulations with two-variable generating functions and an amazing amount of cancellation, one finds that

$H(n) = 5H(n-1) - 7H(n-2) + 4H(n-3)$.

I learned this from Gil Kalai in 1991 (and the result is much older), and I'm quite sure there was no known combinatorial proof of this surprising result for a while. However fairly recently Dean Hickerson found one. I'm sure Dean thought that this looks frustratingly like something that ought to have a combinatorial proof, and then he proceeded to resolve this frustration in the only possible way.

Answer by Gordon Royle for Combinatorial results without known combinatorial proofs

2009-11-14T13:47:36Z

The number of (isomorphism classes of) self complementary graphs on n vertices is the difference between the number of graphs on n vertices with an odd number of edges and the number with an even number of edges.

This is relatively easy to prove with counting arguments, but I'd love to have a combinatorial proof of this...

Answer by Vladimir Dotsenko for Combinatorial results without known combinatorial proofs

2009-11-14T14:54:20Z

The following statement seems to not have clear combinatorial proof (or at least it did not in 2003, when I heard of it):

Denote by L(n) the set of all partitions of n into distinct parts with the smallest part being odd. Let L_o(n), L_e(n) be the subsets of L(n) consisting of partitions into odd and even number of parts respectively. Then |L_o(n)|-|L_e(n)| is 0 if n is not a perfect square, and is (-1)^n if n is a perfect square.

Answer by Konrad Swanepoel for Combinatorial results without known combinatorial proofs

2009-11-14T19:47:33Z

The Graham-Pollak Theorem states that the minimum number of complete bipartite graphs needed to disjointly cover the edge set of the complete graph on n vertices is n-1. The only known proofs all use linear algebra, and there is no pure counting proof is known as far as I know. There is a chapter about this in Aigner and Ziegler's Proofs from the BOOK.

Answer by Jérôme JEAN-CHARLES for Combinatorial results without known combinatorial proofs

2010-10-07T22:50:42Z

PROBLEM Of splitting a necklace between two thieves:

Two thieves want to share equally the stones of a necklace ( an open circle).
The necklace has $s$ types of stones ( each type of stone appears an even number of time.).

They want to minimize the number of cuts ( the link are costly and they do not want to make a mess of it).
Show that it is always possible to achieve the split using $s$ cuts.

SOLUTIONS:

For $s=2$ a combinatorial solution is not too difficult.

For any $s$, a topological/linear algebra proof exists ( a nice exposition by Jiri Matousek in reference below.)

http://www.amazon.com/Using-Borsuk-Ulam-Theorem-Combinatorics-Universitext/dp/3540003622

Though by now there seem to be a combinatorial proof.
AT : http://www.combinatorics.org/Volume_16/PDF/v16i1r79.pdf

Yet I believe it might be of interest as a problem that had no combinatorial proof for a while.

Answer by Łukasz Grabowski for Combinatorial results without known combinatorial proofs

2010-10-08T01:57:42Z

Atiyah conjecture for free groups. It has been proved by Peter Linnel using some operator-algebraic technique, but the statement seems to me to be ultimately combinatorial.

For example, as an important special case there is the analytical 0-divisors conjecture: Let T be a self-adjoint element of the complex group ring of a free group of $l^2$-norm at most 1. Consider the sequence $t_n$ of complex numbers: $t_n$ is the coefficient of the neutral element of the element $(1-T)^n$ of the group ring (so this is a combinatorial thing.)

One of the formulations of the analytical 0-divisors conjecture is the following theorem.

Theorem (P. Linnel): If T is not 0 then the limit of the sequence $t_n$ is 0.

Similarly for many other groups for which Atiyah conjecture is known. For example, the proof for elementary amenable group (again Linnel) uses deep K-theory, but admittedly it might be that this deep K-theory is proven using combinatorics.

Answer by Jonah Ostroff for Combinatorial results without known combinatorial proofs

2010-10-08T14:36:24Z

One result I like is that the number of 321-avoiding permutations of length 2n whose matrices are 180°-symmetric is (2n choose n). The best proof I know is fairly short, but I wouldn't call it bijective:

Under the Robinson-Schensted correspondence, the 180°-symmetric permutations are exactly the ones which map to ordered pairs of self-evacuating tableaux, which are in turn in bijection with ordered pairs of domino tableaux in the same shape. (See Stembridge) Now, if you look at the 2-row (since our permutations must be 321-avoiding) domino tableaux of size 2n, there are n+1 Ferrers shapes they can take, and they can be formed from those of size 2n-2 in a way satisfying the relation in Pascal's triangle, so the sum over all 2-row Ferrers shapes of the square of the number of domino tableaux of that shape is the sum of the squares of the binomial coefficients (2n choose i), yielding (2n choose n).

I've tried to "unpack" each of these steps into a simple bijection, but nothing's budged. Still, it seems like the kind of problem that someone else might be able to solve.

Answer by Mike Spivey for Combinatorial results without known combinatorial proofs

2010-10-09T06:41:02Z

The book Proofs that Really Count: The Art of Combinatorial Proof, by Art Benjamin and Jenny Quinn, contains a large number of combinatorial identities with no known combinatorial proof. (See the end of most of the chapters.) As the subtitle indicates, it is also a great reference for those interested in combinatorial proof techniques.

Answer by Jan Weidner for Combinatorial results without known combinatorial proofs

2012-03-24T16:55:10Z

Some "positivity results" can only be proven using heavy geometric machinery at the moment. The most prominent one is positivity of the coefficients of Kazhdan-Lusztig polynomials (in the case of Weyl groups).