Linear programming bounds for cliques in Paley graphs

Mark Magsino; Dustin G. Mixon; Hans Parshall

doi:10.1117/12.2526801

9 September 2019 Linear programming bounds for cliques in Paley graphs

Mark Magsino, Dustin G. Mixon, Hans Parshall

Proceedings Volume 11138, Wavelets and Sparsity XVIII; 111381H (2019) https://doi.org/10.1117/12.2526801
Event: SPIE Optical Engineering + Applications, 2019, San Diego, California, United States

Abstract

The Lovász theta number is a semidefinite programming bound on the clique number of (the complement of) a given graph. Given a vertex-transitive graph, every vertex belongs to a maximal clique, and so one can instead apply this semidefinite programming bound to the local graph. In the case of the Paley graph, the local graph is circulant, and so this bound reduces to a linear programming bound, allowing for fast computations. Impressively, the value of this program with Schrijver's nonnegativity constraint rivals the state-of-the-art closed-form bound recently proved by Hanson and Petridis. We conjecture that this linear programming bound improves on the Hanson{Petridis bound in infinitely often, and we derive the dual program to facilitate proving this conjecture.

Citation Download Citation

Mark Magsino, Dustin G. Mixon, and Hans Parshall "Linear programming bounds for cliques in Paley graphs", Proc. SPIE 11138, Wavelets and Sparsity XVIII, 111381H (9 September 2019); https://doi.org/10.1117/12.2526801

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available