Property testing and expansion in cubical complexes

Seminar
Speaker
Uzi Vishne (Bar-Ilan University)
Date
10/11/2019 - 15:30 - 14:00Add to Calendar 2019-11-10 14:00:00 2019-11-10 15:30:00 Property testing and expansion in cubical complexes We are given a 2-coloring of the edges of the complete graph. If the number of red edges in triangles is almost always even, then the coloring is approximately defined on vertices. Thus triangles "test" a function on edges to be defined from the vertices. Replacing triangles by squares, and going up in the dimension, we show that differentials can test properties, as long as the cohomology group is sufficiently well understood. Joint work with David Garber. Room 201, Math and CS Building (Bldg. 216) אוניברסיטת בר-אילן - Department of Mathematics mathoffice@math.biu.ac.il Asia/Jerusalem public
Place
Room 201, Math and CS Building (Bldg. 216)
Abstract

We are given a 2-coloring of the edges of the complete graph. If the number of red edges in triangles is almost always even, then the coloring is approximately defined on vertices. Thus triangles "test" a function on edges to be defined from the vertices.
Replacing triangles by squares, and going up in the dimension, we show that differentials can test properties, as long as the cohomology group is sufficiently well understood.

Joint work with David Garber.

Last Updated Date : 11/11/2019