More on graphs and digraphs

So this question’s been bugging me ever since I first thought it up, and I figured (in the spirit of MaBloWriMo, which by now is pretty much dead on this blog) that I’d ask about it here — I need to give Math Overflow a break.

The question concerns adjoint functors, which I don’t understand half as well as I’d like, but enjoy thinking about anyway. One of the (many!) motivating examples that adjoint functors generalize is the common “free/forgetful” dichotomy. For instance, there’s a functor from the category of groups (say) to the category of sets, which is defined by simply “forgetting” the group structure and giving back the underlying set. This functor doesn’t have an inverse, of course; that would make the two categories isomorphic, which is way too much to expect. Nor does it have an “inverse up to natural transformation.” That would make the categories equivalent, which is almost as good as isomorphism. But it does have the next-best thing after that: a functor in the opposite direction which comes with a natural isomorphism on some hom-sets. This is the free functor, that assigns to each set the free group on that set. These functors are called adjoint functors.

Generalized LYM inequalities

I’ve been thinking about this problem ever since an old post of Qiaochu’s first raised the question, and I’ve been frustrated by my inability to solve it. I could post it on MO, but I sort of already have, and anyway it raises questions which are too ill-formed right now to be right for MO. So anyway, here we go:

A lot of problems in extremal combinatorics correspond to finding large antichains in partially ordered sets. (By the way, all posets in this post will be assumed to have a least element.) Classically speaking, Dilworth’s theorem completely characterizes the size of antichains in posets; however, this is often tricky to apply, since it’s not always clear whether a partition into chains is minimal. In addition, it’s sometimes the case (particularly with infinite posets) that there are infinitely long antichains, but a nontrivial bound should still be attainable. The way to get by both of these obstacles is to assign weights to the elements of the poset, and rather than looking for large antichains, we look for antichains with high total weight.

The classical example of this solves the problem of finding the largest antichain in the lattice of subsets of a given finite set — the content of Sperner’s theorem.

In which I am late to the MaBloWriMo party

Hey, guys. Been a while, hasn’t it? Sorry for not blogging more; I blame having to “learn stuff” in “classes.” It’s very silly.

I didn’t find out about Charles Siegel’s MaBloWriMo until almost November 2 (and then there were more of the aforementioned “classes”), but it sounded cool, and gave me a reason to get back to blogging. So to make up for the late start, I’m going to try to write at least 30 total posts for the month of November, which should hopefully average in the range of 1000 words in length.

So, again because of school, I’m supposed to be spending November writing a final (expository) paper for introductory algebraic geometry. This means that I’ll probably be posting bits and pieces of drafts of said paper for MaBloWriMo, which means that there’ll be some unifying theme to some of the posts. The bad news is, I don’t actually know what it is yet, since I haven’t figured out my final paper topic, since I’ve been procrastinating horribly.

So instead I’ll talk about my usual craziness; over the next few days, I’ll ask the question: Is there a higher category theory for graphs? What is it?

So if you’re a combinatorialist, the easy way to think about categories (at least at first) is as special sorts of directed graphs with some extra structure (specifically, a way to glue together edges to make new edges.) To make this rigorous, we can think of every (small) category as having an “underlying digraph” where we just draw a directed edge from X to Y if there’s a morphism .

It turns out that this construction’s functorial: it gives us a forgetful functor from the category of small categories to the category of digraphs. (A morphism between digraphs, by the way, is exactly what it “should” be; it’s a function between the vertex sets that respects the adjacency structure.)

GILA 4: The pseudorandom case

So in the last post, we defined the discrete Fourier transform and gave some of its basic properties. At the end, we claimed that it gives us a simple notion of pseudorandomness that allows us to make rigorous the intuition that “pseudorandom subsets of should have many arithmetic progressions.” Today we’re going to justify this notion of pseudorandomness, and work through this — the easy case — of the proof of Roth’s theorem for . At the end, we’ll sketch how to modify the method for the regular, finitary version of the theorem.

In which I celebrate Labor Day by ripping off others

I’m kidding, of course; I do that all the time. But, in honor of Labor Day, on which many Americans traditionally take the day off from work, I’m going to link to a bunch of other people’s cool stuff instead of writing it myself.

To start with, I finally updated my links sidebar to include John Baez’ “This Week’s Finds,” which has been running for something like 15 years (unfortunately, not every week) and has recently seen a spate of updates. TWF is always very readable and very interesting, and if you don’t read it, you really should. But I have to advise caution: it’s all too easy for your browser to end up looking like this.

