Positive Semidefiniteness of Matrices arising from Ramsey Theory

MaRDI QIDQ6285211zbMATH OpenFDO

Authors Joshua Cooper, Maxwell Forst

Publication date 5 April 2017

Mathematics Subject Classification ID

Combinatorial identities, bijective combinatorics (05A19) Ramsey theory (05D10) Matrices of integers (15B36)

Abstract: We resolve a conjecture of Cooper-Fenner-Purewal that a certain sequence of combinatorial matrices which can be used to bound small product-Ramsey numbers is positive semidefinite. Because the connection to Ramsey Theory involves solving quadratic integer programs associated to these matrices, this implies that there are relatively efficient algorithms for bounding said numbers. The proof is direct, and yields important structural information: we enumerate the eigenvalues and eigenspaces explicitly by employing hypergeometric identities.

This page was built for publication: Positive Semidefiniteness of Matrices arising from Ramsey Theory

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