A Diamater Problem for Families of Sets.

Let me draw your attention to the following problem:

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

Associate to \cal F a graph G({\cal F}) as follows: The vertices of  G({\cal F}) are simply the sets in \cal F. Two vertices S and T are adjacent if |S \cap T|=d-1.

For a subset A \subset N let {\cal F}[A] denote the subfamily of all subsets of \cal F which contain A

MAIN ASSUMPTION: Suppose that for every A for which {\cal F}[A] is not empty G({\cal F}[A]) is connected.

MAIN QUESTION:   How large can the diameter of G({\cal F}) be in terms of d and n.

Extermal Combinatorics II: Some Geometry and Number Theory

Extremal problems in additive number theory

Our first lecture dealt with extremal problems for families of sets. In this lecture we will consider extremal problems for sets of real numbers, and for geometric configurations in planar Euclidean geometry. 

Problem I: Given a set A of n real numbers, how small can the set A+A={a+a': a,a’ \in A} be?

If A={1,2,…,n} |A+A|=2n-1. Suppose the elements of A are a_1,a_2, \dots, a_n and a_1< a_2<a_3\dots a_n. Note that a_1+a_1<a_1+a_2<a_1+a_2< \dots  a_1+a_n<a_2+a_n<\dots a_n+a_n. So we identified 2n-1 distinct elements in A+A. This is the Cauchy-Davenport theorem.  

Problem II: Given a set A of n positive real numbers, how small can be the set A \cdot A={a\cdot a': a,a’ \in A}?

You may protest (again, like in the first lecture,) that I regard problem II a different problem. You can move from problem II to problem I by taking the logarithm of all elements in A, or you can simply use the same proof with the sum replaced by a product. The proof relies only on very basic monotonicity properties of these operations.

OK, lets have another problem II.

Problem II: Given a set A of n real numbers, how small can the quantity max (|A+A|, |A \cdot A|) be? 

This problem was asked by Erdös, and in hindsight it is a very good problem. Erdös conjectured that the maximum behaves like n^2, and this is open.  We will see below a wonderful proof by Elekes that the maximum is (up to a multiplicative constant) at least n^{5/4}. The exponent 5/4 was improved twice(!!) by Jozsef Solymosi and there is a very nice post about his most recent ingenious proof for a lower bound max (|A+A|, |A \cdot A|) \ge (1/2) n^{4/3} (\log n)^{-1/3} in Izabella Laba’s blog. 

(Update 2/1/2008: “product-sum theorems” of this type grew into a large area with surprising applications in math and CS. They give a strong tool to extract randomness, and they are useful when we consider product of matrices where sums and products are naturally entangled. Here is a recent relevant post written by Herald Helfgott from Izabella Laba’s blog.)

Extremal problems in plane geometry

Problem III:  Given n points in the plane what is the maximum number of pairs among them at distance ‘1’

Problem IV:  Given s points and t lines in the plane what is the maximum number of incidences between them.

An incidence is a pair (p,\ell ) where p  is a point \ell  is a line and p \in \ell.

Problem V: Given a graph G with v vertices and e edges what is the minimum number of crossings in a planar drawing of G.

The second of my extremal combinatorics lectures was devoted to the surprising connections that were found between the above problems. There is also a very nice post about this material on Terry Tao’s blog. To show you something new I will describe a few problems in higher dimensions at the end.

Continue reading

Michal Linial – An Ambassador in Singapore

 

After the wonderful “being a cosmonaut” taxi-story, I am happy to present you:

 An Ambassador in Singapore

A story by Michal Linial

 

It was a long trip, 4 days in Singapore. I visited the tallest artificial waterfall in the world, and went on a night safari with artificial moon light. Well, time to go back home to reality. Before leaving my hotel, I made sure that I had enough money for a taxi ride to the airport. Due to last minute extra taxes, I found myself with only 15 Singaporean Dollars (~ 10 $ US). In the hotel, they promised me that it is more than enough. I entered the Taxi and immediately mentioned that I have 15$.

In the next 30 minutes my taxi driver explained that he actually does not want these 15$ at all. At the matter of fact, he is honored to take me to the airport as a treat of the Singaporean people to their distinguished guests. He said: ”I want your memories from Singapore to be enjoyable so you will tell everyone to visit us, and so you come back as well”. I was impressed. He continued: “my real satisfaction is to be the ambassador of my country”. He even went into some psychological arguments: “Can you remember the last time you were in Paris, can you tell me who took you to the airport?” I admitted that I did not remember, and then he continued: “Can you remember who took you to the airport from Jerusalem only 5 days ago ?” I had to admit that I did not remember any of this…and then he made his last point ”You will always remember me and you will want to come again to Singapore just because you met people like me”. Indeed, Continue reading

Arrow’s Economics 1

The annual Summer School in Economics at HU was directed until last year by Kenneth Arrow, along with Eyal Winter. Arrow decided this year to step down as a director and Eric Maskin is replacing him. The 2008 Summer School was devoted to Arrow’s economics. The list of speakers was quite impressive, with six lecturers who are Nobel Laureates. (Our local Institute for Advanced Study runs five schools every year, in Physics, Economics, Life Sciences, Jewish Studies, and Mathematics.)    

Economic puzzles told by Arrow

Let me tell you about three economics puzzles mentioned by Arrow in an earlier summer school. I doublechecked some details with Arrow himself; still, if my description contains errors I will be happy to be corrected. (Arrow spent a considerable amount of time talking with the workshop students. Another remarkable thing about him: he takes lecture notes! Is it a good idea to take detailed lecture notes at lectures? Let’s return to this question sometime.)

Puzzle 1: Why is there unemployment?

Why is this even a puzzle? Because the economics teaching that “the market will clear” means that all people who can work will. A person who can work and is not working represents inefficiency, which is not supposed to exist in a competitive economy. Part of the issue is referred to as “friction” and accounts for economics processes being slow rather than instantaneous. But it appears to be true that there is more to unemployment than that. What can explain the 30% unemployment that was witnessed in the US in the 1930s?

Is this puzzle a scientific problem? You bet it is! And it is a fairly clear-cut scientific problem. I suppose there are several answers to this puzzle in the literature but we are far from a definite understanding of the issue.

Puzzle 2: What is the reason for high volatility of prices in markets, say in stock markets?

The price of a stock, according to economics theory, represents the long-term value of the company. What accounts for the fact that the overall value of the entire stock market may fluctuate by more than 1% on a typical day? What accounts for fluctuations (more often drops) of 3-5% in one day? (Such fluctuations are not rare.) A famous question is to explain the one-day drop of 20% in October 1987. Continue reading

Pushing Behrend Around

Erdos and Turan asked in 1936: What is the largest subset S of {1,2,…,n} without a 3-term arithmetic progression?

In 1946 Behrend found an example with |S|=\Omega (n/2^{2 \sqrt 2 \sqrt {\log_2n}} \log^{1/4}n.)

Now, sixty years later, Michael Elkin pushed the the log^{1/4} n factor from the denominator to the enumerator, and found a set with  |S|=\Omega (n \log^{1/4}n/2^{2 \sqrt 2 \sqrt {\log_2n}} ). !

Here is a description of Behrend’s construction and its improvment as told by Michael himself:

“The construction of Behrend employs the observation that a sphere in any dimension is convexly independent, and thus cannot contain three vectors  such that one of them is the arithmetic average of the two other. The new construction replaces the sphere by a thin annulus. Intuitively, one can produce larger progression-free sets because an annulus of non-zero width contains more integer points than a sphere of the same radius does. However, Continue reading

From Helly to Cayley IV: Probability

I decided to split long part III into two parts. This (truly) last part of this series deals with probabilistic problems and with combinatorial questions regarding higher Laplacians. 

21. Higher Laplacians and their meanings

Our high dimensional extension to Cayley’s theorem reads:

\sum |H_{d-1}(K,{\bf Z})|^2 = n^{{n-2} \choose {d}},

The right hand side of our formula corresponds to the eigenvalues of a higher Laplacian of a complete d-dimensional complex with n vertices. In several general cases there are nice expressions for these eigenvalues – for matroidal complexes, for shifted complexes, for complete skeleta of the cubes and in other cases. There are also nice general high-dimensional matrix-tree theorems.

If C_k(K) is the space of k cycles and we identify it via a certain inner product with the space of k-cocycles, then we can talk about the Laplacian defined by latex \delta \partial+ (-1)^k \partial \delta where \partial is the boundary operator from C_k to C_{k-1} and \delta is the coboundary operator from C^k to C^{k+1}

Spectra of graphs’ Laplacians are very important, for understanding random walks on graphs, for expansion properties and they are also related to many graph parameters like the diameter. The recent series of posts on Luca Trevisan’s blog give a detailed description of these connections (See also this post on James Lee’s blog.) What about higher Laplacians? (Those do not correspond to connectivity but to higher homology groups.) 

What is the analog of the random walk interpretation of the spectral gap?

What is the analog of the relation between the spectral gap and expansion properties?

What is the analog of the diameter?   

22. Probabilistic questions

 Consider the class G of all d-dimensional simplicial complexes on n labelled vertices with {n-1} \choose {d} d-faces and a complete (d-1)-skeleton. Is there a substantial probability, for d>1,  that a random complex in G with the property that every (d-1)-face is contained in a d-face (no isolated (d-1)-faces) is Q-acyclic? This is not the case for graphs (d=1). The probability for a graph with n vertices and n-1 edges to be a tree tends to 0 even if it has no isolated vertices. This question has a similar flavour to results regarding singularity of random matrices with 0,1 entries.

Here are other natural probabilistic questions that go back to my old paper.

Inside G consider  

A) The class of collapsible complexes

B) The class of contractible complexes

