Special logic seminar - Elad Levi "Algebraic regularity lemma for hypergraphs"

Speaker: Elad Levi Algebraic regularity lemma for hypergraphs Abstract: Szemer´edi’s Regularity Lemma is a fundamental tool in graph theory. It states that for every large enough graph, the set of vertices has a partition A1,..,Ak, such that for almost every two subsets Ai,Aj the induced bipartite graph on (Ai,Aj) is regular, i.e. similar to a random bipartite graph up to a given error. Tao proved an algebraic version of this theorem in case the graph is definable in a pseudo-finite field. Tao's theorem has three advantages: the partition is definable, the induced graph on every two subsets behave almost randomly, and a drastic improvement of the error term. In our work we develop model theoretical tools and use them to generalise this theorem to hypergraphs. Joint work with Ehud Hrushovski.

Date: 

Mon, 19/12/2016 - 10:00 to 12:00

Location: 

Sprinzak 101