caa a22 4500 445358467 CHVBK 20180317142908.0 cr unu---uuuuu 170323e20110101xx s 000 0 eng 10.1007/s00493-011-2595-6 doi (NATIONALLICENCE)springer-10.1007/s00493-011-2595-6 Linear algebra methods for forbidden configurations [Elektronische Daten] [Richard Anstee, Balin Fleming] We say a matrix is simple if it is a (0,1)-matrix with no repeated columns. Given m and a k×l (0,1)-matrix F we define forb(m,F) as the maximum number of columns in a simple m-rowed matrix A for which no k×l submatrix of A is a row and column permutation of F. In set theory notation, F is a forbidden trace. For all k-rowed F (simple or non-simple) Füredi has shown that forb(m,F) is O(m k ). We are able to determine for which k-rowed F we have that forb(m,F) is O(m k−1) and for which k-rowed F we have that forb(m,F) is Θ(m k ). We need a bound for a particular choice of F. Define D 12 to be the k×(2 k −2 k−2−1) (0,1)-matrix consisting of all nonzero columns on k rows that do not have [ 1 1 ] in rows 1 and 2. Let 0 denote the column of k 0's. Define F k (t) to be the concatenation of 0 with t+1 copies of D 12. We are able to show that forb(m,F k (t)) is Θ(m k−1). Linear algebra methods and indicator polynomials originated in this context in a paper of the authors and Füredi and Sali. We provide a novel application of these methods. The results are further evidence for the conjecture of Anstee and Sali on the asymptotics for fixed F of forb(m,F). János Bolyai Mathematical Society and Springer Verlag, 2011 Anstee Richard Mathematics Department, The University of British Columbia, V6T 1Z2, Vancouver, B. C., Canada aut Fleming Balin Mathematics Department, The University of British Columbia, V6T 1Z2, Vancouver, B. C., Canada aut Combinatorica Springer-Verlag 31/1(2011-01-01), 1-19 0209-9683 31:1<1 2011 31 493 https://doi.org/10.1007/s00493-011-2595-6 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00493-011-2595-6 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Anstee Richard Mathematics Department, The University of British Columbia, V6T 1Z2, Vancouver, B. C., Canada aut NATIONALLICENCE 700 1- Fleming Balin Mathematics Department, The University of British Columbia, V6T 1Z2, Vancouver, B. C., Canada aut NATIONALLICENCE 773 0- Combinatorica Springer-Verlag 31/1(2011-01-01), 1-19 0209-9683 31:1<1 2011 31 493 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer