# Applications of Measure, Integration and Banach Spaces to Combinatorics

I'm going to be teaching a Master's level analysis course(measure theory, Lebesgue integration, Banach and Hilbert spaces, and if there's time, some spectral or PDE stuff) in the fall. My problem is that while roughly half of the students will actually be using analysis in their further work, the rest of them are going to specialize in combinatorics, and while I want to convince them that they should know this stuff as part of their general mathematical culture, I'd also like to try to connect it to what they'll be working on. So far, I've found survey articles on applications of Ramsey theory to Banach spaces, and applications of harmonic analysis to additive number theory, but I was wondering whether anyone had some suggestions of references for applications of classical analysis to old-fashioned, classical combinatorics. (I realise that this is a pretty tall order, as on many levels, these two fields are at antipodes.)

PS: I'm planning on talking about probability measures on discrete spaces, but I don't think that will convince the combinatorics people that hacking through the construction of the Lebesgue integral could have a practical payoff someday for them.

-
Well, I don't know what you mean by "combinatorics", but there are many connections between functional analysis and discrete mathematics. Try, for example, wapedia.mobi/en/Johnson–Lindenstrauss_lemma and look at Jiri Matoušek's books and expository articles. –  Bill Johnson Aug 27 '10 at 1:02
While the goal of motivating the students by presenting diverse applications is commendable, at this basic level you can't meaningfully say much of depth (as Steve Huntsman commented, probability, a la Feller, is a bridge, but that's already a course of its own). There is also a real danger of losing analysts by emphasizing combinatorics too much. If they view it as an annoying distraction, in a course that isn't even nominally related to combinatorics, they'd be right. Maybe the solution is not to try to be something for everyone, but to assume some maturity on the students' part. –  Victor Protsak Aug 27 '10 at 1:27
I agree. However, here should enter the sensitivity of the teacher. Showing at least connections with different fields is a good thing, and in case the audience reacts positively, one may decide to expand. Also, in presence of a class of students that have already chosen their own specialization, a very nice thing is to schedule a short seminal part with expositions by the students, each one on his/her favourite field. –  Pietro Majer Aug 27 '10 at 8:44
The existence of the internet means that the days of - Me Teacher. Me Teach. You Pupil. You Learn. - are over. Instead tell the students how interconnected mathematics is, and ask each of them to search the internet to find papers that link functional analysis to their own favourite topics and perhaps ask the students to present their findings to the class. Make it a competition to see who can find the most interesting links. –  user8232 Aug 27 '10 at 17:06
Pietro's suggestion about presentations is eminently sensible, I just don't see how to do it in a measure theory - functional analysis class. "Make it a competition to see who can find the most interesting links": I've actually done this once as a motivational exercise in a linear algebra class I taught, and the feel-good effect aside, its instructional value was surprisingly low - while I expected some attempt at understanding, all it did was establish that students knew what a search engine was. Even if that's an improvement over unknown's pidgin education standards, it ain't much. –  Victor Protsak Aug 28 '10 at 17:01

Here's a nice application of measure theory, precisely, of the the theory of orthogonal polynomials, to a classic problem of counting derangements.

Problem: How many anagrams with no fixed letters of a given word are there?

For instance, for a word made of only two different letters, say $n$ letters $A$ and $m$ letters $B$, the answer is, of course, 1 or 0 according whether $n = m$ or not, for the only way to form an anagram without fixed letters is, exchanging all the $A$ with $B$, and this is possible if and only if $n=m$.

In the general case, for a word with $n_1$ letters $X_1$, $n_2$ letters $X_2$, ..., $n_r$ letters $X_r$, you will find (after the proper use of the inclusion-exclusion formula) that the answer has the form of a sum of products, that looks very much like the expansion of a product of sums, yet it is not. It is not, exactly because of the presence of terms $k!$, that would formally make a true expansion of a product of sums, if only they where replaced by corresponding terms $x^k$. This suggests to express them with the Eulerian integral $k!=\int_0^\infty x^ke^{-x}dx$, with the effect that the said expression becomes an integral (with the weight $e^{-x}$) of a true product of sums: precisely,

$$\int_0^\infty P_{n_1} (x) P_{n_2}(x)\cdots P_{n_r}(x)\, e^{-x}\, dx,$$

with a certain sequence of polynomials $P_n$, where $P_n$, has degree $n$. But the above answer for the case $r=2$ gives an orthogonality relation, whence the $P_n$, are the Laguerre polynomials, (up to a sign that is easily decided). Note that in the case with no repeated letters, all $n_i=1$, one finds again the more popular enumeration of permutations without fixed points.

Disclaimer: I partially copied this from wikipedia; it's me who wrote it there. The above is my personal amateur's solution, and possibly differs slightly from the vulgata. An on-line reference, with generalizations of the problem, is e.g.

Weighted derangements and Laguerre polynomials, D.Foata and D.Zeilberger, SIAM J. Discrete Math. 1 (1988) 425-433.

-
Thanks! That sounds perfect for one of the student talks at the end of term; they'll get to do a bit more on orthogonal polynomials than I'm counting on doing, and then the application will be a nice payoff. –  Gordon Craig Sep 13 '10 at 19:15

