Difference Ramsey numbers and Issai numbers

DOI10.1006/AAMA.2000.0678MaRDI QIDQ1585507zbMATH OpenOpenAlexFDO

Authors Aaron Robertson

Publication date 16 November 2000

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/9904023

zbMATH Keywords

difference graphedge-coloringRamsey numberSchur numbers

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Ramsey theory (05D10)

Abstract: We present a recursive algorithm for finding good lower bounds for the classical Ramsey numbers. Using notions from this algorithm we then give some results for generalized Schur numbers, which we call Issai numbers.

Review text

An \(r\)-colored difference graph is a complete graph \(K_n\) with vertex set \(\{1,2,\dots, n\}\) and an \(r\)-edge-coloring constructed as follows: partition \(\{1,2,\dots, n-1\}\) into \(r\) classes \(C_1,C_2,\dots, C_r\), and assign color \(c_k\) to the edge \((i,j)\) if \(|i-j|\in C_k\). For each class \(C_k\) of an \(r\)-colored difference graph, let \(\kappa(C_k)\) be the size of a largest collection of vertices \(\{i_1,\dots, i_m\}\) so that \(|i_p,i_q|\in C_k\), for all \(1\leq p< p\leq m\). The author has produced an algorithm which, given \(h_1\) and \(h_2\), will find the maximum \(n\) and 2-partition of \(\{1,2,\dots, n-1\}\) which form a 2-colored difference graph with the property that \(\kappa(C_i)< h_i\), for \(i= 1,2\). This \(n\) is, of course, a lower bound on the Ramsey number \(R(h_1,h_2)\). The author also uses this algorithm to bound generalized Schur numbers.

Recommendations

• scientific article; zbMATH DE number 4110731
• scientific article; zbMATH DE number 19184
• Some Ramsey Schur Numbers
• The exact values of two-color Ramsey-Schur numbers \(RS(3,m)\)
• Some new Ramsey colorings

Cites work

• A survey of bounds for classical Ramsey numbers
• Combinatorial Relations and Chromatic Graphs
• scientific article; zbMATH DE number 3711961 (Why is no real title available?)
• scientific article; zbMATH DE number 3784892 (Why is no real title available?)
• scientific article; zbMATH DE number 1334622 (Why is no real title available?)
• scientific article; zbMATH DE number 637325 (Why is no real title available?)
• scientific article; zbMATH DE number 4120201 (Why is no real title available?)
• On the Ramsey numbers N(3,3,\dots ,3;2)
• On the Ramsey numbers R(3,8) and R(3,9)
• Some graph theoretic results associated with Ramsey's theorem

Cited in

(8)

• On Rado numbers for \(\Sigma^{m-1}_{i=1} a_{i}x_{i}= x_{m}\)
• Disjunctive Rado numbers
• On the \(n\)-color Rado number for the equation \(x_{1}+x_{2}+\cdots +x_{k}+c =x_{k+1}\)
• scientific article; zbMATH DE number 4110731 (Why is no real title available?)
• Two formulas of 2-color off-diagonal Rado numbers
• Off-diagonal generalized Schur numbers
• On some exact formulas for \(2\)-color off-diagonal Rado numbers
• On a modification of a problem of Bialostocki, Erdős, and Lefmann

This page was built for publication: Difference Ramsey numbers and Issai numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1585507)