Continue reading

A New Rector-Elect at the Hebrew University of Jerusalem

 

Professor Sarah Stroumsa

On Wednesday, the Senate of the Hebrew University of Jerusalem elected Professor Sarah Stroumsa (homepage) as the next Rector (provost) of the Hebrew University. For the first time since its establishment, the Hebrew University has elected a woman to its highest post of academic leadership.

The situation of the Israeli higher education is complicated and constantly on the verge of a crisis. But this election is a reason for celebration for the HU, and is part of an ongoing change in the Israeli society as a whole.

Leah Goldberg, 1946

Professor Leah Goldberg

 On this occasion, I would like to dedicate to Sarah and to the HU community a poem entitled “Rainbow”, written by the poet Leah Goldberg.  Leah Goldberg was an important scholar and a professor at the Hebrew University, and she is most famous as one of the greatest Hebrew writers of modern times. It is a poem for children, which I also regard as a metaphor of academic and other quests. To further celebrate the event (and in the tradition of Ehud Friedgut’s translation contest of a limerick on Konigsberg’s bridges and Euler), I am announcing an open contest for translating the poem into English. Please email me your translations or post them directly here. (You can find a very rough literal translation below.)

 

 

 

בשמיים ראיתי קשת,
היא עמדה ממש מול הרחוב
ורציתי אליה לגשת
ולראות אותה מקרוב.
והתחלתי ללכת, ללכת,
ועליתי על ראש גיבעה.
אך ככל שהרחקתי לכת
הקשת לא קרבה:

 עופי, עופי, יפת כנפיים!
