A generalised linear Ramsey graph construction

MaRDI QIDQ5026977zbMATH OpenFDO

Authors Fred Rowley

Publication date 8 February 2022

Full work available at URL https://arxiv.org/abs/1912.01164, http://ajc.maths.uq.edu.au/pdf/81/ajc_v81_p245.pdf

zbMATH Keywords

cyclic Ramsey graph colouringsGiraud's recursive formula

Mathematics Subject Classification ID

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

Abstract: A construction described by the current author in 2017 uses two linear `prototype' graphs to build a compound graph with Ramsey properties inherited from the prototypes. This paper describes a generalisation of that construction which has produced improved lower bounds in many cases for multicolour Ramsey numbers. The resulting graphs are linear, as before, and under certain specific conditions set out here, they can be cyclic. The mechanism of the new construction requires that the first prototype contains a triangle-free `template' in one colour, with defined properties. This paper shows that in the compound graph, clique numbers in the colours of the first prototype may exceed those of the prototype. However, it proves necessary only to test for a limited subset of the possible cliques using these colours, in order to evaluate the relevant clique numbers for the entire graph. Clique numbers in the colours of the second prototype are equal to those of that prototype. These attributes enable the efficient searching of a new family of graphs based on the `template' approach. It has also been found that there are a number of useful cases in which the clique numbers of the first prototype are not increased by the compounding process. As a result of this construction many lower bounds can be improved. The improvements include $R_4(5)ge4073$, $R_5(5)ge38914$, $R_3(6)ge1106$, $R_4(6)ge21302$, $R_4(7)ge84623$ and $R_3(9)ge14034$. It is also shown that $R_3(9)ge14081$ using a non-linear construction.

Recommendations

• Some further results in Ramsey graph construction
• scientific article; zbMATH DE number 6813638
• New lower bounds of classical Ramsey numbers R(6,12), R(6,14) and R(6,15)
• scientific article; zbMATH DE number 4043886
• More constructive lower bounds on classical Ramsey numbers

Cites work

• A problem of Schur and its generalizations
• Constructive lower bounds on classical multicolor Ramsey numbers
• scientific article; zbMATH DE number 6813638 (Why is no real title available?)
• scientific article; zbMATH DE number 3294608 (Why is no real title available?)
• scientific article; zbMATH DE number 3294609 (Why is no real title available?)
• Lower bounds for Ramsey numbers and association schemes
• Small Ramsey numbers
• Some further results in Ramsey graph construction
• Sum-free sets of integers

Cited in

(7)

• scientific article; zbMATH DE number 4043886 (Why is no real title available?)
• Search algorithm for Ramsey graphs by union of group orbits
• scientific article; zbMATH DE number 6813638 (Why is no real title available?)
• Some further results in Ramsey graph construction
• Modular generalizations of Schur numbers
• A dynamic version of Schur's problem for rotations on the unit interval
• Systematic generation of linear graphs - check and extension of the list of Uhlenbeck and Ford

This page was built for publication: A generalised linear Ramsey graph construction

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