On Forbidden Submatrices
| Autor: | Méroueh, Arès |
|---|---|
| Rok vydání: | 2014 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | Given a $k\times l$ $(0,1)$-matrix $F$, we denote by $\mathrm{fs}(m,F)$ the largest number for which there is an $m \times \mathrm{fs}(m,F)$ $(0,1)$-matrix with no repeated columns and no induced submatrix equal to $F$. A conjecture of Anstee, Frankl, F\"{u}redi and Pach states that $\mathrm{fs}(m,F) = O(m^k)$ for a fixed matrix $F$. The main results of this paper are that $\mathrm{fs}(m,F) = m^{2+ o(1)}$ if $k=2$ and that $\mathrm{fs}(m,F) = m^{5k/3 -1 + o(1)}$ if $k\geq 3$. Comment: 11 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|