Fourier Analysis is a major tool in Arithmetic combinatorics (see Tao and Vu's book, they have a chapter named L^p theory, i.e. the theorem of Bourgain's about "long APs in sumsets").

Moreover, one can show applications in Number Theory and Summability theory (those have combinatorial uses), for example, Hardy-Littlewood's proof of the Prime Number Theorem (based on their Tauberain theorem (or Landau's, they are essentialy the same for this perpose)).

If you want to dwelve into Ergodic Theory, there are a lot of uses (as one suggested here, Hillel's proof of Szemeradi's theorem, a generalization concerning forms in the plane (by Furstenberg-Katzenelson-Weiss), there are even previous works, in topological dynamics, of proving for example the van-der-warden theorem. And if one wants to go in other direction, Weil's equidistribution theorem, works of Dani and Margulis about the Oppenheim conjecture, and general work in the geometry of numbers by recent fields medalist Lindenstrauss), but covering all those subjects would require about 2 courses (Ergodic Theory and Homogenuous dynamics, prehepes even a course in topological dynamics).

If you want to go purely combinatorial, recently there had been a lot of interest in expanders (see the works of Bourgain and Varju (Princeton)). You can show for example Margulis' construction (altough it will require some Lie groups and Rep. theory).

In a totally other direction, you can speak of embedding into metric spaces (that stuff has some application in CS), for example, the Johnson-Lindenstrauss Lemma (this Lindenstrauss is the father of the fields medalist).

-
These applications are beautiful, but they are completely unsuitable for presenting to students learning about the Lebesgue theory for the first time. Almost every one of them is a good topic to spend a month on in an advanced graduate course. –  Victor Protsak Aug 29 '10 at 4:19
Thanks, I'll look into these. They do sound over my students' head at this point, but I'll drop them into conversation, and give references. –  Gordon Craig Sep 13 '10 at 18:59

Give Flajolet's book "Analytic Combinatorics" a shot. Although I'm still not sure how you would insert a generating function and a saddle-point analysis into your course ...

-
I'm not too sure either, but I'll check out the book. Thanks. –  Gordon Craig Sep 13 '10 at 19:15

Probability is a thread that can tie analysis and combinatorics together. In particular, Markov processes on various spaces enjoying some nice combinatorial properties have a good many applications (and can also introduce harmonic analysis representation theory of finite groups). A couple of books that look interesting in regard to these sorts of overlaps are here and here. It is likely that with a bit of browsing you can find better examples.

Another related area that may provide fertile ground is statistical physics, though this may require more background than you can afford to provide. On the other hand, the thermodynamic limit is a subtle analytic beast that requires a great deal of care and all the theory they could handle in such a course.

-
Thanks. That sounds out of our league, but it's something I can mention in passing to pique their interest. –  Gordon Craig Sep 13 '10 at 19:16

If you count additive number theory as combinatorics, there is Fürstenberg's measure theoretic proof of Szemerédi's theorem ("Any 'positive fraction' of the natural numbers contains arithmetic progressions of any length."). Presenting the proof is certainly not possible – that's the subject of an entirely different course – but you could do some small talk and prove Poincaré's recurrence theorem instead, which is a trivial special case of Szemerédi's theorem.

In that light, another, if elementary, measure theoretic fact is Minkowski's theorem about lattice points (vectors with integer coordinates) in convex subsets of $\mathbb{R}^n$. I vaguely remember that it can be used in the proof that every natural number is a sum of four squares (can it?), which could be labeled "combinatorics" with heavy squinting. Since this is about convex sets, there is some connection to norms and functional analysis, too ("Geometry of numbers").

-
Thanks! I'll look into that. –  Gordon Craig Sep 13 '10 at 19:06

Fourier analytic methods can sometimes be useful to proof combinatorical results. A celebrated result which uses fourier analysis on the boolean cube is the KKL (Kahn-Kalai-Linial) -Theorem about the influence of a variable in a Boolean function. Here are lecture notes which cover that subject.
As someone else already mentioned, metric embeddings are an interesting topic where analysis and combinatorics intersect. There is a good survey by Matousek on the subject.
Finally I would like to remark that a good method to gain the interest of combinatorialists is to give them interesting problems to think about. So a great analysis book for combinatorialists -although a bit too advanced for your course I guess- is Halmos "A Hilbert Space Problem Book"

-
Thanks for the references. I'll try to pick a topics out of there for one of their talks, although Halmos's book will be too advanced, as we won't be on to Hilbert spaces until at least the middle of term. –  Gordon Craig Sep 13 '10 at 19:01

This isn't exactly what you are looking for, but I highly recommend Using the Borsuk-Ulam theorem by Matousek. The Borsuk-Ulam theorem states that any continuous map $f:S^n \to \mathbb{R}^n$ must map some pair of antipodal points to the same point. Surprisingly, this theorem has many applications in combinatorics, including for example graph colouring.

-
That sounds nice. I'm not sure whether I'll be able to integrate it in my course, but if I can that would certainly interest the combinatorists. –  Gordon Craig Sep 13 '10 at 19:12

Here's a theorem of Weyl: Let $a_1,a_2,\dots$ be a sequence of distinct integers. Then the sequence $a_1x,a_2x,\dots$ is uniformly distributed modulo 1 for almost all real numbers $x$. The theory of uniform distribution of sequences, which you may or may not consider to be combinatorics, relies heavily on estimation of exponential sums, and thus on classical analysis.

-

There is a direct connection between Hall's marriage theorem (combinatorics) and Linear programming (linear inequalities). Of course, the latter is about finite dimensions, but prominently features duality and convexity, two important tools in functional analysis.

To elaborate on Hall's marriage theorem, consider the following picture:

The dots on the left represent men, the dots on the right represent women and the connecting lines indicate whether this man and woman like each other. The question is whether it is possible to arrange simultaneous, monogamous marriages such that everyone marries someone he or she likes. Hall's theorem gives a necessary and sufficient condition for that: for every subset $M$ of men, the set $$W = \lbrace w \text{ woman}\ |\ w \text{ likes } m, m\in M\rbrace$$ of women liked by these men must fulfill $|M| \le |W|$.

This problem is also known as perfect matching in a bipartite graph. It turns out that it is equivalent to a maximum flow problem, for which we have the min-cut max-flow theorem, which is equivalent to the duality theorem for linear programming. The details of this equivalence are not very difficult and can be found here: http://web.mit.edu/k_lai/www/6.046/r11-handout.pdf .

Unfortunately, I haven't found a ready-made proof of Hall's theorem from the duality theorem, you'd have to work that out yourself for your lecture. The intermediate reformulations are bit long, I don't think it's worth spending more than a cursory remark on them; I'd jump right to the reformulation as linear program.

-
There's a book by Reichmeider about Hall, max flow, Dilworth, and a few other equivalent or closely related topics. –  Gerry Myerson Aug 28 '10 at 13:57
Thanks, that sounds promising. I'll investigate Gerry's reference to see if I can make a connection with what we'll be doing. –  Gordon Craig Sep 13 '10 at 19:05
These notes present Menger's theorem in a functional-analytic sort of way: terrytao.wordpress.com/2007/11/30/… Menger's theorem is one of the closely related topics/theorems mentioned by Gerry. –  Brendan Murphy Dec 8 '13 at 1:04

Markov chains on symmetric groups converging to various distributions other than uniform provide a fertile ground for the marriage between modern combinatorics such as Macdonald polynomials and hard analysis using ratio test etc. For starters one could look at Diaconis and Shashahani's proof of cutoff convergence rate of random transposition walk. It involves looking at Schur polynomials which encode the eigenfunctions of the markov chain. If one looks at walks converging to so-called ewens sampling measure, or jack measure, then jack polynomials replace Schur polynomials as the relevant objects. Recent Diaconis and Ram have studied an auxilliary variable algorithm markov chain converging to a two parameter family of distributions on the symmetric group that use heavily the theory of Macdonald polynomials. This last one will probably be in print in a few months time.

-
Thanks. That sounds too advanced for my students, but I'll look into it. –  Gordon Craig Sep 13 '10 at 19:15

As warm-up exercises using Cauchy-Schwarz and Holder's inequality, you could mention restricted subgraph bounds and incidence bounds. When you rearrange these bounds to bound the number of "rich/popular" points or vertices you get (weak) $L^p$ bounds for the degree of each vertex (viewed a function on the vertex set). In this setting it's easy to see how interpolation works, and it gives you a feel for how $L^p$ spaces work in a probability setting (i.e. on a compact domain).

Here's a reference for the restricted subgraph bounds: http://murphmath.wordpress.com/2012/06/19/restricted-subgraph-bounds/. Instead of the convexity of ${x\choose s}$ in $x$, you can use Holder's inequality. The bounds can be rearranged using Chebyshev's inequality to state that (in the notation of that blog post):

$$|\{b\in B\colon \mathrm{deg}(b)\geq t\}|\leq C \frac{|A|^s}{t^s}$$

where $C$ is a constant depending on $s$ and $t$. Then using the "layer-cake" theorem (which is a nice exercise using Fubini's theorem!) you get that

$$||\mathrm{deg}(b)||_{L^s(B)}^s \leq C'|A|^s\log|A|.$$

I know this is pretty trivial, but this is actually what's at stake in the Kakeya maximal conjecture. Here one has a collection of tubes $T_1,\ldots,T_n$ and the goal is to prove $L^p$ bounds for the function

$$f(x)=\sum_{i=1}^n \chi_{T_i}(x),$$

where $\chi_{T_i}$ is the indicator function on the tube $T_i$. Thus we are seeking $L^p$ bounds for the function that counts how many tubes are incident to to a point $x$! The proof of the two dimensional Kakeya conjecture is essentially the same as the proof restricted subgraph bound for $s=2$ in that blog post---the incidence graph for points and lines in a plane contains no $K_{2,2}$'s, and modulo some technicalities in the Kakeya case, the main tool is Cauchy-Schwarz. In fact, Wolff's paper on the Kakeya problem contains a finite field analog where the proof is exactly by Cauchy-Schwarz.

-