Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

On 09.10.2008 at 12:20 in S8, there is the following noon lecture:

Removal Lemma for systems of linear equations

Daniel Král

KAM

Abstract

We study algebraic analogues of the (hyper)graph Removal Lemma. In 2005, Green conjectured the following:

For every k x m integral matrix A with rank k and every eps>0, there exists delta>0 such that the following holds for every N and every subset S of {1,...N}: if the number of solutions of A x = 0 with x \in S^m is at most delta N^{m-k}, then it is possible to destroy all solutions x \in S^m of A x = 0 by removing at most eps N elements from the set S.

We prove this conjecture by establishing its analogue for not necessarily homogenous systems of equations over finite fields. The core of our proof is a reduction of the statement to the colored version of hypergraph Removal Lemma for (k+1)-uniform hypergraphs. Independently of us, Shapira obtained the same result using a reduction to the colored version of hypergraph Removal Lemma for O(m^2)-uniform hypergraphs.

Joint work with Oriol Serra and Lluis

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010