Exact Bounds for Forbidden Configurations and the Extremal Matrices
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918276619042816 |
|---|---|
| author | Anstee, Richard P. Edens, Oakley Sahami, Arvin Seok, Jaehwan Sali, Attila |
| author_facet | Anstee, Richard P. Edens, Oakley Sahami, Arvin Seok, Jaehwan Sali, Attila |
| contents | Let $F$ be a $k\times \ell$ (0,1)-matrix. A matrix is simple if it is a (0,1)-matrix with no repeated columns. A (0,1)-matrix $A$ is said to have a $F$ as a configuration if there is a submatrix of $A$ which is a row and column permutation of $F$. In the language of sets, a configuration is a trace.
Let $\mathrm{Avoid}(m,F)$ be all simple $m$-rowed matrices $A$ with no configuration $F$. Define $\mathrm{forb}(m,F)$ as the maximum number of columns of any matrix in $\mathrm{Avoid}(m,F)$. The $2\times (p+1)$ (0,1)-matrix $F(0,p,1,0)$ consists of a row of $p$ 1's and a row of one 1 in the remaining column. The paper determines $\mathrm{forb}(m,F(0,p,1,0))$ for $1\le p\le 9$ and the extremal matrices are characterized. A construction may be extremal for all $p$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_04084 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Exact Bounds for Forbidden Configurations and the Extremal Matrices Anstee, Richard P. Edens, Oakley Sahami, Arvin Seok, Jaehwan Sali, Attila Combinatorics 05D05 Let $F$ be a $k\times \ell$ (0,1)-matrix. A matrix is simple if it is a (0,1)-matrix with no repeated columns. A (0,1)-matrix $A$ is said to have a $F$ as a configuration if there is a submatrix of $A$ which is a row and column permutation of $F$. In the language of sets, a configuration is a trace. Let $\mathrm{Avoid}(m,F)$ be all simple $m$-rowed matrices $A$ with no configuration $F$. Define $\mathrm{forb}(m,F)$ as the maximum number of columns of any matrix in $\mathrm{Avoid}(m,F)$. The $2\times (p+1)$ (0,1)-matrix $F(0,p,1,0)$ consists of a row of $p$ 1's and a row of one 1 in the remaining column. The paper determines $\mathrm{forb}(m,F(0,p,1,0))$ for $1\le p\le 9$ and the extremal matrices are characterized. A construction may be extremal for all $p$. |
| title | Exact Bounds for Forbidden Configurations and the Extremal Matrices |
| topic | Combinatorics 05D05 |
| url | https://arxiv.org/abs/2601.04084 |