Noon lecture

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

On 18.11.2010 at 12:20 in S11, there is the following noon lecture:

Large subfamilies with forbidden configurations

Ida Kantor

Abstract

Let F be a family of finite sets. A subfamily F' of F is a-union-free if it does not contain distinct sets A_1,...,A_{a+1} such that A_1\cup A_2 \cup...\cup A_a = A_{a+1}. f(F,a-union-free) will denote the size of the largest a-union-free subfamily of F, and f(m,a-union-free)= min f(F,a-union-free), where the minimum is taken over all families F of cardinality m.

Instead of "a-union-free" we can take any other property Gamma, and define f(m,Gamma) analogously.

Erdos and Komlos, Kleitman, and Erdos and Shelah have results on 2-union-free families and B_2-free families, where B_2 is Boolean lattice of dimension 2, i.e., distinct sets A_1,A_2,A_3,A_4 such that A_1\cup A_2=A_3 and A_1\cap A_2=A_4. In particular, they show that f(m,B_2-free)\leq (2/3)m^{2/3} and conjecture that the lower bound is cm^{2/3} for some positive constant c.

We prove the conjecture, and provide lower and upper bounds for f(m,

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