עופי, עופי אל המרום,
אל הקשת אשר בשמיים
ומיסרי לה בירכת שלום.

 היא עמדה במרום רקיע
כמצויירת על עננה,
אז ידעתי שלא אגיע
ושלחתי אליה יונה. Continue reading

Helly, Cayley, Hypertrees, and Weighted Enumeration III

This is the third and last part of the journey from a Helly type conjecture of Katchalski and Perles to a Cayley’s type formula for “hypertrees”.  (On second thought I decided to divide it into two devoting the second to probabilistic questions.) This part will include several diversions, open problems, and speculations.  

11. How to make it work – the matrix tree theorem

Our high dimensional extension to Cayley’s theorem reads:

\sum |H_{d-1}(K,{\bf Z})|^2 = n^{{n-2} \choose {d}},

where the sum is over all d-dimensional simplicial complexes K on n labelled vertices, with a complete (d-1)-dimensional skeleton, and which are Q-acyclic, namely all their (reduced) homology groups with rational coefficients vanish.  

Looking at the various proofs of Cayley’s formula (there are many many many beautiful proofs), the proof that I know to apply is the one based on the matrix tree theorem.

Consider the signed incidence matrix A’ between all (d+1)-subsets and all d-subsets of {1,2,…,n} that represents the boundary operator of simplicial homology. The rank of this matrix is {n-1} \choose {d}, and just like in the ordinary matrix tree theorem you delete rows to be left with linearly independent rows. Here you delete all rows corresponding to sets containing ‘n’ and you are left with a matrix A. Now we compute the determinant of det (A \cdot A^{tr})  directly, and compare the result to a computation based on the Cauchy-Binet Formula.

