A Portion of the Book

April 8, 2009

Integrals, Combinatorics, and Geometry

Filed under: Combinatorics — by Masoud Zargar @ 9:27 am

Clearly, integrals are of profound importance and interest to most, if not all, mathematicians. A topic that is rarely incorporated into the required mathematics courses, let it be at the undergraduate or graduate level, is the applications of integrals to combinatorics, especially those combinatorial questions that do not have an algebraic flavour.

In this article, several interesting and useful ideas concerning geometric combinatorics and combinatorial identities will be introduced. The geometric combinatorics discussion will primarily deal with a very powerful technique that uses integrals of characteristic functions. Here, we will deal with Lebesgue integrals, and so \int_{C}1 is simply the planar measure of measurable C; our sets C will be sufficiently nice, and so if you are unaware of the terminology used in Lebesgue integration, you can think of \int_C1 as the area of C. As I strongly believe that mathematics should be taught via examples and problems, as in An Important Equivalence Relation the ideas will be introduced by discussing several problems. Initially, a technical solution will be given to a combinatorial geometry problem that has a simple elementary solution; however, the power of the method will be demonstrated by claiming that a more general relation holds that could be nontrvial depending on the parameters.  The story will certainly not end here!  A solution will be given to a combinatorial (geometry) problem using trigonometric functions, followed by the solution to a combinatorial identity by rewriting the terms under consideration in terms of integrals. Digressing, integrals will be used to show the power of averagin using integral (even in combiantorial problems with a geometric flavour).  This entry will then end with a discussion of a beautiful solution to Putnam 2005 B6. Following this plan, consider the following problem in extremal combinatorial geometry:

  • Suppose that you have nine planar surfaces S_1,\hdots,S_9 each of area 1, whose union is a surface of a surface of area 5.  Prove that there are i\neq j such that S_i\cap S_j has area at least \frac{1}{9}.

You can give a short proof to this by assuming the contrary (why?), but that is a different story that may be pursued in the near future.  For the purpose of making sure that we are all on the same page,  given a set S\subseteq T, the characteristic function \chi_S:T\rightarrow\{0,1\} of S in T is defined as

\chi_S(x) =\begin{cases}0, x\notin S;\\ 1, x\in S.\end{cases}

Now, here is the solution to the above problem:

Solution.Consider the function f:S=\cup_iS_i\rightarrow\mathbb{Z} given by f=\sum_i\chi_{S_i}.  Then f takes integer values, so (f-1)(f-2)\geq 0.  Therefore,

0 \leq\int_Sf^2-3\int_Sf+\int_S2= -2\sum_i\int_S\chi_{S_i}+2\sum_{i<j}\int_S\chi_{S_i\cap S_j}+10

Because \int_S\chi_{S_i}=\int_{S_i}1=1 \forall i\in[9], we have \sum_{i<j}\int_{S}\chi_{S_i\cap S_j}\geq 4.  The left hand side has \binom{9}{2}=36 summands, and so there must be i\neq j such that\int_{S_i\cap S_j}1=\int_S\chi_{S_i\cap S_j}\geq\frac{1}{9}; otherwise, the left hand side is less than \frac{1}{9}\binom{9}{2}=4. \Box

Hoping that the above example has demonstrated the method, consider the following generalized version of the above problem:

  • If |X| denotes the area of X, then \left|\bigcup_iS_i\right|\geq \sum_i|S_i|-\sum_{i<j}|S_i\cap S_j|, where S_i are as above.  (This is, in fact, a special case of the principle of inclusion exclusion. Changing the initial values would lead to more complicated results.)

Let’s focus on a different part of combinatorial geometry. The following problem has many solutions, one of which is a simple application of the heuristic “proofs by coloring.”

  • Suppose that you take a rectangle R with adjacent sides parallel to the axes in the plane.  Then tile R with disjoint rectangles (with side parallel to the axes) R_1,\hdots, R_n each of which has a side of integral length.  Prove that R has a side of integral length.

Solution. Let f(x,y)=\sin 2\pi x\sin 2\pi y.  Then, \int_{R_i}f=0 because R_i has at least one integral side.  Suppose, without loss of generality that R is [0,a]\times[0,b].  Then \int_Rf=\sum_i\int_{R_i}f=0.  But an evaluation of the integral gives that

0=\int_Rf=\int_0^a\int_0^bf(x,y)dydx=\frac{1}{4\pi^2}(1-\cos 2\pi a)(1-\cos 2\pi b)

