Back to Search Start Over

Unavoidable patterns in $2$-colorings of the complete bipartite graph

Authors :
Hansberg, Adriana
Ventura, Denae
Publication Year :
2024

Abstract

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.<br />Comment: Keywords: Ramsey, Zarankiewicz, unavoidable patterns, balanceable graph, omnitonal graph

Subjects

Subjects :
Mathematics - Combinatorics

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2407.08873
Document Type :
Working Paper