A proof length challenge July 26, 2010

Here is a question I thought of this morning, and have given no serious thought to — hence, perfect for a blog post.

In any commutative ring, if and are matrices, and , then .

For any fixed , there should be a proof of this by direct algebraic manipulation: Start with the equations saying that , and add, multiply, expand and recombine them to produce the equations saying that . Our starting point is equations of size , as is our destination. But every route I see involves writing down the adjoint of or , which is an expression of length .

Can we show that a direct proof of this result must involve either an expression of exponential length, or an exponentially long proof?

Bleg: Great combinatorial applications July 15, 2010

I am currently writing up a syllabus for a combinatorics course. I want to show the students that combinatorics is not just a collection of puzzles, but that it has connections to lots of interesting problems. Because the prerequisites for this course are fairly minimal (calculus and linear algebra), I think I’d do best to talk about applied uses. So, this is a request for cool applications of combinatorial techniques, which I can explain in a single lecture or less. Cool applications within math are also welcome, if they can be explained at a low level.

Details: The audience is mixed undergrad-grad. The undergrads will probably mostly be math majors, but I hope to haul in some engineers and computer scientists. I plan to organize the course into four main topics (which means none of them can be covered in depth):

• Generating functions and enumeration
• Graph theory
• Posets
• Combinatorial geometry

Two things I am not doing: Symmetric functions and representation theory, because we’ll have a separate course on that, and asymptotics, because that would increase the prerequisites significantly.

Thanks!