The characterization of zero-sum (mod 2) bipartite Ramsey numbers
✍ Scribed by Caro, Yair; Yuster, Raphael
- Publisher
- John Wiley and Sons
- Year
- 1998
- Tongue
- English
- Weight
- 134 KB
- Volume
- 29
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
Let G be a bipartite graph, with k|e(G). The zero-sum bipartite Ramsey number B(G, Z k ) is the smallest integer t such that in every Z k -coloring of the edges of K t,t , there is a zero-sum mod k copy of G in K t,t . In this article we give the first proof that determines B(G, Z 2 ) for all possible bipartite graphs G. In fact, we prove a much more general result from which B(G, Z 2 ) can be deduced: Let G be a (not necessarily connected) bipartite graph, which can be embedded in K n,n , and let F be a field. A function f : E(K n,n ) → F is called G-stable if every copy of G in K n,n has the same weight (the weight of a copy is the sum of the values of f on its edges). The set of all G-stable functions, denoted by U (G, K n,n , F ) is a linear space, which is called the K n,n uniformity space of G over F . We determine U (G, K n,n , F ) and its dimension, for all G, n and F . Utilizing this result in the case F = Z 2 , we can compute B(G, Z 2 ), for all bipartite graphs G.