When: Sunday, March 27, 10am
Where: Schreiber 309
Speaker: Deepak Rajendraprasad, University of Haifa
Title: Covering a complete simplicial complex with coboundaries
The minimum number of bipartite graphs needed to cover a complete n-vertex graph is ceil(log n). In this seminar, we will discuss an extension of this to higher dimensional simplicial complexes.
A simplicial complex X is a set-system which is closed under taking subsets. The members of X are called simplices. The dimension of a simplex s is |s|-1 and the dimension of X is the maximum dimension among its simplices. (Graphs are thus 1-dimensional simplicial complexes.) The n-vertex d-dimensional complete complex K(n,d) is the collection of all subsets of [n] of size at most d+1. One way to view a bipartite graph is as a subgraph of the "coboundary" of a set of vertices, where the coboundary of a set S of (d-1)-dimensional simplices is the collection of all the d-dimensional simplices in K(n,d), each of which contains an odd number of faces from S. (This is equivalent to the homological definition of a coboundary over the field GF(2)).
We will present estimates on the minimum number of coboundaries needed to cover K(n,d).
This is a joint work with Ilan Newman and Yuri Rabinovich.
