Higher-dimensional combinatorics

1:30 – 2:20pm, Tuesday, February 2, 2010
CSE 305
Nati Linial, Hebrew University of Jerusalem


A simplicial complex X is a finite collection of sets such that if A is in X and B is a subset of A, then B is in F as well. The members of X are called faces or simplices and the dimension of A is defined as |A|-1. The dimension of X is defined as the highest dimension of any face in X. It is not hard to see that a graph is simply a one-dimensional simplicial complex. This suggests that we can investigate simplicial complexes in ways that were found useful in the study of graphs.

In this talk I will mention some of what is already known in this domain. I will mention some (past and current) applications in computer science. I will describe a little of what we know about random simplicial complexes and discuss some interesting open questions in the extremal theory of simplicial complexes. I will also briefly explain some basic topological aspects of the subject.

The parts that refer to my own research are covered in papers with Roy Meshulam, Lior Aronshtam, Eli Gafni, Yehuda Afek and Benny Sudakov.

The talk is self-contained and does not require any particular background in the relevant fields.