Sách Forbidden Configurations: Exact bounds determined by critical substructures

We consider the following extremal set theory problem. Define a matrix to be simple if it is a (0,1)-matrix with no repeated columns. An m-rowed simple matrix corresponds to a family of subsets of {1, 2, . ,m}. Let m be a given integer and F be a given (0,1)-matrix (not necessarily simple). We say a matrix A has F as a configuration if a submatrix of A is a row and column permutation of F. We define forb(m, F) as the maximum number of columns that a simple m-rowed matrix A can have subject to the condition that A has no configuration F. We compute exact values for forb(m, F) for some choices of F and in doing so handle all 3 × 3 and some k × 2 (0,1)-matrices F. Often forb(m, F) is determined by forb(m, F′ ) for some configuration F′ contained in F and in that situation, with F′ being minimal, we call F′ a critical substructure.