Printable PDF
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

****************************