and so a or b is an integer, as required. \Box

This solution is certainly ingenious and difficult to deduce.   There are certain integral substitutions that are very useful when solving inequalities and proving identities.

Take m,n\in\mathbb{N} and notice that via a substitution x\rightarrow 1-x, we have \int_0^1x^m(1-x)^ndx=\int_0^1x^n(1-x)^mdx.  Many would stop here and not delve deeper into the implications of this identity.  Notice that by the Binomial Theorem, (1-x)^m=\sum_{k\geq 0}\binom{m}{k}(-1)^kx^k and (1-x)^n=\sum_{k\geq 0}\binom{n}{k}(-1)^kx^k.  So

\sum_{k\geq o}(-1)^k\binom{m}{k}\int_0^1x^{k+n}dx=\sum_{k\geq 0}(-1)^k\binom{n}{k}\int_o^1x^{m+k}dx\\ \iff \sum_{k\geq o}\frac{(-1)^k\binom{m}{k}}{n+k+1}=\sum_{k\geq 0}\frac{(-1)^k\binom{n}{k}}{m+k+1}.

Let us look at another Olympiad problem (Columbian TST 2004) having a geometric flavour:

  • Suppose that you have a finite number of line segments in \mathbb{R}^2 with sum of lengths at most 1.  Then prove that there is a line \ell such that the sum of the lengths of projections of the line segments is at most \frac{2}{\pi}.

Solution.One way to approach this problem is to fix coordinate axes for \mathbb{R}^2 and take the average of the sum of lengths of all projections over all possible directions of lines.  Then we must have a line with sum of lengths of projections at most the average.

Let \ell_i be the lengths of the lines and \theta_i suitable real numbers that make the x+\theta_i the angles between the lines \ell_i and the varying line.  Then the average is \frac{1}{2\pi}\int_0^{2\pi}\sum_i\ell_i|\cos(s+\theta_i)|ds=\frac{4\sum_i\ell_i}{2\pi}\leq \frac{2}{\pi}, as required. \Box

Last, but not least, we discuss a solution of Putnam 2005 B6:

  • Let S_n denote the set of all permutations of the numbers 1,2,\dots,n. For \pi\in S_n, let \sigma(\pi) be the sign of \pi\in S_n.   Also, let v(\pi) denote the number of fixed points of \pi. Show that \sum_{\pi\in S_n}\frac {\sigma(\pi)}{v(\pi) + 1} = ( - 1)^{n + 1}\frac {n}{n + 1}.

Solution (Major Steps).

  1. There was a substritution that was cucial in proving the above combinatorial identity: \frac{1}{1+k}=\int_0^1x^kdx, k\in\mathbb{N}.  Using this, we have \frac{1}{1+v(\pi)}=\int_0^1x^{v(\pi)}dx.  So we have \sum_{\pi\in S_n}\frac {\sigma(\pi)}{v(\pi) + 1} = \int_0^1\sum_{\pi\in S_n}\sigma(\pi)x^{v(\pi)}dx.
  2. \det(a_{ij})=\sum_{\pi\in S_n}\sigma(\pi)a_{1\pi(1)}\hdots a_{n\pi(n)} for (a_{ij})\in\mathcal{M}_n(\mathbb{F}), \mathbb{F} a field.  Notice that \det(J+(x-1)I)=\sum_{\pi\in S_n}\sigma(\pi)x^{v(\pi)}, where J is tha matrix with all entries equal to 1.
  3. Evaluate \det(J+(x-1)I) by subtracting the first row from all other rows.  The conclusion then follows after a straightforward integration.

Summarizing, we see that integration can have multiply applications in proving combinatorial identities, proving inequalities via an integral substitution, summing over all values of a desired set to obtain an average, or introducing trigonometric functions to solve combinatorial problems.  The possibilities go way beyond this very short list!

Possibly related posts: (automatically generated)

1 Comment »

  1. [...] Usually, undergrads hardly think integrals have much to do with combinatorics. At A Portion of the Book, Masoud Zargar has a very nice post that deals with the intersection of Integrals, Combinatorics and Geometry. [...]

    Pingback by The 54th Carnival of Mathematics « Todd and Vishal’s blog — July 4, 2009 @ 8:16 pm |Reply


RSS feed for comments on this post. TrackBack URI

Leave a comment

Powered by WordPress.com