Uniformly at Random

Posts Tagged ‘combinatorics

Borges’ Theorem

leave a comment »

No doubt one of the most delightful parts of writing a book of mathematics is the search for clever literary quotations to place at the beginning of chapters or to scatter throughout the book as appropriate (perhaps also, in the eyes of some, one of the greatest wastes of time).  Flajolet and Sedgewick, in Analytic Combinatorics, make reference to the following result, which they call “Borges’ Theorem”, namely that given any finite set P of words, a random text of length n will contain every word of P with probability tending to 1 exponentially fast as n tends to infinity.  The reason for the appellation “Borges’ Theorem” is due to Borges’ story The Library of Babel, which describes a library that contains

Everything: the minutely detailed history of the future, the archangels’ autobiographies, the faithful catalogues of the Library, thousands and thousands of false catalogues, the demonstration of the fallacy of those catalogues, the demonstration of the fallacy of the true catalogue, the Gnostic gospel of Basilides, the commentary on that gospel, the commentary on the commentary on that gospel, the true story of your death, the translation of every book in all languages, the interpolations of every book in all books.

Written by uncudh

August 15, 2009 at 1:57 pm

The necklace splitting problem

leave a comment »

The necklace splitting problem may be formulated (somewhat fancifully) as follows.

Suppose that two thieves have stolen a necklace.  The necklace is open at the clasp and consists of some number of jewels of k different types.  There are an even number of jewels of each type.  The thieves wish to cut the necklace into as few pieces as possible and share the pieces between the two of them so that each thief has a fair share of each type of jewel.  What is the minimum number of cuts that suffices?

Alon and West (Proc. Amer. Math. Soc. 98 (1986) 623-628) showed that k cuts always suffices for a fair division of the necklace, regardless of the total number of jewels.  Remarkably, the (very short!) proof of this combinatorial result uses a result from topology, namely the Borsuk-Ulam theorem.

Written by uncudh

June 9, 2009 at 3:04 pm

Posted in math

Tagged with

Hoffman’s eigenvalue bound on the size of an independent set

with 2 comments

We present here Hoffman’s eigenvalue bound on the size of an independent set in a regular graph. We follow the presentation of Ellis, Friedgut, and Pilpel. Recall that a graph is d-regular if every vertex has degree d.

Theorem. Let G = (V,E) be a d-regular graph with adjacency matrix A. Let d = \lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n = \lambda_{\min} be the eigenvalues of A. Let I be an independent set in G. Then

|I|/|V| \leq -\lambda_{\min}/(\lambda_1 - \lambda_{\min}).

Proof. Let us suppose that V = \{1,2,\ldots,n\}. Let \langle\cdot,\cdot\rangle be the inner product on \mathbb{R}^n defined by \langle x,y \rangle = (1/n)(x \cdot y), where the \cdot denotes the usual dot product. Let \|x\| = \sqrt{\langle x,x \rangle} be the corresponding norm on \mathbb{R}^n.

The adjacency matrix A is a real symmetric matrix, so we may suppose that the eigenvectors v_1,v_2,\ldots,v_n (corresponding to the eigenvalues \lambda_1,\lambda_2,\ldots,\lambda_n) form an orthonormal basis of \mathbb{R}^n with respect to the inner product \langle\cdot,\cdot\rangle. Note that since G is d-regular, v_1 is the vector with all entries equal to 1. Let u be the characteristic vector of the independent set I and define \alpha = |I|/|V|.

Observe that u^TAu counts the number of edges among the vertices of I. Since I is an independent set, we have u^TAu = 0. We write u as a linear combination of the eigenvectors; i.e.,

u = a_1v_1 + a_2v_2 + \cdots + a_nv_n.

Since the v_i‘s form an orthonormal set, we have \alpha = \langle u,v_1 \rangle = a_1. By Parseval’s identity we also have

a_1^2 + a_2^2 + \cdots + a_n^2 = \|u\|^2 = \langle u,u \rangle = \alpha.

We therefore have

0 = u^TAu = \sum_{i=1}^n a_i^2 \lambda_i \geq a_1^2\lambda_1 + \sum_{i=2}^n a_i^2\lambda_{\min} = \alpha^2\lambda_1 + (\alpha - \alpha^2)\lambda_{\min}.

