Hypertrees (Nati Linial)
Abstract: Paraphrasing a very famous poem, I would like to ask "who can make a hypertree?". This lecture is partly based on work with Ilan (jointly also with Yuval Peled and Yuri Rabinovich). Hypertrees were first introduced by Gil Kalai in 1983. As is often the case in high-dimensional combinatorics, it is a good idea to start the journey with graphs which constitute the one-dimensional case. Consider A=A_n the signed incidence (n \times {n \choose 2}) of the complete graph. It has rank n-1 and we wish consider bases for the column space of A. It is not hard to see that these are precisely all n-vertex trees. In the d-dimensional case, we start from A=A^d_n, the signed inclusion matrix. This is an {n \choose d}x{n \choose d+1} matrix of rank is {n-1 \choose d}. A basis for the column space of this matrix is a set of {n-1 \choose d} sets of size d+1 and such a collection is called a d-dimensional hypertree. Many fascinating questions suggest themselves and I will try to give you a taste of what we know and what we still wish to accomplish.
