Premium
The characterization of zero‐sum (mod 2) bipartite Ramsey numbers
Author(s) -
Caro Yair,
Yuster Raphael
Publication year - 1998
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199811)29:3<151::aid-jgt3>3.0.co;2-p
Subject(s) - bipartite graph , combinatorics , mathematics , dimension (graph theory) , discrete mathematics , graph , integer (computer science) , zero (linguistics) , complete bipartite graph , linguistics , philosophy , computer science , programming language
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 . © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 151–166, 1998