## Archive for the ‘Combinatorics’ Category

### Interview with László Lovász

May 11, 2013

On November 28, 2011, Avi Wigderson interviewed László Lovász. A total of 27 short videos can be watched at the Simons Foundation website. I particularly liked the discussion on the LLL algorithm, and also on semidefinite relaxations.

__________

Related:

### Combinatorial Explosion

September 16, 2012

An amusing Japanese cartoon on combinatorial explosion:

Tastefully done, I would say. The target audience consists not of this blog’s readers, but rather of their children.

Hat tip: Michael Lugo

### Playing with Permutations

July 24, 2008

Let’s play a game:

You build an ordered list $y = (y_1, y_2, \ldots, y_n)$ of $n$ real numbers, and you conceal it from me. You then compute $c_k = \sum_{i=1}^n y_i^k$ for each $k \in \{1,2,\ldots,n\}$, and you give me the $n$-tuple $c = (c_1, c_2, \ldots, c_n)$. Finally, I build a list $x = (x_1, x_2, \ldots, x_n)$ of $n$ real numbers such that $\sum_{i=1}^n x_i^k = c_k$ for all $k \in \{1,2,\ldots,n\}$. Can I conclude that my list is a permutation of yours (or equal to it)?

__________

Each ordered list of $n$ elements is an $n$-tuple. We can also think of an ordered list of $n$ reals as a vector in $\mathbb{R}^n$, where the list’s $i$-th element is the vector’s $i$-th entry.

The following 3-stage diagram hopefully clarifies the essence of this $2$-player game:

where I am player #1, and you’re player #2. The game’s three stages are:

1. player #2 builds an ordered list $y \in \mathbb{R}^n$, but player #1 doesn’t have access to it.
2. player #2 gives player #1 the $n$ “measurements” $c = (c_1, c_2, \ldots, c_n)$, where $c_k = \sum_{i=1}^n y_i^k$.
3. player #1 builds ordered list $x \in \mathbb{R}^n$ from $c = (c_1, c_2, \ldots, c_n)$ such that $\sum_{i=1}^n x_i^k = c_k$ for all $k \in \{1,2,\ldots,n\}$.

We know that it’s always possible to build list $x$, because if $x$ is equal to $y$ or a permutation of $y$, then all $n$ equality conditions

$\begin{array}{rl} \displaystyle\sum_{i=1}^n x_i &= c_1\\ \displaystyle\sum_{i=1}^n x_i^2 &= c_2\\ \vdots\\ \displaystyle\sum_{i=1}^n x_i^n &= c_n\\\end{array}$

will be satisfied. What we don’t know is whether any list $x$ that satisfies the equality conditions will be a permutation of $y$. In more rigorous terms: if $x, y$ are permutations of one another, then it is necessary that the $n$ equalities hold. What we would like to know is whether the fact that the $n$ equalities hold is sufficient for us to conclude that $x, y$ are permutation of one another.

But how can player #1 build the desired ordered list? A possibility would be for player #1 to solve the following system on polynomial equations in variables $x_1, x_2, \ldots, x_n$

$\begin{array}{rl} x_1 + x_2 + \ldots + x_n &= c_1\\ x_1^2 + x_2^2 + \ldots + x_n^2 &= c_2\\ \vdots\\ x_1^n + x_2^n + \ldots + x_n^n &= c_n\\\end{array}$

where $c$ is a contant, and $x$ is a variable.

The game I propose on this post stems from two closely related problems I have been thinking of since January 2008. I have written a few posts on these problems already:

January 18, 2008

Consider a set $S$ with $|S|=n$ elements (where all elements of $S$ are distinct). We can build ordered lists of $n$ elements by taking elements from set $S$ and using them (with no repetition) to build $n$-tuples. With $n$ elements we can build $n!$ distinct $n$-tuples.

Let us think in terms of vectors in $\mathbb{R}^n$, where each vector represents a particular ordered list of the elements of some set with $n$ elements. If $x, y \in \mathbb{R}^n$ are permutations of one another, then they contain the same elements, but in a different order; consequently, for every $p \in \mathbb{N}$ we have

$\displaystyle\sum_{i=1}^n x_i^p = \displaystyle\sum_{i=1}^n y_i^p$.

Let $I: \mathbb{R}^n \times \mathbb{R}^n \rightarrow \{0,1\}$ be an indicator function, such that $I(x,y) = 1$ if and only if $x,y$ are permutations of one another ($I(x,y)=0$ otherwise). Let $g_p: \mathbb{R}^n \rightarrow \mathbb{R}$ be defined as

$g_p(z) = \displaystyle\sum_{i=1}^n z_i^p$,

for all $p \in \mathbb{N}$. We can then conclude that

$I(x,y) = 1 \Rightarrow g_p(x) = g_p(y), \quad{} \forall p \in \mathbb{N}$.

