Forbidden Configurations and Product Constructions
| العنوان: | Forbidden Configurations and Product Constructions |
|---|---|
| المؤلفون: | Richard P. Anstee, Christina Koch, Miguel Raggi, Attila Sali |
| المصدر: | Graphs and Combinatorics. 30:1325-1349 |
| بيانات النشر: | Springer Science and Business Media LLC, 2013. |
| سنة النشر: | 2013 |
| مصطلحات موضوعية: | Combinatorics, Discrete mathematics, Matrix (mathematics), Trace (linear algebra), Product (mathematics), Identity matrix, Triangular matrix, Discrete Mathematics and Combinatorics, Theoretical Computer Science, Mathematics |
| الوصف: | A simple matrix is a (0,1)-matrix with no repeated columns. For a (0,1)-matrix F, we say that a (0,1)-matrix A has F as a configuration if there is a submatrix of A which is a row and column permutation of F (trace is the set system version of a configuration). Let $${\|A\|}$$ ? A ? denote the number of columns of A. We define $${{\rm forb}(m, F) = {\rm max}\{\|A\| \,:\, A}$$ forb ( m , F ) = max { ? A ? : A is m-rowed simple matrix and has no configuration F. We extend this to a family $${\mathcal{F} = \{F_1, F_2, \ldots , F_t\}}$$ F = { F 1 , F 2 , ? , F t } and define $${{\rm forb}(m, \mathcal{F}) = {\rm max}\{\|A\| \,:\, A}$$ forb ( m , F ) = max { ? A ? : A is m-rowed simple matrix and has no configuration $${F \in \mathcal{F}\}}$$ F ? F } . We consider products of matrices. Given an m 1 × n 1 matrix A and an m 2 × n 2 matrix B, we define the product A × B as the (m 1 + m 2) × n 1 n 2 matrix whose columns consist of all possible combinations obtained from placing a column of A on top of a column of B. Let I k denote the k × k identity matrix, let $${I_k^{c}}$$ I k c denote the (0,1)-complement of I k and let T k denote the k × k upper triangular (0,1)-matrix with a 1 in position i, j if and only if i ≤ j. We show forb(m, {I 2 × I 2, T 2 × T 2}) is $${\Theta(m^{3/2})}$$ ? ( m 3 / 2 ) while obtaining a linear bound when forbidding all 2-fold products of all 2 × 2 (0,1)-simple matrices. For two matrices F, P, where P is m-rowed, let $${f(F, P) = {\rm max}_{A} \{\|A\| \,:\,A}$$ f ( F , P ) = max A { ? A ? : A is m-rowed submatrix of P with no configuration F}. We establish f(I 2 × I 2, I m/2 × I m/2) is $${\Theta(m^{3/2})}$$ ? ( m 3 / 2 ) whereas f(I 2 × T 2, I m/2 × T m/2) and f(T 2 × T 2, T m/2 × T m/2) are both $${\Theta(m)}$$ ? ( m ) . Additional results are obtained. One of the results requires extensive use of a computer program. We use the results on patterns due to Marcus and Tardos and generalizations due to Klazar and Marcus, Balogh, Bollobas and Morris. |
| تدمد: | 1435-5914 0911-0119 |
| URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_________::750d2a9c60a1d9c5bcfc1fd32f47fea3 https://doi.org/10.1007/s00373-013-1365-1 |
| حقوق: | OPEN |
| رقم الأكسشن: | edsair.doi...........750d2a9c60a1d9c5bcfc1fd32f47fea3 |
| قاعدة البيانات: | OpenAIRE |
| تدمد: | 14355914 09110119 |
|---|