# Combinatorics Seminar

When: Sunday, March 27, 10am

Where: Schreiber 309

Speaker: Deepak Rajendraprasad, University of Haifa

Title: Covering a complete simplicial complex with
coboundaries

## Abstract:

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.

redesigned by barak soreq