The first and second moment methods

As I mentioned earlier, I’ve been reading a little about the probabilistic method, especially in combinatorics and related fields, as a result of a course I’m TAing. This material is certainly fundamental to a lot of mathematics and computer science, but I’ve never really studied probability. I’ve been trying to change that. The material in this post is from Alon and Spencer’s The Probabilistic Method.

 

1. First moments

For the purposes of the probabilistic method, we often want to show that a certain event is possible, which is done by showing that it occurs with positive probability as the outcome of a random process. Let be a nonnegative random variable on a probability space . A basic observation is that:

that is, a random variable takes at least its expectation value with positive probability. This alone is sufficient to obtain many interesting results.

Example: Let’s go back to the problem of bounding below the Ramsey numbers. Consider a random 2-coloring of the edges of the graph , and let be the random variable which outputs the number of monochromatic -cliques, and . We note that if we remove one vertex from from each monochromatic edge, we get a 2-colored complete graph with vertices and no -cliques.

 

Ramsey theory and the probabilistic method

Let be a collection of events in a probability space . There are two situations under which we can conclude that

1. .
2. The are independent of each other. In this case, the are independent and .

There are a number of probabilistic arguments in combinatorics which can be made from the first situation alone. One of the original examples is the problem of bounding below the Ramsey numbers . By definition, is large enough such that any 2-coloring of the edges on a complete graph contains a monochromatic -clique .

In order to show that must be larger than some value , one chooses a random 2-coloring (with both colors equally likely and the coloring of each edge independent) on the edges of a . For each -subset , let be the event that is monochromatic under this 2-coloring, so that

If is a proper subset of the probability space, then there is a 2-coloring of with no monochromatic -clique. In particular, if

then we can conclude that there is a 2-coloring of without a monochromatic , so that . One concludes the following lower bound:

Theorem 1 (Erdös) If , then .

 

In such arguments, the individual “bad” events (say, the ) had small probability, and to show that they did not together exhaust the entire probability space, one used the relatively crude bound : that is, we used the first of the above two conditions at the beginning of this post. In practice, the events are not independent, but a large proportion of them are, and that might suggest the use of a “hybrid” of the two strategies.

 

Disjoint pairs and the probabilistic method

I’m TAing a combinatorics course this semester, and as a result I’ve been reading a few books on the subject recently. I’ve in particular been reading Alon and Spencer’s book on the probabilistic method. In this post, I’d like to highlight one of the examples I learned from it; there is a paper by Alon and Frankl where the material originates.

Let be a family of subsets of . We let be the number of disjoint pairs of : that is, the number of pairs with .

Clearly we have

and a natural question is whether this inequality can be substantially improved if is large.

If is even, and we take

then while

by choosing pairs such that one element is contained in and the other in , or vice versa. In particular, we find that 

Nonetheless, if grows sufficiently fast, then we have:

Theorem 1 (Alon and Frankl) If we require for , then

as .

 

Spanning trees, the cut property, and Kruskal’s algorithm

I decided this semester to take an algorithms course, in an attempt to finally learn some discrete math. As of late, we have been talking about graph algorithms. The problem is that, having never thought much about graphs, I don’t have a great deal of intuition for them. So I want to devote a post to try to help myself understand this material better.

The problem we are currently concerned with is the following. Let be an undirected graph, such that each edge has a “weight” or “cost” associated with it. The problem is to find a minimal spanning tree. That is, a subtree containing all the vertices and such that is minimal. The naive approach of listing every possible tree and calculating the weights for each of them is horribly inefficient here, as the number of trees on a complete graph of size grows super-exponentially.

1. Trees

To start with, I will recall the definition of a tree. All graphs will be undirected.

Definition 1 A tree is a connected graph containing no cycles.

Intuitively, one has the standard picture of a node branching out into several nodes, each of which branch into several other nodes, and so on. In fact, with the above definition one can show in fact the precise analog of the preceding statement: the “geometric realization” of a tree (when considered as a simplicial complex) is contractible. The above definition is precise, and furthermore is equivalent to the following. An easy consequence of the definition, that we will use, is that a connected subgraph of a tree is tree.