Thus,

\alpha\lambda_1 + (1 - \alpha) \lambda_{\min} \leq 0,

whence we obtain

\alpha = |I|/|V| \leq -\lambda_{\min}/(\lambda_1 - \lambda_{\min}),

as required.

Written by uncudh

March 21, 2009 at 5:02 pm

Posted in math

Tagged with ,

The number of ways of shuffling a cabinet

leave a comment »

No doubt the first question on the mind of anyone reading the previous post concerning John A. Macdonald’s double shuffle is, “In how many ways could Macdonald have appointed his former cabinet members to new ministries so that no minister was appointed to the same position that he had held in the previous Macdonald government?”

Letting n denote the number of ministers in Macdonald’s cabinet, the answer to this question is d(n), the number of derangements of an n-element set. A derangement is a permutation such that no element is mapped to itself. The number of derangements of an n-element set is well-known to be d(n) = n! \sum_{i=0}^n (-1)^i/i!, which turns out to be simply the nearest integer to n!/e.

I am too lazy to bother writing a proof of this formula here, so instead I refer the reader to, for example, the book Concrete Mathematics by Graham, Knuth and Patashnik.

Written by uncudh

February 27, 2009 at 4:44 pm

Posted in math

Tagged with ,

The Fine-Wilf Theorem

leave a comment »

The Fine-Wilf Theorem is as follows. Supppose (a_n)_{n \geq 0} and (b_n)_{n \geq 0} are two infinite periodic sequences with periods p and q respectively. If (a_n)_{n \geq 0} and (b_n)_{n \geq 0} agree on their first p+q-\gcd(p,q) terms then the two sequences are identical.

We present here the elegant algebraic proof given as the solution to Problem 134 in Bollobas’ book The Art of Mathematics and attributed by Bollobas to Ernst Straus.

We first define formal power series F(X) = \sum_{n \geq 0} a_n X^n and G(X) = \sum_{n \geq 0} b_n X^n. By the periodicity hypothesis, we have F(X) = P(X)/(1-X^p) and G(X) = Q(X)/(1-X^q) for some polynomials P,Q of maximum degrees p-1 and q-1 respectively. However, since (1-X^{\gcd(p,q)}) divides each of (1-X^p) and (1-X^q), we also have

F(X) - G(X) = [(1-X^q)P(X) - (1-X^p)Q(X)](1-X^p)^{-1}(1-X^q)^{-1} = (1-X^{\gcd(p,q)})R(X)(1-X^p)^{-1}(1-X^q)^{-1}

where R(X) is some polynomial of degree at most p+q-\gcd(p,q)-1. If the first p+q-\gcd(p,q) coefficients of F and G coincide, then the first p+q-\gcd(p,q) coefficients of F(X) - G(X) are zero, whence the polynomial R is the zero polynomial. It follows that F(X) - G(X) is identically zero, so that F and G and hence (a_n)_{n \geq 0} and (b_n)_{n \geq 0} are identical, as claimed.

We should point out that several other results that we have discussed in previous posts appear as problems in the previously mentioned book by Bollobas.

Written by uncudh

February 19, 2009 at 5:56 pm

Posted in math

Tagged with

Enumerating permutations by number of inversions

with 2 comments

We have previously given a proof of the identity

\prod_{i \geq 1}(1-q^i) = \sum_{n=-\infty}^\infty (-1)^n q^{(3n^2+n)/2},

which is Euler’s Pentagonal Number Theorem. We now describe how to apply this formula to derive a formula for the number of permutations of n elements with k inversions. Let p = p_1p_2 \cdots p_n be a permutation of 1,2,\ldots,n, written in the so-called “one line” notation. An inversion of p is a pair (p_i,p_j) such that i<j and p_i>p_j. Let i(p) denote the number of inversions of p. Then we claim that the generating function I_n of i(p) is

I_n(q) = \sum_{p \in S_n} q^{i(p)} = (1+q)(1+q+q^2)\cdots(1+q+\cdots+q^{n-1}) = \prod_{i=1}^n\frac{1-q^i}{1-q}.

