比利时vs摩洛哥足彩
,
university of california san diego
****************************
math 269 - combinatorics
peter keevash
cal. tech
pairwise intersections and forbidden configurations
abstract:
let $f_m(a,b,c,d)$ denote the maximum size family of a family $f$ of subsets of an $m$-element set so that there is no pair of sets $a,b$ in $f$ such that: \vskip .1in \noindent (i) $a$ and $b$ have at least $a$ points in common \vskip .01in \noindent (ii) $b$ has at least $b$ points not in $a$ \vskip .01in \noindent (iii) $a$ has at least $c$ points not in $b$ \vskip .01in \noindent (iv) there are at least $d$ points not in $a$ or $b$ \vskip .1in \noindent by symmetry we can assume $a >= d$ and $b >= c$. we show that $f_m$(a,b,c,d) has order of magnitude $m^{a+b-1}$ if either $b>c$ or $a,b >= 1$. we also show $f_m$(0,b,b,0) has order $m^b$ and $f_m(a,0,0,d)$ has order $m^a$. this can be viewed as a result concerning forbidden configurations, and provides further evidence for a conjecture of anstee and sali. our key tool is a strong stability version of the ahlswede-khachatrian complete intersection theorem, which is of independent interest. \vskip .1in \noindent this is joint work with richard anstee.
host: fan chung graham
october 25, 2005
4:00 pm
ap&m 7321
****************************