Interview with László Lovász

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:

• The social construction of Hungarian genius

Combinatorial Explosion

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

Let’s play a game:

You build an ordered list of real numbers, and you conceal it from me. You then compute for each , and you give me the -tuple . Finally, I build a list of real numbers such that for all . Can I conclude that my list is a permutation of yours (or equal to it)?

__________

Each ordered list of elements is an -tuple. We can also think of an ordered list of reals as a vector in , where the list’s -th element is the vector’s -th entry.

The following 3-stage diagram hopefully clarifies the essence of this -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 , but player #1 doesn’t have access to it.
2. player #2 gives player #1 the “measurements” , where .
3. player #1 builds ordered list from such that for all .

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

will be satisfied. What we don’t know is whether any list that satisfies the equality conditions will be a permutation of . In more rigorous terms: if are permutations of one another, then it is necessary that the equalities hold. What we would like to know is whether the fact that the equalities hold is sufficient for us to conclude that 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

where is a contant, and 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:

• Thinking about permutations

• My Conjecture

Thinking about permutations

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

Let us think in terms of vectors in , where each vector represents a particular ordered list of the elements of some set with elements. If are permutations of one another, then they contain the same elements, but in a different order; consequently, for every we have

.

Let be an indicator function, such that if and only if are permutations of one another ( otherwise). Let be defined as

,

for all . We can then conclude that

.

The condition is necessary. Is it sufficient?! In other words, if is true, can we conclude that vectors 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

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

Take such that , and consider all subsets of elements of the set . Each subset has a smallest element. Let be the arithmetic mean of these smallest elements. Prove that .

For starters, note that there are

different subsets of elements of the set ; let’s denote these subsets by , where and . If the minimum element of subset is given by , we then have

.

This is all very nice, but computing 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: and

In this case, we have

different subsets of the set . Since is quite small, we can quickly and easily find all the different subsets:

and the smallest element of each subset:

.

And finally we have

.

Note that .

My Solution:

Let’s start by considering two extreme examples of subsets of

,

where . The smallest element of each of these subsets is given by

and therefore we have for every . While there’s only one subset of whose smallest element is , there is more than one subset whose smallest element is . If one can compute the number of subsets whose smallest element is , then one has solved the problem.

Let’s now consider all subsets (of elements of set ) whose smallest elements are . How many are them? If the smallest element of each of these sets is , then the remaining elements of the subset must be elements of set , whose cardinality is , and therefore we have

such subsets. If we consider all subsets whose smallest elements are (where ), then the remaning elements of these subsets must be elements of set , whose cardinality is . Therefore, there are

subsets whose smallest elements are . Note that if , we have

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

.

The denominator should me equal to , 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.