The eigenvalues of A \cdot A^{tr} are the eigenvalues of the d-th Laplacian of the complete d-dimensional simplicial complex with n vertices. It is easy to inspect what they are and the determinant of A \cdot A^{tr} is indeed n^{{n-2} \choose {d}}.

The many square determinants correspond to d-dimensional simplicial complexes K on our labelled set of vertices, which satisfy f_{d-1}(K) = {{n} \choose {d}} and f_d(K) = {{n-1} \choose {d}}. Now if K has non-vanishing d-th homology, the determinant is zero. If K is a Q-acyclic simplicial complex (i.e., its (reduced) homology groups with rational coefficients are trivial) then it has a non zero determinant. So far, it is like trees, but next comes a surprise. The contribution of K is the square of the number of elements in H_{d-1}(K), the (d-1)th homology group of K. This torsion group is finite, but for d >1 it need not be trivial.

Emily Peters presents the matrix-tree theorem. From The Sarong Theorem Archive” – an electronic archive of images of people proving theorems while wearing sarongs.

 

12. An even simpler use of Cauchy-Binet worth knowing

Consider the n \times 2^n matrix A, whose columns are all +1 -1 vectors of length n. Computing det A A^{tr}, via Cauchy-Binet Formula (or by other easy methods) asserts that the expected value (det (B))^2 for all n \times n  +1/-1 matrices behaves roughly like (n!). This was observed by Turan and Szekeres who also found a formula for the sum of the fourth powers of all 0-1 n by n matrices. See a leter paper by Turan. (I am not aware of a similar formula for the fourth power of the size of the homology groups for hypertrees.) Much is known about the determinant and related properties of random 0-1 matrices and the analogy between torsion in the homology groups of random complexes and determinants of random matrices looks like a good analogy.

13. Torsion

One consequence of the formula compared to the total number of available simplicial complexes is that the torsion group is typically huge. (For d>1, the expected value of |H_{d-1}(K,{\bf Z})|^2 for Q-acyclic complexes counted by the formula, is asymptotically larger than ((d+1)/e)^{{n-2} \choose {d}}; I am not aware of explicit examples with such a huge torsion group.)

How should we think about torsion in homology? It seems that thinking about the size of the torsion as a behaving like the determinant of a random matrix, may give a good intuition for many cases.

14. Extending other proofs for Cayley’s theorem?     

Cayley’s counting trees theorem has many wonderful proofs.  Can any other proof extend to the case of Q-acyclic simplicial complexes? For example, one proof relies on the exponential theorem that relates the exponential generating functions for connected and general graphs with a certain property P. (Followed by the Lagrange inversion formula.) Is there an analog of the exponential formula when connectivity is replaced by higher homology? Is there any analog of Prüfer sequences? I am not aware of any other proof that works.

15. Weights to the rescue of other conjectures? 

Can we use subtle weights to save other promising but false enumerative conjectures? The farthest reaching fantasy in this direction Continue reading