Do you read Achewood? If not, now might be an interesting time to start — one of the most gripping stories since the famous Great Outdoor Fight (which led to a trade paperback being released last year) is currently ongoing. It’s a long trip through the archives (something like 1700 strips and counting), but it’s worth it — if you’re not sure what to do with the last few hours of the long weekend, you can always kick back with a good webcomic. (Note: If you’re easily offended, Achewood might not be for you — these cats drink, smoke, cuss, and everything else — but if you can handle that, its offbeat humor and minimalist visuals are well worth checking out.)

We have less than a year to go until the next ICM, and speculation about the prizewinners is starting to kick into gear over at Not Even Wrong. Ngo Bau Chao looks like the best bet for a Fields next year, but the really interesting thing is the very good possibility that the Nevanlinna prize might finally be awarded to a woman, with nearly half the qualified TCS sectional speakers, plus the token TCS plenary speaker (Irit Dinur), being women. But Ben Webster suggests that the ICM is maybe not such a good idea.

I ran across Eric Schechter’s page of undergraduate errors the other day, and was struck in particular by “the derivative of problem” — sort of a scaled-up version of my “derivative of problem.” The whole page raises some interesting pedagogical questions, and if you’re into that sort of thing, check it out!

Scott Aaronson’s Worldview Manager is up, about a year after its conception. It’s an interesting idea, although the implementation’s far from perfect. I’m pleased to say that I had an epsilon-sized role in the creation of the Manager; my very good friend Louis was one of Scott’s students this summer, and he’d occasionally ask me about anything from low-level implementation to “is this a good complexity-theory implication?” My contribution was generally to sit back and let him puzzle it out (indeed, that’s usually all I could do!) but it still felt cool to watch it evolve in real time.

Finally, many parents, here in Georgia and elsewhere, are keeping their children at home tomorrow instead of having them exposed to President Obama’s evil Muslim back-to-school propaganda. Partially in an attempt to counteract this, the White House has posted the text of the address ahead of time. You can, and maybe should, read it here.

Quasi-bleg: Why are there bump functions?

When I was learning analysis (beyond, say, first-year calculus), one of the facts that most surprised me was the fact that there are functions that were smooth (i.e., infinitely differentiable) and yet compactly supported. Of course, I didn’t think about it with that phrasing; there’s a pretty simple geometric interpretation of smoothness for most functions one encounters in calculus (actually, one rarely sees differentiable functions that aren’t smooth!) Specifically, if a function isn’t smooth at , then there’s some sort of a “kink” at that point, or at least “around” that point.

Is this justified? Well, not totally, but let’s give a couple of examples to at least show why it’s a good first approximation.

GILA 3: The Fourier transform, and why it works

At the end of the last post, we outlined an approach to proving Roth’s theorem via a density-increment method. I’ll re-post it here, a little more fleshed out, for convenience.

Sketch. The idea is to deal with “structured sets” (like sets that are themselves long arithmetic progressions) and “pseudo-random sets” in different ways; we saw last time that the density-increment argument looks promising for structured sets, but “random” sets won’t succumb to it.

First, we need to make rigorous our intuition that “random enough” sets of positive density will have length-3 APs. The obvious way to do this is by showing the contrapositive. We want to find some suitable “randomness measure” such that random dense sets have high randomness measure. Now let be a positive-density set without 3-APs; we want to show that this condition is enough to guarantee that has low randomness measure.

Now for our modified-probabilistic argument. We want to show that “low-randomness” sets can’t be uniformly distributed (mod d) for every d; this guarantees the existence of an AP on which it has higher density. We pass to this AP; rinse, lather, and repeat, until our density rises above some pre-set bound ( will do nicely.) We also want to introduce a tool that tells us how much a set “looks like” an arithmetic progression with common difference d; this is because we need to obtain quantitative bounds for the density-increment argument, in order to ensure that the densities of our set on the sequence of APs don’t monotonically approach, say, 0.0000001.

So we’re looking for two technical tools; one that quantifies the “randomness” of a set, and one that lets us correlate our set with a candidate arithmetic progression to pass to so that our density-increment argument will actually work quantitatively. As it turns out, though, we can find one tool that will do both jobs for us; the discrete Fourier transform.

GILA 2: The probabilistic approach

To begin, a historical curiosity. In the last post, I talked about Khinchin’s little book on number theory, which from today’s perspective is one of the earliest books to deal entirely with additive combinatorics and additive number theory. One of Khinchin’s most famous results has to do with the denominators of continued fractions; Khinchin’s original proof of the theorem was quite complicated and involved. Nowadays, the existence of Khinchin’s constant is understood as a simple consequence of the ergodicity of the Gauss-Kuzmin-Wirsing operator.

