Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2410.19076 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _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 |