We prove this by induction on n. For n=2, we have one permutation with no inversions and one with one inversion, whence we obtain the generating function I_2(q) = 1+q, as claimed.

Suppose the claim holds for n-1 and let p be a permutation of 1,2,\ldots,n-1. We create a new permutation q by inserting n into p. If we insert n after all elements of p we have created no new inversions; if we insert n after all but one element of p we have created one new inversion; and in general, if we insert n after all but i elements of p we create i new inversions. Thus the number of permutations so created is enumerated by the generating function

I_{n-1}(q)\cdot(1+q+\cdots+q^{n-1}) = (1+q)(1+q+q^2)\cdots(1+q+\cdots+q^{n-1}),

as claimed. This completes the proof.

Let b(n,k) denote the coefficient of q^k in I_n(q); i.e., b(n,k) is the number of permutations of n elements with k inversions. We wish to deduce a formula for b(n,k). Since b(n,k) is the coefficient of q^k in \prod_{i=1}^n\frac{1-q^i}{1-q} = (1-q)^{-n}\prod_{i=1}^n (1-q^i), it must also equal the coefficient of q^k in the infinite product (1-q)^{-n}\prod_{i \geq 1}(1-q^i). By Euler’s Pentagonal Number Theorem, we have

(1-q)^{-n}\prod_{i \geq 1}(1-q^i) = (1-q)^{-n}\sum_{j=-\infty}^\infty (-1)^j q^{(3j^2+j)/2}.

Thus, b(n,k) is the coefficient of q^k in (1-q)^{-n}\sum_{j=-\infty}^\infty (-1)^j q^{(3j^2+j)/2}. By the binomial theorem, we have

(1-q)^{-n} = \sum_{h \geq 0} {n+h-1 \choose h}q^h

(recall that {-n \choose h} = (-1)^h {n+h-1 \choose h}). Thus, letting d_j = (3j^2+j)/2 denote the pentagonal numbers, we obtain a term q^k in (1-q)^{-n}\sum_{j=-\infty}^\infty (-1)^j q^{d_j} by multiplying a term q^{k-d_j} from (1-q)^{-n} by a term q^{d_j} from \sum_{j=-\infty}^\infty (-1)^j q^{d_j}. The coefficient of q^{k-d_j} in (1-q)^{-n} is {n+k-d_j-1 \choose k-d_j}, and the coefficient of q^{d_j} in \sum_{j=-\infty}^\infty (-1)^j q^{d_j} is (-1)^j. Thus, the coefficient b(n,k) of q^k is given by

b(n,k) = \sum_j (-1)^j {n+k-d_j-1 \choose k-d_j},

where the sum is over all j for which d_j \leq k. This is the desired formula for the number of permutations of n elements with k inversions.

Written by uncudh

February 17, 2009 at 2:48 am

Posted in math

Tagged with , ,

Another intersecting families result

leave a comment »

We have previously discussed the following result of Kleitman concerning intersecting families of sets: if {\cal A,B} are monotone decreasing families of subsets of \{1,\ldots,n\}, then {\cal |A||B|} \leq 2^n {\cal |A \cap B|}. Suppose that instead of the hypothesis that {\cal A,B} are monotone decreasing, we instead have that |A \cap B| is even for every A\in{\cal A}, B\in{\cal B}. In this case we have the following result of Ahlswede, El Gamal, and Pang (1984).

Theorem. If {\cal A,B} are families of subsets of \{1,\ldots,n\} such that |A \cap B| is even for every A\in{\cal A}, B\in{\cal B}, then {\cal |A||B|} \leq 2^n.

Proof. Let U and V be the vector spaces over GF(2) generated by the sets of characteristic vectors of the sets in {\cal A} and {\cal B} respectively. The assumption that |A \cap B| is even for every A\in{\cal A}, B\in{\cal B} means that the inner product \langle u,v \rangle is 0 over GF(2) for every u \in U, v \in V. In other words V is contained in the orthogonal complement U^\perp of U. Since \dim U + \dim U^\perp = n, we have |{\cal A}||{\cal B}| \leq |U||V| \leq 2^{\dim U + \dim U^\perp} = 2^n, as required.

Written by uncudh

February 12, 2009 at 4:50 am

Posted in math

Tagged with ,