Where else do we see ergodic theory popping up to simplify complicated proofs? Why, in additive combinatorics! Although we won’t discuss it in this series, ergodic theory has become a central tool for Szemeredi-type theorems, and some results are still only provable by such methods (for instance, until recently, the density Hales-Jewett theorem was in this class.)

To top it all off, note that ergodic theory was originally motivated by problems in statistical physics. Guess who wrote one of the best-known textbooks on mathematical statistical physics? But on to the math!

We’ve seen that traditional arguments based on the pigeonhole principle and such aren’t sufficient to prove Roth’s theorem. So we’ll go to the next tool in our kit — the probabilistic method.

The probabilistic method is one of the most useful weapons in a combinatorialist’s arsenal, even having a whole textbook devoted to it. (The linked page is out of date; a third edition was published last year.) The core of the method is this — if we want to show the existence of an object with a given property, instead of constructing one directly, we instead show that a randomly chosen large enough object has the property with positive probability. Its best-known use in Ramsey theory is for proving lower bounds, where it often gives the best known results, but clever applications can give upper bounds as well, for instance in the proof of Kraft’s inequality. Of particular interest to us is the fact that it provides our first nontrivial proof in the direction of Roth’s theorem.

GILA 1: van der Waerden and all that

I’m beginning my GILA series announced on Thursday with a short exposition of van der Waerden’s theorem, and an attempt to extend its proof to the density version (at least in the k=3 case). Before I start, I should mention something I neglected in the last post: that this series is as much for my benefit as for that of any “interested lay audience” out there. Someone like Terry Tao could undoubtedly do a better series of this type (and, indeed, I’ll be leaning heavily on my borrowed copy of Tao and Van Vu’s Additive Combinatorics throughout) but they haven’t, so I’ll try. However, there are certain to be a number of embarrassing mistakes, unjustified statements, lines of thinking left unresolved, etc., throughout (indeed, an anonymous commenter noted two in the introductory post!), and I encourage readers to point them out in the comments.

So, on to van der Waerden’s theorem. van der Waerden’s theorem is one of the early jewels of Ramsey theory (actually predating Ramsey’s article by a couple of years) and can be viewed as a weaker version of Szemeredi’s theorem. It states simply that, for any integers , if you color the positive integers with c colors, then there exists a monochromatic k-term arithmetic progression.

Khinchin, in his wonderful book which unfortunately appears to be out of print (at least in English), gives some history of the problem:

All to whom this question [the theorem in the c = 2 case] was put regarded the problem at first sight as quite simple; its solution in the affirmative appeared to be almost self-evident. The first attempts to solve it, however, led to nought… [T]his problem, provoking in its resistance, soon became the object of general mathematical interest… I made [van der Waerden's] acquaintance, and learned the solution from him personally. It was elementary, but not simple by any means. The problem turned out to be deep; the appearance of simplicity was deceptive.

This last clause is particularly wonderful, describing as it does not only van der Waerden’s theorem but Ramsey theory and perhaps even combinatorics in general.

The usual proof (given in story-form by Zeilberger here) is not van der Waerden’s, however, but comes from Khinchin, attributed by him to a M.A. Lukomskaya in Minsk. It is a masterpiece, using nothing but a very clever inductive argument and some application of the pigeonhole principle. For the sake of self-containedness, I’ll sketch the argument below the fold.

GILA 0: Roth’s proof of Roth’s theorem

I’m returning from my unplanned, unannounced hiatus from blogging with a series on the standard (Fourier-theoretic) proof of Roth’s theorem on arithmetic progressions, otherwise known as the k = 3 case of Szemeredi’s theorem. I’d like to start out by noting that there’s no shortage of good expositions on the topic; a quick Google search will turn up several. This series will differ from these expositions, however, in two key ways.

First, I’ll try to highlight the key ideas of the proof, rather than get bogged down in the calculations. Although, by the end of the series, we should have at least a sketch of a complete proof of Roth’s theorem, I want to make it easy to separate the real insights from the straightfoward calculational machinery. So I’ll likely present a high-level overview of the proof in the main body of these posts, with one or several appendices fleshing out the computations needed to ensure that the overview works.

Second, and more importantly, this is to be a piece of historical fiction. Although I don’t know how Roth came upon his original proof, he was a number theorist and an expert in Diophantine approximation, and was therefore familiar with things like Fourier analysis. I want to approach the problem from the perspective of a combinatorialist roughly contemporaneous with Roth, who’d be familiar with standard combinatorial methods but not with some of the more technical tools, and attempt to re-derive the proof from that viewpoint.

The real meat of the series will start this weekend (which is why this post is numbered 0), but since this is targeted toward a Generally Interested Lay Audience, I’d like to introduce a few topics which a layman might not be familiar with below the cut.