Back to Search
Start Over
Unavoidable patterns in $2$-colorings of the complete bipartite graph
- 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 :
- Mathematics - Combinatorics
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2407.08873
- Document Type :
- Working Paper