Richard Anstee, Ron Ferguson and Attila Sali - Small forbidden configurations

Next: Aart Blokhuis, Ralph Faudree, Up: Extremal Combinatorics / Combinatoire Previous: Extremal Combinatorics / Combinatoire

Richard Anstee $^\ast$ , Ron Ferguson and Attila Sali - Small forbidden configurations

RICHARD ANSTEE
$\begin{TEX2HTML_WRAP_INLINE}$^\ast$\end{TEX2HTML_WRAP_INLINE}$
, RON FERGUSON AND ATTILA SALI, Department of Mathematics, University of British Columbia, Vancouver, British Columbia V6T 1Z2, Canada; Department of Mathematics, University of British Columbia, Vancouver, British Columbia V6T 1Z2, Canada and Mathematics Institute of Hungarian Academy of Sciences, Budapest, Hungary

Small forbidden configurations

An extremal set problem stated in matrix terms considers a $k\times l$ (0,1)-matrix F and an $m\times n$ (0,1)-matrix A which has no repeated columns. We assume A has no submatrix which is a row and column permutation of F and then seek bounds on n in terms of F,m. We wish to report progress in obtaining a number of new exact bounds for various $2\times l$ F. The arguments often use graph theory in interesting ways. Turán's m²/4 bound arises with a different twist. It seems possible to get exact bounds for all $2\times l$ F. Progress for $3\times l$ F has also been obtained but the triple systems are harder to analyze.

Next: Aart Blokhuis, Ralph Faudree, Up: Extremal Combinatorics / Combinatoire Previous: Extremal Combinatorics / Combinatoire