Given a graph , we are interested in the following problem: Is there a subgraph which is a tree and which contains every vertex of ? Such a subgraph is called a spanning tree. Physically, there are reasonable instances where one might wish to find one, such as in building a pipeline system. The claim is that a spanning tree always exists. To see this, we shall use the following characterization of trees:

Proposition 2 A graph is a tree if and only if it is connected and removing any edge would make it disconnected.

So trees are precisely the minimal connected graphs.

 

A talk on Sperner’s lemma and two applications

I gave this talk earlier today. It went somewhat well, though I didn’t say too much about the Brouwer fixed-point theorem. The main application I got to was the theorem of Monsky that one cannot subdivide a square into an odd number of triangles of equal area. Bizarrely, the only known proof of this result uses properties of the 2-adic valuation, in particular its extendability to the real line.

I could run latex2wp and make this into a proper blog post, but I think I’ll just leave it as a PDF for anyone interested to look at.

 

The combinatorial approach to Brouwer’s fixed point theorem

There is an clever and interesting combinatorial (homology-free) approach to the proof of the well-known Brouwer fixed point theorem. Recall that this theorem states that:

Theorem 1 Any continuous (for the unit ball in euclidean -space ) has a fixed point.

The first idea that suggests that a combinatorial approach might tackle the Brouwer theorem is that the set

is open in the set of continuous maps (with the uniform topology). So if we can show that any continuous map can be uniformly approximated by maps that do have fixed points to an arbitrary degree, then it will follow that itself has a fixed point.

Now one way you could take this is to assume that is differentiable. And indeed, there are differential-topological proofs of Brouwer’s theorem. This is not the purpose of the present post, though. We will replace the continuous ball with a simplicial complex.

 

The ideology of a long top row: Or, why you shouldn’t be surprised about the irreducibles in Rep(S_t)

[This post, a continuation of the series on representation theory in complex rank, discusses the irreducibles in Deligne’s category for and what one can do with them.]

OK, so we now know that Deligne’s categories are semisimple when . But, this is a paradox. Deligne’s categories, a family of categories constructed to interpolate the semisimple categories of representations of are semisimple precisely at the complement of the nonnegative integers!

The problem is, when , is not equivalent to the ordinary category . The problem is that not all relations correspond to actual morphisms. Deligne in fact shows that the ordinary category can be obtained as a quotient of his (via the tensor ideal of “neglligible morphisms”) but this isn’t really important for the story I’m telling.

1. Motivation and remarks

Today, I want to talk about what the simple objects in , look like. We know what the simple -representations are; they are the Specht modules, parametrized by the Young diagrams of size . It turns out that the simple objects in are parametrized by the Young diagrams of arbitrary size. There is an interesting way of thinking about this that Etingof explains in his talk, and which I will try to motivate here now.

OK. So, just as we defined a filtration on Deligne’s categories yesterday, let’s define a filtration on the ordinary representation categories . Namely, we let denote the category generated by for the regular representation. When is large enough, this becomes the full category, so we will always pretend that is really really large relative to (which is kinda ironic when you think about the notation…).

Anyhow, we want to look at the simple objects in . Well, these are going to have to correspond to some Young diagrmas of size , but the question is which ones?

I claim that the Young diagrams that arise are precisely those where the rows below the top have boxes.

In particular, as gets large, the top row must get really long, but the number of simple objects stays bounded.

 

Deligne’s category Rep(S_t) for t not necessarily an integer

[Updated, 6/12; various errors fixed]

I’ve just uploaded to arXiv my paper (submitted to J. of Algebra) “Categories parametrized by schemes and representation theory in complex rank,” an outgrowth of my RSI project started last summer, where I worked with Pavel Etingof and Dustin Clausen.  I will devote this post to talking about some of the story surrounding it. In short, the project is about looking at this program of studying representation theory when the dimension is complex (admittedly nobody has ever seen a vector space of dimension ; I will explain this precisely below) in the simplest possible case.  But the categories of interest in the project are built out of certain symmetric tensor categories that Deligne defined back in 2004, and I’ll talk a bit about those today. I could have just jumped straight into my paper, but I figured this would make things potentially more accessible, and would be more fun.

