On the Zero-Sum Ramsey Problem over Z₂^d

Autor(es)

Alvarado, Jose D. ; Coluccile, Lucas ; Parente, Roberto ; Souza, Victor

• Tipo de documento: Artigo Científico
• Fonte: LATIN 2022: THEORETICAL INFORMATICS; v. 13568, p. 15-pg., 2022-01-01.

Resumo

Let Gamma be a finite abelian group and let G be a graph. The zero-sum Ramsey number R(G, Gamma) is the least integer N (if it exists) such that, for every edge-colouring E(K-N) bar right arrow Gamma, one can find a copy G subset of K-N where the sum of the colours of the edges of G is zero. A large body of research on this problem has emerged in the past few decades, paying special attention to the case where Gamma is cyclic. In this work, we start a systematic study of R(G, Gamma) for groups Gamma of small exponent, in particular, Gamma = Z(2)(d). For the Klein group Z(2)(2), the smallest non-cyclic abelian group, we compute R(G, Z(2)(2)) for all odd forests G and show that R(G, Z(2)(2)) <= n + 2 for all forests G on at least 6 vertices. We also show that R(C-4, Z(2)(d)) = 2(d) + 1 for any d >= 2, and determine the order of magnitude of R(K-t,K-r, Z(2)(d)) as d -> infinity for all t, r. We also consider the related setting where the ambient graph K-N is substituted by the complete bipartite graph K-N,K-N. Denote the analogue bipartite zero-sum Ramsey number by B(G, Gamma). We show that B(C-4, Z(2)(d)) = 2(d) + 1 for all d >= 1 and B({C-4, C-6}, Z(2)(d)) = 2(d/2) + 1 for all even d >= 2. Additionally, we show that B(K-t,K-r, Z(2)(d)) and R(K-t,K-r, Z(2)(d)) have the same asymptotic behaviour as d -> infinity, for all t, r. Finally, we conjecture the value of B({C-4, . . . , C-2m}, Z(2)(d)) and provide the corresponding lower bound. (AU)

• Processo FAPESP: 20/10796-0 - Problemas estruturais em grafos aleatórios
• Beneficiário: José Diego Alvarado Morales
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Processo FAPESP: 20/08252-2 - Problemas extremais e probabilísticos em coloração de grafos
• Beneficiário: Lucas Colucci Cavalcante de Souza
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado