Applications of Measure, Integration and Banach Spaces to Combinatorics - MathOverflow

Applications of Measure, Integration and Banach Spaces to Combinatorics

2010-08-27T00:30:12Z

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.

Answer by Gerry Myerson for Applications of Measure, Integration and Banach Spaces to Combinatorics

2010-08-27T00:42:51Z

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.

Answer by Steve Huntsman for Applications of Measure, Integration and Banach Spaces to Combinatorics

2010-08-27T00:59:24Z

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.

Answer by anonnn for Applications of Measure, Integration and Banach Spaces to Combinatorics

2010-08-27T03:39:18Z

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 ...

Answer by John Jiang for Applications of Measure, Integration and Banach Spaces to Combinatorics

2010-08-27T05:24:00Z

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.

Answer by Pietro Majer for Applications of Measure, Integration and Banach Spaces to Combinatorics

2010-08-27T06:44:05Z

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.

Answer by Greg Graviton for Applications of Measure, Integration and Banach Spaces to Combinatorics

2010-08-27T20:39:10Z

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").

Answer by Tony Huynh for Applications of Measure, Integration and Banach Spaces to Combinatorics

2010-08-28T11:04:46Z

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.

Answer by Greg Graviton for Applications of Measure, Integration and Banach Spaces to Combinatorics

2010-08-28T11:12:36Z

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.

Answer by Paolo Ketter-Umbanza for Applications of Measure, Integration and Banach Spaces to Combinatorics

2010-08-28T12:18:39Z

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"

Answer by Asaf for Applications of Measure, Integration and Banach Spaces to Combinatorics

2010-08-28T22:28:52Z

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).