I also recommend looking at these posts of David Speyer and Noah Snyder, which talk about some of Deligne’s work as well (and which I learned a lot from). Also, cf. this talk of Pavel Etingof.  The talk goes further (into the non-semisimple analogs of Deligne’s categories) that I will cover in a later post. Finally, the paper of Deligne is available here.

1. Motivation

The whole story behind this starts with the representation theory of the classical groups—these are objects like , etc. And in particular, I’m going to zoom in on the symmetric group—or more precisely, the family of symmetric groups .

The symmetric group is a very complicated object (indeed, any finite group is a subgroup of a symmetric group, by Cayley’s theorem), but its representation theory has been understood for 100 years and has many interesting combinatorial facets.

In the modern language, we can package the entire representation theory of into a category (depending on the nonnegative integer ). This is a very interesting category for several reasons. The first, and most obvious, part of its structure is that it is a -linear abelian category.

More interestingly, it’s semisimple: every exact sequence splits. This is because the group algebra is semisimple, by Maschke’s theorem. In addition, it is a tensor category: we can define the tensor product of any two representations of a group in a natural way, and is no exception. It is even a symmetric tensor category because we have a nice isomorphism for any two representations .

Technically, all this works for any finite group. What’s special about the symmetric group is, for instance, the very nice way the simple objects of (i.e. irreducible representations) are parametrized. Namely, (as for every finite group) they are in bijection with the conjugacy classes of , but (unlike for other groups) we have an explicit map between such conjugacy classes and irreducible representations. Since each conjugacy class of corresponds to a partiton of (a well-known fact easily seen because any permutation can be written as a product of disjoint cycles),

The whole idea behind Deligne’s work is that, while there isn’t any such thing as a symmetric group on elements, there is nevertheless a category (or more generally for ) that has much of the same structure. Deligne constructed these categories via an interpolation procedure.

2. Interpolation

 

In which I post my AP Econ. final project

Since my latest posts have been contrary to the mission of this blog, why not.

So, we were assigned to write a paper about any topic of interest.  I naturally sprinted my way to the bank to cash the blank check and wrote mine to be an exposition of Arrow’s theorem. (Yes, it’s a scam, but scams can be fun.) Here’s the file.   Presumably readers of this splog blog will be most interested in the second section, which gives an exposition of the proof.

 

An infinite Ramsey theorem for graphs

I’m not yet back to full-blown quasi-daily blogging.  But I couldn’t resist this all the same. 

Edit: I am embarrassed to admit that I used the wrong terminology in the first version of this entry.  I said “discrete graph” for null graph.  Whoops.

I recently learned about a version of Ramsey’s theorem in combinatorics:

Let .  There is such that if be a graph with more than vertices, then contains either a null subgraph of size or a complete subgraph of size .

One of the interesting applications of model theory is that this (finitary) version of Ramsey’s theorem can be proved using the simpler infinite Ramsey theorem.  There are other such applications, e.g., using the regular Nullstellensatz to prove one with bounds on the coefficients.  The idea is similar to the theorem of Robinson that a sentence of first-order logic holding in fields of characteristic zero must hold in fields of all but finitely many characteristics.   All this abstract nonsense (OK, it’s not technically category theory, but it has the same feel) deserves its own post at some point.

I don’t have time for a full post that explains all this, but I found the infinite Ramsey theorem an interesting problem in itself.

Let be an infinite graph.  Then contains either an infinite complete subgraph or an infinite null subgraph.

To prove this, let be the collection of vertices that are connected to only finitely many other vertices. 

1) If is infinite, we may construct a null subgraph is follows.  Choose ; then choose not one of the finitely many points connected to ; then not connected to .  The infiniteness of allows this process to continue indefinitely.

2) If is finite, we may assume wlog that for any infinite subgraph , the analogous set is finite (or we could use the previous reasoning applied to ).   Now choose , which is connected to infinitely many vertices that form a subgraph ; then each vertex of is connected to .  Also, because (the analog of for ) is finite, we can choose connected to infinitely many points of .  Then define to be the subgraph of consisting of points connected to .  Repeating this process, one obtains an infinite sequence such that is connected to (by virtue of belonging to ), which is thus a complete subgraph.