combinatorics


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 {X} be a nonnegative random variable on a probability space {\Omega}. A basic observation is that:

\displaystyle \mathbb{P}(X \geq \mathbb{E}( X)) > 0.

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 {K_N}, and let {X} be the random variable which outputs the number of monochromatic {k}-cliques, and {Y = N - X}. We note that if we remove one vertex from {K_N} from each monochromatic edge, we get a 2-colored complete graph with {Y} vertices and no {k}-cliques. (more…)

Let {A_i, 1 \leq i \leq n} be a collection of events in a probability space {\Omega}. There are two situations under which we can conclude that

\displaystyle \bigcup A_i \neq \Omega.

  1. {\sum \mathbb{P}(A_i) < 1}.
  2. The {A_i} are independent of each other. In this case, the {\overline{A_i} } are independent and {\mathbb{P} ( \bigcap \overline{A_i}) = \prod \mathbb{P}(\overline{A_i}) >0}.

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 {R(k, k)}. By definition, {R(k, k)} is large enough such that any 2-coloring of the edges on a complete graph {K_{R(k, k)}} contains a monochromatic {k}-clique {K_k}.

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

\displaystyle \mathbb{P}(E_A) = 2^{1-\binom{k}{2}}.

If {\bigcup_{A: |A| = k} E_A } is a proper subset of the probability space, then there is a 2-coloring of {K_n} with no monochromatic {k}-clique. In particular, if

\displaystyle \sum_{A: |A| = k} \mathbb{P}(E_A) = \binom{n}{k} 2^{1-\binom{k}{2}} < 1,

then we can conclude that there is a 2-coloring of {K_n} without a monochromatic {K_k}, so that {n < R(k, k)}. One concludes the following lower bound:

Theorem 1 (Erdös) If {\binom{n}{k} 2^{1-\binom{k}{2}} < 1}, then {R(k, k) > n}.

 

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

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 {\mathcal{F} \subset 2^{[n]}} be a family of subsets of {[n] \stackrel{\mathrm{def}}{=} \left\{1, 2, \dots, n\right\}}. We let {d(\mathcal{F})} be the number of disjoint pairs of {\mathcal{F}}: that is, the number of pairs {(A, A') \in \mathcal{F}^2} with {A \cap A' = \emptyset}.

Clearly we have

\displaystyle d(\mathcal{F}) \leq \left\lvert \mathcal{F}\right\rvert^2,

and a natural question is whether this inequality can be substantially improved if {|\mathcal{F}|} is large.

If {n} is even, and we take

\displaystyle \mathcal{F} = \left\{A: A \subset \left\{1, 2, \dots, n/2\right\} \ \text{or} A \subset \left\{n/2 +1 , \dots, n\right\}\right\},

then {| \mathcal{F}| = 2^{n/2 + 1}} while

\displaystyle d(\mathcal{F}) \geq 2 ( 2^{n/2} . 2^{n/2})) = 2^{1+n},

by choosing pairs such that one element is contained in {\left\{1, 2, \dots, n/2\right\}} and the other in {\left\{n/2, \dots, n\right\}}, or vice versa. In particular, we find that d(\mathcal{F}) = \Omega( |\mathcal{F}|^2).

Nonetheless, if {|\mathcal{F}|} grows sufficiently fast, then we have:

Theorem 1 (Alon and Frankl) If we require {|\mathcal{F}| \geq 2^{(1/2 + \delta) n}} for {\delta >0}, then

\displaystyle d(\mathcal{F}) = o( |\mathcal{F}|^2)

as {n \rightarrow \infty}. (more…)

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 {G = (V, E)} be an undirected graph, such that each edge {e \in E} has a “weight” or “cost” {w(e) \in \mathbb{R}} associated with it. The problem is to find a minimal spanning tree. That is, a subtree {T \subset G} containing all the vertices and such that {\sum_{e \in  T} w(e)} 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 {n} 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 {G}, we are interested in the following problem: Is there a subgraph {T \subset G} which is a tree and which contains every vertex of {G}? 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. (more…)

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.

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 {f: B^n \rightarrow B^n} (for {B^n} the unit ball in euclidean {n}-space {\mathbb{R}^n}) has a fixed point.

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

\displaystyle \left\{ f: B^n \rightarrow B^n \ \mathrm{with} \ \mathrm{no} \ \mathrm{fixed \ pt } \right\}

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

Now one way you could take this is to assume that {f} 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 {B^n} with a simplicial complex. (more…)

[This post, a continuation of the series on representation theory in complex rank, discusses the irreducibles in Deligne’s category \mathrm{Rep}(S_t) for t \notin \mathbb{Z}_{\geq 0} and what one can do with them.]

OK, so we now know that Deligne’s categories {\mathrm{Rep}(S_t)} are semisimple when {t \notin  \mathbb{Z}_{\geq 0}}. But, this is a paradox. Deligne’s categories, a family of categories constructed to interpolate the semisimple categories of representations of {S_n, n \in \mathbb{Z}_{\geq  0}} are semisimple precisely at the complement of the nonnegative integers!

The problem is, when {t \in \mathbb{Z}_{\geq 0}}, {\mathrm{Rep}(S_t)} is not equivalent to the ordinary category {\mathrm{Rep}^{\mathrm{ord}}(S_t)}. 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 {\mathrm{Rep}(S_t)} (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 {\mathrm{Rep}(S_t), t \notin \mathbb{Z}_{\geq 0}}, look like. We know what the simple {S_n}-representations are; they are the Specht modules, parametrized by the Young diagrams of size {n}. It turns out that the simple objects in {\mathrm{Rep}(S_t)} 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 {\mathrm{Rep}^{\mathrm{ord}}(S_n), n \in \mathbb{Z}_{\geq  0}}. Namely, we let {\mathrm{Rep}^{\mathrm{ord}}(S_n)^{(N)}} denote the category generated by {\mathfrak{h}^{\otimes p}, p \leq  N} for {\mathfrak{h}} the regular representation. When {N} is large enough, this becomes the full category, so we will always pretend that {n} is really really large relative to {N} (which is kinda ironic when you think about the notation…).

Anyhow, we want to look at the simple objects in {\mathrm{Rep}^{\mathrm{ord}}(S_n)^{(N)}}. Well, these are going to have to correspond to some Young diagrmas of size {n}, but the question is which ones?

I claim that the Young diagrams that arise are precisely those where the rows below the top have {\leq N} boxes.

In particular, as {n} gets large, the top row must get really long, but the number of simple objects stays bounded. (more…)

Next Page »