## Combinatorics, Mathematics, Academics, Polemics, …

My name is Gil Kalai and I am a mathematician working mainly in the field of Combinatorics.  Within combinatorics, I work mainly on geometric combinatorics and the study of convex polytopes and related objects, and on the analysis of Boolean functions and related matters. I am a professor at the Institute of Mathematics at the Hebrew University of Jerusalem and also have a  long-term visiting position at the departments of Computer Science and Mathematics at Yale University, New Haven.

Gosset polytope- a hand drawing by Peter McMullen of the plane projection of the 8-dimensional 4-simplicial 4-simple Gosset polytope.

The Shlegel diagram (a certain 3-d projection) of the 120-cell –  a regular 4-dimensional polytope with 120 dodecahedral facets.

### 2. Getting started:

I have decided to follow the (separate) suggestions of Terry Tao, Noam Nisan and Oded Schramm (followed by a final push by Avi Wigderson) and set up a blog; I plan to do it for about a year.  It will be centered around combinatorics which is my main area of research and will touch on other matters.

Tao, Schramm and Nisan

Wigderson (left)

### 3. A problem: Frankl’s Conjecture

Let me tell you about a problem in extremal combinatorics that I like: I will probably return to the context later. But meanwile have a look:

## Frankl’s conjecture

Let $\cal F$ be a finite family of finite sets which is closed under union. In other words,  if $S,T \in {\cal F}$ then also $S \cup T \in {\cal F}$.

There exists an element $x$ which belongs to at least half the sets in $\cal F$.

Peter Frankl

(Sept 09: Frankl’s conjecture was proposed, among other problems, for a “polymath project.”)

### 4. Earlier blog experience:

I became acquainted with blogs quite recently; Greg Kuperberg told me about Dave Bacon’s blog “The Quantum Pontiff“. Then I asked my children if they knew what blogs were, and they looked at me (again) like I said something very silly;  It turned out my youngest son, Lior,  had already completed a blog.

Greg Kuperberg (left) with his mother Krystyna.  (Both Greg’s parents, Krystyna and Wlodek, are well known mathematicians). Dave Bacon (right)

Since then, I took part in a few blog discussions. I am curious about the meaning and role of mathematical discussions in general, and on blogs in particular.

### 5. Are mathematical debates possible?

I even took part in little “mathematical debates”. Here is a little quote from one of them; never mind the context. There aren’t many debates and controversies in mathematics, so if mathematical debating will ever become more developed, mathematical polemics may, perhaps, look like this:

Comment by Gil Kalai 3/14/2006:

In all these cases you approximate a rank-one matrix to start with. I believe that you may be able to approximate a rank-one matrix up to a rank-one error. I do not believe that you will be able to approximate an arbitrary matrix up to a rank one matrix.

Comment by Dave Bacon, later that day:

I will never look at rank one matrices the same

### 6. Guest Blogging on “what’s new”:

I gave two guest posts over Terry Tao’s blog

One was about the  weak epsilon net problem.

and the other was about the entropy/influence conjecture.

### 7.  Other topics.

I will occasionally try to discuss areas of mathematics that touch on combinatorics, and also topics that go beyond my expertise: applied mathematics, and in particular its applications to, and connection with computer science, economics, statistics,  and even physics and philosophy;  and issues related to academic life, especially in Israel.

This entry was posted in Blogging, Combinatorics, Controversies and debates, Open problems and tagged , , , , , , , , , , , . Bookmark the permalink.

### 13 Responses to Combinatorics, Mathematics, Academics, Polemics, …

1. Mr WordPress says:

Hi, this is a comment.
To delete a comment, just log in, and view the posts’ comments, there you will have the option to edit or delete them.

2. Noam says:

Way to go, Gil!

3. Itai says:

4. Oded says:

Hi Gil,
This is my first post to a blog.
I have a question for you. Suppose that you want to find a large collection of subsets of [n] such that no set in your collection is contained in the union of 3 other sets in the collection. Picking the sets independently with x in S having probability 1/2 independently allows you to have a^n subsets for some a>1. Are there known explicit constructions?
Oded

PS: I recently learned that there’s a new math journal: Rejecta Mathematica http://math.rejecta.org/

5. Gil Kalai says:

Dear Noam, Itai and Oded – thanks a lot.

Regarding Oded’s question. I did not know off hand but Noga whom I asked did. Here is his answer:

“Yes, there are all kinds of explicit and semi-explicit constructions, usually not as good as the one you can get probabilistically (which is obtained by choosing things not with p=1/2 but with some optimal p, so maybe this shows that Oded does not care about the constant).

One place to look is at my paper :

N. Alon, D. Moshkovitz and M. Safra,

Algorithmic construction of sets for k-restrictions, ACM Transactions on Algorithms 2 (2006), 153-177. (section 6, I think)+ its references,

an earlier place (simpler, if you don’t care about constants) is in:

N. Alon, Explicit construction of exponential sized families of $k$-independent sets, Discrete Math. 58(1986), 191-193.

The simplest way is to take some code with large alphabet (say 100 letters or so) with distance that ensures that every 4 words have a coordinate in which all 4 are distinct, and then use concatenation (i.e., replace every letter by a binary word ensuring that in every 4 words there will be a coordinate in which one is 1 and all other 3 are 0.

That is the original problem, but now we need only 100 words so no need to be clever here, if you don’t care about constants you can even use the unit vectors). “

6. Oded says:

Thanks for the info! Indeed, at this point I don’t care about the constant.

Sorry for being slow, but I don’t understand the simple explicit construction you are referring to at the end. Say you have a code with n words of length k over an alphabet with 100 letters. I see how to reduce to the binary case. But what does “then use concatenation” mean?

7. Gil says:

I think it goes like this. You replace every letter of the alphabet (say 100 of them) by a binary string of length t so that the family of these binary strings (regarded as sets) satisfies the original “no union of three contain the forth” requirement.

If you do it then the condition that there is a coordinate for which in the large alphabet code all entries are distinct implies that in the binary version
for every four code-words a b c d , there is a coordinate where a b c are ’0′ and d is ’1′.

The number of codewords in the large-alphabet-code was exponential in the length s. The number of codewords in the binary new code is exponential in s and therefore also in (st) since t is a constant. And if you do not care at all about the constant you can take t=100 and represent the ith alphabet letter by (0,0,…,1,0…0) with 1 in the ith place.

8. Gil Kalai says:

Actually the very simple construction does depend on an explicit exponential constructions of codes over a large alphabet which correct many errors. There is no simple such constructions. Using Justesen codes, which are concatenation codes of Reed Solomon codes, is perhaps the easiest option. There are the famous algebraic geometry codes which gives the best known rates.

9. Gil says:

Noam Nisan has a blog now “Algorithmic Game Theory”
http://agtb.wordpress.com/
way to go, Noam!