Extremal bounds for pattern avoidance in multidimensional 0-1 matrices
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909373488431104 |
|---|---|
| author | Geneson, Jesse Tsai, Shen-Fu |
| author_facet | Geneson, Jesse Tsai, Shen-Fu |
| contents | A 0-1 matrix $M$ contains another 0-1 matrix $P$ if some submatrix of $M$ can be turned into $P$ by changing any number of $1$-entries to $0$-entries. $M$ is $\mathcal{P}$-saturated where $\mathcal{P}$ is a family of 0-1 matrices if $M$ avoids every element of $\mathcal{P}$ and changing any $0$-entry of $M$ to a $1$-entry introduces a copy of some element of $\mathcal{P}$. The extremal function $\operatorname{ex}(n,\mathcal{P})$ and saturation function $\operatorname{sat}(n,\mathcal{P})$ are the maximum and minimum possible weight of an $n\times n$ $\mathcal{P}$-saturated 0-1 matrix, respectively, and the semisaturation function $\operatorname{ssat}(n,P)$ is the minimum possible weight of an $n\times n$ $\mathcal{P}$-semisaturated 0-1 matrix $M$, i.e., changing any $0$-entry in $M$ to a $1$-entry introduces a new copy of some element of $\mathcal{P}$.
We give upper bounds on parameters of minimally non-$O(n^{d-1})$ $d$-dimensional 0-1 matrices, generalized from minimally nonlinear 0-1 matrices in two dimensions, and we show the existence of infinitely many minimally non-$O(n^{d-1})$ $d$-dimensional 0-1 matrices with all dimensions of length greater than $1$. For any positive integers $k,d$ and integer $r\in[0,d-1]$, we construct a family of $d$-dimensional 0-1 matrices with both extremal function and saturation function exactly $kn^r$ for sufficiently large $n$. We show that no family of $d$-dimensional 0-1 matrices has saturation function strictly between $O(1)$ and $Θ(n)$ and we construct a family of $d$-dimensional 0-1 matrices with bounded saturation function and extremal function $Ω(n^{d-ε})$ for any $ε>0$. Up to a constant multiplicative factor, we fully settle the problem of characterizing the semisaturation function of families of $d$-dimensional 0-1 matrices, which we prove to always be $Θ(n^r)$ for some integer $r\in[0,d-1]$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_11934 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Extremal bounds for pattern avoidance in multidimensional 0-1 matrices Geneson, Jesse Tsai, Shen-Fu Combinatorics A 0-1 matrix $M$ contains another 0-1 matrix $P$ if some submatrix of $M$ can be turned into $P$ by changing any number of $1$-entries to $0$-entries. $M$ is $\mathcal{P}$-saturated where $\mathcal{P}$ is a family of 0-1 matrices if $M$ avoids every element of $\mathcal{P}$ and changing any $0$-entry of $M$ to a $1$-entry introduces a copy of some element of $\mathcal{P}$. The extremal function $\operatorname{ex}(n,\mathcal{P})$ and saturation function $\operatorname{sat}(n,\mathcal{P})$ are the maximum and minimum possible weight of an $n\times n$ $\mathcal{P}$-saturated 0-1 matrix, respectively, and the semisaturation function $\operatorname{ssat}(n,P)$ is the minimum possible weight of an $n\times n$ $\mathcal{P}$-semisaturated 0-1 matrix $M$, i.e., changing any $0$-entry in $M$ to a $1$-entry introduces a new copy of some element of $\mathcal{P}$. We give upper bounds on parameters of minimally non-$O(n^{d-1})$ $d$-dimensional 0-1 matrices, generalized from minimally nonlinear 0-1 matrices in two dimensions, and we show the existence of infinitely many minimally non-$O(n^{d-1})$ $d$-dimensional 0-1 matrices with all dimensions of length greater than $1$. For any positive integers $k,d$ and integer $r\in[0,d-1]$, we construct a family of $d$-dimensional 0-1 matrices with both extremal function and saturation function exactly $kn^r$ for sufficiently large $n$. We show that no family of $d$-dimensional 0-1 matrices has saturation function strictly between $O(1)$ and $Θ(n)$ and we construct a family of $d$-dimensional 0-1 matrices with bounded saturation function and extremal function $Ω(n^{d-ε})$ for any $ε>0$. Up to a constant multiplicative factor, we fully settle the problem of characterizing the semisaturation function of families of $d$-dimensional 0-1 matrices, which we prove to always be $Θ(n^r)$ for some integer $r\in[0,d-1]$. |
| title | Extremal bounds for pattern avoidance in multidimensional 0-1 matrices |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2306.11934 |