Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Forbidden Configurations: Exact bounds determined by critical substructures. | Forbidden Configurations Exact bounds determined by critical substructures R. P. Anstee and S. N. Karpi Mathematics Department The University of British Columbia Vancouver . Canada V6T 1Z2 anstee@ skarp@uwaterloo. ca Submitted Aug 5 2009 Accepted Mar 18 2010 Published Mar 29 2010 Mathematics Subject Classification 05D05 Abstract 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 X 3 and some k X 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. Keywords VC-dimension 0 1 -matrices forbidden configurations trace 1 Introduction We define a simple matrix as a 0 1 -matrix with no repeated columns. Assume we are given a k X I 0 1 -matrix F. We say that a matrix A has F as a configuration if A has Research supported in part by NSERC. The first author gratefully thanks the Mathematics Department of the University of South Carolina Columbia SC USA for hosting me during my sabbatical in 2008 when this work was initiated. 1 Undergraduate at U of Waterloo with research at UBC supported by NSERC USRA and NSERC of first author THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 R50 1 a k X submatrix which is a row and column permutation of F and so F is referred to as a configuration in A sometimes called trace . Many F considered in this paper are non-simple. For a matrix A we .
