Minimizing Monochromatic Subgraphs of $K_{n,n}$
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908840048459776 |
|---|---|
| author | Gong, Charles |
| author_facet | Gong, Charles |
| contents | Given any $r$-edge coloring of $K_{n,n}$, how large is the maximum (over all $r$ colors) sized monochromatic subgraph guaranteed to be? We give answers to this problem for $r \leq 8$, when $r$ is a perfect square, and when $r$ is one less than a perfect square all up to a constant additive term that depends on $r$. We give a lower bound on this quantity that holds for all $r$ and is sharp when $r$ is a perfect square up to a constant additive term that depends on $r$. Finally, we give a construction for all $r$ which provides an upper bound on this quantity up to a constant additive term that depends on $r$, and which we conjecture is also a lower bound. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_19076 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Minimizing Monochromatic Subgraphs of $K_{n,n}$ Gong, Charles Combinatorics Given any $r$-edge coloring of $K_{n,n}$, how large is the maximum (over all $r$ colors) sized monochromatic subgraph guaranteed to be? We give answers to this problem for $r \leq 8$, when $r$ is a perfect square, and when $r$ is one less than a perfect square all up to a constant additive term that depends on $r$. We give a lower bound on this quantity that holds for all $r$ and is sharp when $r$ is a perfect square up to a constant additive term that depends on $r$. Finally, we give a construction for all $r$ which provides an upper bound on this quantity up to a constant additive term that depends on $r$, and which we conjecture is also a lower bound. |
| title | Minimizing Monochromatic Subgraphs of $K_{n,n}$ |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2410.19076 |