Small forbidden configurations. II
The electronic journal of combinatorics, Tome 8 (2001) no. 1
The present paper continues the work begun by Anstee, Griggs and Sali on small forbidden configurations. In the notation of (0,1)-matrices, we consider a (0,1)-matrix $F$ (the forbidden configuration), an $m\times n$ (0,1)-matrix $A$ with no repeated columns which has no submatrix which is a row and column permutation of $F$, and seek bounds on $n$ in terms of $m$ and $F$. We give new exact bounds for some $2\times l$ forbidden configurations and some asymptotically exact bounds for some other $2\times l$ forbidden configurations. We frequently employ graph theory and in one case develop a new vertex ordering for directed graphs that generalizes Rédei's Theorem for Tournaments. One can now imagine that exact bounds could be available for all $2\times l$ forbidden configurations. Some progress is reported for $3\times l$ forbidden configurations. These bounds are improvements of the general bounds obtained by Sauer, Perles and Shelah, Vapnik and Chervonenkis.
@article{10_37236_1548,
author = {Richard Anstee and Ron Ferguson and Attila Sali},
title = {Small forbidden configurations. {II}},
journal = {The electronic journal of combinatorics},
year = {2001},
volume = {8},
number = {1},
doi = {10.37236/1548},
zbl = {0960.05100},
url = {http://geodesic.mathdoc.fr/articles/10.37236/1548/}
}
Richard Anstee; Ron Ferguson; Attila Sali. Small forbidden configurations. II. The electronic journal of combinatorics, Tome 8 (2001) no. 1. doi: 10.37236/1548
Cité par Sources :