Optimization Tools for Computing Colorings of $[1,\cdots ,n]$ with Few Monochromatic Solutions on $3$-variable Linear Equations
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929566593843200 |
|---|---|
| author | De Loera, Jesús A. Ventura, Denae Wang, Liuyue Wesley, William J. |
| author_facet | De Loera, Jesús A. Ventura, Denae Wang, Liuyue Wesley, William J. |
| contents | A famous result in arithmetic Ramsey theory says that for many linear homogeneous equations $E$ there is a threshold value $R_k(E)$ (the Rado number of $E$) such that for any $k$-coloring of the integers in the interval $[1,n]$, with $n \ge R_k(E)$, there exists at least one monochromatic solution. But one can further ask, how many monochromatic solutions is the minimum possible in terms of $n$? Several authors have estimated this function before, here we offer new tools from integer and semidefinite optimization that help find either optimal or near optimal 2-colorings minimizing the number of monochromatic solutions of several families of 3-variable non-regular homogeneous linear equations. In the last part of the paper we further extend to three and more colors for the Schur equation, improving earlier work. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_21651 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Optimization Tools for Computing Colorings of $[1,\cdots ,n]$ with Few Monochromatic Solutions on $3$-variable Linear Equations De Loera, Jesús A. Ventura, Denae Wang, Liuyue Wesley, William J. Combinatorics A famous result in arithmetic Ramsey theory says that for many linear homogeneous equations $E$ there is a threshold value $R_k(E)$ (the Rado number of $E$) such that for any $k$-coloring of the integers in the interval $[1,n]$, with $n \ge R_k(E)$, there exists at least one monochromatic solution. But one can further ask, how many monochromatic solutions is the minimum possible in terms of $n$? Several authors have estimated this function before, here we offer new tools from integer and semidefinite optimization that help find either optimal or near optimal 2-colorings minimizing the number of monochromatic solutions of several families of 3-variable non-regular homogeneous linear equations. In the last part of the paper we further extend to three and more colors for the Schur equation, improving earlier work. |
| title | Optimization Tools for Computing Colorings of $[1,\cdots ,n]$ with Few Monochromatic Solutions on $3$-variable Linear Equations |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2410.21651 |