Department of Mathematics,
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
****************************