Coming back from Hinxton, the most exciting genome center in the world and the most boring place after 5pm… At 5:30, a shuttle bus takes all the ‘workers’ to the big city – to Cambridge. The shuttle bus dropped us in the middle of town and without noticing, I remained alone. I quickly looked around; actually, there was no one on the street… OK I decided, the evening is not lost yet, I will go to London…

I waited 5 minutes and a Taxi stopped next to me. To the train station” I said. My taxi driver started the ride and then slowed down, stopped for a minute next to an open bar looked extremely worried and after 2 minutes speeded up again. We moved another 100 meters and again, he slows down and stop for 2 minutes next to a TV screen in the next open bar. He looks bothered and mumbled to himself, I hate him, Continue reading

# Monthly Archives: December 2008

# Test Your Intuition (2)

**Question:** Let be the cube in centered at the origin and having -dimensional volume equal to one. What is the maximum -dimensional volume of when is a hyperplane?

Can you guess the behavior of when ? Can you guess the plane which maximizes the area of intersection for ?

Test your intuition **before** reading the rest of the entry.

# Test Your Intuition (1)

**Question:** Suppose that we sequentially place balls into boxes by putting each ball into a randomly chosen box. It is well known that when we are done, the fullest box has with high probability balls in it. Suppose instead that for each ball we choose **two** boxes at random and place the ball into the one which is less full at the time of placement. What will be the maximum occupancy?

Test your intuition **before** reading the rest of the entry.

# Can Category Theory Serve as the Foundation of Mathematics?

Usually the foundation of mathematics is thought of as having two pillars: mathematical logic and set theory. We briefly discussed mathematical logic and the foundation of mathematics in the story of Gödel, Brouwer, and Hilbert. The story of set theory is one of the most exciting in the history of mathematics, and its main hero was Georg Cantor, who discovered that there are many types of “infinity.”

Mathematical logic was always considered a very abstract part of mathematical activity, related to philosophy and quite separate from applications of mathematics. With the advent of computers, however, this perception completely changed. Logic was the first, and for many years, the main mathematical discipline used in the development of computers, and to this day large parts of computer science can be regarded as “applied logic.”

While mathematical logic and set theory indeed make up the language spanning all fields of mathematics, mathematicians rarely speak it. To borrow notions from computers, basic mathematical logic can be regarded as the “machine language” for mathematicians who usually use much higher languages and who do not worry about “compilation.” (Compilation is the process of translating a high programming language into machine language.)

The story of Category Theory is markedly different from that of mathematical logic and set theory. It was invented Continue reading

# Gödel, Hilbert and Brouwer

Is mathematics a consistent theory? Or, rather, is there a danger of finding a correct mathematical proof for a false statement like “0 = 1”? These questions became quite relevant at the end of the nineteenth century, when some mathematical truths dating back many centuries were shattered and mathematicians started to feel the need for completely rigorous and solid foundations for their discipline. Continue reading

# A Diameter problem (7): The Best Known Bound

### Our Diameter problem for families of sets

Consider a family of subsets of size d of the set N={1,2,…,n}.

Associate to a graph as follows: The vertices of are simply the sets in . Two vertices and are adjacent if .

For a subset let denote the subfamily of all subsets of which contain .

**MAIN ASSUMPTION**: Suppose that for every for which is not empty is **connected.**

We will call a family satisfying this assumption **“hereditarily connected”.**

**MAIN QUESTION: **How large can the diameter of be in terms of and ?

**We denote the answer by . **

For let be the family obtained from by removing from every set. Since , the diameter of is at most .

### 8. A slight generalization

Let be an hereditarily connected family of -subsets of a set . Let be a subset of . The length of a path of sets **modulo Y**

*(where for every ) is the number of such that both and are subsets of . (In other words, in we consider edges between subsets of*

*having length 1 and other edges as having length 0.)*

**Y**asLet be the largest diameter of an hereditarily connected family of -subsets of an arbitrary set **modulo a set Y** , with .

Since we can always take we have .

### 9. A quasi-polynomial upper bound

We will now describe an argument giving a quasi-polynomial upper bound for . This is an abstract version of a geometric argument of Kleitmen and me.

Let be a hereditarily connected family of -subsets of some set , let , , and let and be two sets in the family.

**Claim:** We can always either

1) find paths of length at most **modulo Y **from to -subsets of whose union has more than elements.

or

2) we can find a path of this length **modulo Y** from to .

**Proof of the claim**: Let be the set of elements from that we can reach in steps **modulo Y** from . (Let me explain it better: is the elements of in the union of all sets that can be reached in steps

**modulo**from . Or even better: is the intersection of with the union of all sets in which can be reached from in steps

*Y***modulo**

*Y.**)*

The distance of from **modulo Z** is at most .

Now, if we are in case 1).

If then there is a path from to **modulo Z** of length . If this path reaches no set containing a point in we are in case 1). (Because this path is actually a path of length from to

**modulo**. Otherwise, we reached via a path of length

*Y)***modulo**from a set containing a point in , in contradiction to the definition of .

*Y***Walla**.

**Corollary: **.

By a path of length **modulo Y ** we reach from at least elements in , (or ). By a path of length

**modulo**we reach from at least elements in , (or ). So unless we can go from to in steps

*Y***modulo**we can reach more than elements from both and by paths of length

*Y***modulo**,hence there is some element we can reach from both.

*Y*In other words in steps **modulo *** Y *we go from to and from to so that and share an element .

But the distance from to **modulo Y** (which is the same as the distance

**modulo**from to in is at most . (We use here the fact that )

*Y***Ahla!**

To solve the recurrence, first for convenience replace by . (You get a weaker inequality.) Then write to get and to get which gives which in turn gives and . **Sababa!**