Date:
Mon, 19/12/201610:00-12:00
Location:
Sprinzak 101
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.
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.