Timeline for Examples of combinatorial problems where the only known solutions, or most "natural" solutions, use representation theory?
Current License: CC BY-SA 4.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 4 at 12:44 | comment | added | Timothy Chow | For those not familiar with Proctor's work, here is perhaps the most easily stated example of a result that is (arguably) most naturally proved using the representation theory of $\mathfrak{sl}_2(\mathbb{C})$: The coefficients of the polynomial $(1+x)(1+x^2)(1+x^3)\cdots(1+x^n)$ form a unimodal sequence. I believe that there is still no really simple combinatorial proof of this fact. One can "dismantle" the representation-theoretic proof to make it more "elementary", as Proctor does, but the result is still a rather complicated proof. | |
| Nov 4 at 10:13 | history | made wiki | Post Made Community Wiki by Stefan Kohl♦ | ||
| Nov 4 at 7:02 | comment | added | Naysh | Thanks everyone for the examples! In reply to Will Sawin's question, yes my main interest is in problems which can be stated naturally (and ideally were already being studied independently) without invoking representation theoretic language. | |
| Nov 4 at 1:45 | answer | added | Benjamin Steinberg | timeline score: 3 | |
| Nov 3 at 22:45 | history | edited | LSpice | CC BY-SA 4.0 |
Name of "this paper"
|
| Nov 3 at 21:07 | comment | added | Asaf | If you count construction of expander graphs then sure, Lubotzky-Phillips-Sarnak/Margulis | |
| Nov 3 at 20:16 | history | became hot network question | |||
| Nov 3 at 17:33 | comment | added | Sam Hopkins | Another place to look: Stanley's list of Bijective Proof Problems (math.mit.edu/~rstan/bij.pdf). Problems marked [*] have no combinatorial proofs. Of course, not all of the non-combinatorial proofs here are from representation theory, but many are. | |
| Nov 3 at 16:50 | answer | added | Sam Hopkins | timeline score: 4 | |
| Nov 3 at 16:17 | answer | added | Sam Hopkins | timeline score: 8 | |
| Nov 3 at 13:06 | comment | added | Will Sawin | Maybe for quantities that are most naturally defined representation-theoretically, the interesting question is if there is any combinatorial proof (as Sam was discussing mathoverflow.net/questions/481722/…) but for quantities that are most naturally defined combinatorially one can ask if the most natural proof is representation-theoretic. | |
| Nov 3 at 13:01 | comment | added | Will Sawin | Do you want to include the proviso that the problem itself can't be expressed in a more motivated and natural way using representation-theoretic language? Several quantities in representation theory (e.g. characters of the symmetric group) have purely combinatorial formulas for them. Every property these quantities satisfy can therefore be expressed as the resolution of a combinatorial problem. For many properties the most motivated and natural proof surely uses representation theory. Is this an example of what you want? | |
| Nov 3 at 13:01 | comment | added | Sam Hopkins | There are many examples. In many cases the only reason we know some quantity is positive (e.g. plethysm coefficients, Kronecker coefficients, Schubert polynomial structure constants, row sums of character tables of $S_n$) is because of representation theory and/or algebraic geometry. This is even though these quantities have purely combinatorial descriptions. See Stanley's classic survey on positivity problems in algebraic combinatorics (math.mit.edu/~rstan/papers/problems.pdf) and my related question: mathoverflow.net/questions/349406. | |
| Nov 3 at 12:14 | history | asked | Naysh | CC BY-SA 4.0 |