Minimizing Monochromatic Subgraphs of $K_{n,n}$
| Autor: | Gong, Charles |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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. Comment: 35 pages, 13 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|