תאריך:
ב', 19/12/201610:00-12:00
תאריך:
ב', 19/12/201610:00-12:00
ראה גם: Logic, Seminars, Events & Seminars
מיקום:
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.
ב', 19/12/201610:00-12:00
ראה גם: Logic, Seminars, Events & Seminars
מיקום:
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.