The condition $g_p(x) = g_p(y), \quad{} \forall p \in \mathbb{N}$ is necessary. Is it sufficient?! In other words, if $g_p(x) = g_p(y), \quad{} \forall p \in \mathbb{N}$ is true, can we conclude that vectors $x,y$ are permutations of one another?

This is an interesting problem. Think about it!

Update (Jan. 25, 2008): this post was featured on the 25th edition (Silver Jubilee) of the Carnival of Mathematics.

### Today’s Putnam problem – Dec. 01, 2007

December 1, 2007

From Harvard’s Math Department webpage, here’s today’s Putnam problem:

Take $r$ such that $1 \leq r \leq n$, and consider all subsets of $r$ elements of the set $\{1, 2, \ldots, n\}$. Each subset has a smallest element. Let $F(n,r)$ be the arithmetic mean of these smallest elements. Prove that $F(n,r) = \frac{n+1}{r+1}$.

For starters, note that there are

$m = \displaystyle\binom{n}{r} = \frac{n!}{(n-r)! r!}$

different subsets of $r$ elements of the set $\{1, 2, \ldots, n\}$; let’s denote these subsets by $S_i$, where $i \in \{1, 2, \ldots, m\}$ and $|S_i| = r$. If the minimum element of subset $S_i$ is given by $\min(S_i)$, we then have

$F(n,r) = \displaystyle\frac{1}{m} \sum_{i=1}^m \min(S_i)$.

This is all very nice, but computing $\min(S_i)$ is not that straightforward. The best way to make sure that one understands the problem at hand is to consider an example, and that’s what I will do now.

Example: $n=4$ and $r=2$

In this case, we have

$m = \displaystyle\binom{4}{2} = \frac{4!}{2! 2!} = 6$

different subsets of the set $\{1, 2, 3, 4\}$. Since $m=6$ is quite small, we can quickly and easily find all the different subsets:

$S_1 = \{1, 2\}$

$S_2 = \{1, 3\}$

$S_3 = \{1, 4\}$

$S_4 = \{2, 3\}$

$S_5 = \{2, 4\}$

$S_6 = \{3, 4\}$

and the smallest element of each subset:

$\min(S_1) = 1$

$\min(S_2) = 1$

$\min(S_3) = 1$

$\min(S_4) = 2$

$\min(S_5) = 2$

$\min(S_6) = 3$.

And finally we have

$F(4,2) = \displaystyle\frac{\left(1 +1 +1 + 2 +2 + 3\right)}{6} = \displaystyle\frac{10}{6} = \displaystyle\frac{5}{3}$.

Note that $F(4,2) = \displaystyle\frac{4+1}{2+1}$.

My Solution:

Let’s start by considering two extreme examples of subsets of $\{1, 2, \ldots, n\}$

$S_1 = \{1, 2, \ldots, r\}$

$S_m = \{n, n-1, \ldots, n - (r-1)\}$,

where $|S_1| = |S_m| = r$. The smallest element of each of these subsets is given by

$\min(S_1) = 1$

$\min(S_m) = n - (r-1) = n - r + 1$

and therefore we have $1 \leq \min(S_i) \leq n -r + 1$ for every $i \in \{1, 2, \ldots, m\}$. While there’s only one subset of $\{1, 2, \ldots, n\}$ whose smallest element is $n - r + 1$, there is more than one subset whose smallest element is $1$. If one can compute the number of subsets whose smallest element is $k \in \{1, 2, \ldots, n - r + 1\}$, then one has solved the problem.

Let’s now consider all subsets (of $r$ elements of set $\{1, 2, \ldots, n\}$) whose smallest elements are $1$. How many are them? If the smallest element of each of these sets is $1$, then the remaining $r-1$ elements of the subset must be elements of set $\{2, 3, \ldots, n\}$, whose cardinality is $n-1$, and therefore we have

$\displaystyle \binom{n-1}{r-1}$

such subsets. If we consider all subsets whose smallest elements are $k$ (where $k \in \{1, 2, \ldots, n-r+1\}$), then the remaning $r-1$ elements of these subsets must be elements of set $\{k+1, k+2, \ldots, n\}$, whose cardinality is $n-k$. Therefore, there are

$\displaystyle \binom{n-k}{r-1}$

subsets whose smallest elements are $k$. Note that if $k = n-r+1$, we have

$\displaystyle \binom{n-(n-r+1)}{r-1} = \binom{r-1}{r-1} = 1$

subset only, as I had mentioned above. Since we now know how many subsets with a specific smallest element there are, we can compute $F(n, r)$ by taking the weighted average

$\displaystyle F(n, r) = \frac{\displaystyle\sum_{k=1}^{n-r+1} k \binom{n-k}{r-1}}{\displaystyle\sum_{k=1}^{n-r+1} \binom{n-k}{r-1}}$.

The denominator should me equal to $m = \binom{n}{r}$, and I have proved that already (I am not going to type the proof here because it’s a bit cumbersome). However, I can’t do much with the numerator. I am stuck. If you have any ideas, let me know.