Unavoidable patterns in $2$-colorings of the complete bipartite graph
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929418307371008 |
|---|---|
| author | Hansberg, Adriana Ventura, Denae |
| author_facet | Hansberg, Adriana Ventura, Denae |
| contents | We determine the colored patterns that appear in any $2$-edge coloring of $K_{n,n}$, with $n$ large enough and with sufficient edges in each color. We prove the existence of a positive integer $z_2$ such that any $2$-edge coloring of $K_{n,n}$ with at least $z_2$ edges in each color contains at least one of these patterns. We give a general upper bound for $z_2$ and prove its tightness for some cases. We define the concepts of bipartite $r$-tonality and bipartite omnitonality using the complete bipartite graph as a base graph. We provide a characterization for bipartite $r$-tonal graphs and prove that every tree is bipartite omnitonal. Finally, we define the bipartite balancing number and provide the exact bipartite balancing number for paths and stars. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_08873 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Unavoidable patterns in $2$-colorings of the complete bipartite graph Hansberg, Adriana Ventura, Denae Combinatorics We determine the colored patterns that appear in any $2$-edge coloring of $K_{n,n}$, with $n$ large enough and with sufficient edges in each color. We prove the existence of a positive integer $z_2$ such that any $2$-edge coloring of $K_{n,n}$ with at least $z_2$ edges in each color contains at least one of these patterns. We give a general upper bound for $z_2$ and prove its tightness for some cases. We define the concepts of bipartite $r$-tonality and bipartite omnitonality using the complete bipartite graph as a base graph. We provide a characterization for bipartite $r$-tonal graphs and prove that every tree is bipartite omnitonal. Finally, we define the bipartite balancing number and provide the exact bipartite balancing number for paths and stars. |
| title | Unavoidable patterns in $2$-colorings of the complete bipartite graph |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2407.08873 |