Linear programming bounds for cliques in Paley graphs

Mark Magsino, Dustin G. Mixon, Hans ParshallarXiv 2019 · OpenReview

TL;DR

This paper presents a novel approach to bound the clique number of Paley graphs by reformulating a semidefinite programming problem (the Lovász theta number) into a linear programming problem. This new method yields bounds that are competitive with, and sometimes improve upon, the best known theoretical bounds, offering a more computationally tractable way to explore these important graph structures.

What Problem Does This Paper Address?

The paper tackles the challenge of determining the clique number, denoted $w(G)$, for Paley graphs, a family of graphs with significant applications in areas like compressed sensing. Specifically, finding tight upper bounds for $w(G_p)$ (the clique number of a Paley graph with $p$ vertices) as $p$ grows is a notoriously difficult open problem. While theoretical bounds exist, they are often difficult to compute or not as sharp as desired. The authors aim to provide a more efficient and potentially tighter method for bounding $w(G_p)$ by leveraging the structure of Paley graphs.

Methods

The core of the paper's contribution lies in transforming a semidefinite programming (SDP) formulation for bounding clique numbers into a linear programming (LP) problem. The Lovász $\theta$ number, $VL(G)$, is a well-known SDP bound for $w(G)$. For vertex-transitive graphs like Paley graphs, the authors consider a subgraph called the "local graph" ($L_p$), which is circulant. This circulant structure allows the SDP to be reduced to an LP. They introduce two LP formulations: one based on $VL(G)$ and another, $VLS(G)$, which incorporates an additional nonnegativity constraint (Schrijver's constraint). The paper then demonstrates how to efficiently compute these LP bounds for Paley graphs, leveraging the Fast Fourier Transform (FFT) for computational speed. Finally, they derive the dual program of the $VLS(G)$ formulation, which is crucial for potentially proving new theoretical bounds.

Datasets

Not discussed in the paper. The paper focuses on theoretical bounds and computational experiments on existing mathematical objects (Paley graphs for various primes $p$).

Key Insights and Ideas

  • Paley Graphs as Circulant Subgraphs: The key insight is that the "local graph" of a Paley graph, which is relevant for bounding its clique number, is a circulant graph. This structural property is what enables the reduction from SDP to LP.
  • LP as a Practical Tool: The paper shows that by reformulating the problem as an LP, one can obtain numerical bounds for $w(G_p)$ much more efficiently than with the original SDP. This opens the door for extensive computational exploration.
  • Schrijver's Constraint: The introduction of Schrijver's nonnegativity constraint ($VLS(G)$) leads to bounds that are often tighter than those obtained from the standard Lovász $\theta$ number ($VL(G)$).
  • Dual Program for Theoretical Proofs: Deriving the dual program of the $VLS(G)$ LP is a significant step. It provides a framework for constructing "magic functions" that could potentially be used to prove new, stronger theoretical upper bounds on $w(G_p)$.
  • Conjecture on Bound Improvement: The authors conjecture that their LP-based bounds will improve upon the state-of-the-art theoretical bound (Hanson-Petridis) for infinitely many primes.

Key Results

  • The paper provides efficient linear programming formulations for computing $VL(L_p)$ and $VLS(L_p)$, where $L_p$ is the local graph of the Paley graph $G_p$.
  • Computational experiments for primes $p < 3000$ show that the LP-based bounds ($L(p)$ and $LS(p)$) frequently match or improve upon the best known theoretical upper bound, $HP(p)$.
  • Specifically, for 17 primes $p < 3000$, the $LS(p)$ bound is strictly less than the floor of the $HP(p)$ bound, indicating a potential improvement.
  • The paper successfully computes $L(809)$ in under 20 seconds using their LP approach, a task that took hours with previous SDP methods.
  • The dual program for $VLS(G)$ is derived, offering a path towards proving new theoretical bounds.

Limitations and Future Work

  • Computational Cost for Large Primes: While significantly faster than SDP, computing these LP bounds for extremely large primes might still be computationally intensive. The authors suggest leveraging the Fast Fourier Transform (FFT) to further speed up computations.
  • Proving the Conjecture: The primary future work direction is to use the derived dual program and appropriate number-theoretic functions to prove Conjecture 6: that $LS(p) < \lfloor HP(p) \rfloor$ for infinitely many primes $p$. This would establish a new theoretical improvement over existing bounds.
  • Exploring Other Graph Classes: The methods developed could potentially be applied to other classes of vertex-transitive graphs.

Summary updated

Abstract

The Lov\'{a}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 infinitely often, and we derive the dual program to facilitate proving this conjecture.
BibTeX
@misc{magsino2019linear,
  author = {Mark Magsino and Dustin G. Mixon and Hans Parshall},
  title = {{Linear programming bounds for cliques in Paley graphs}},
  year = {2019},
  eprint = {1907.05971},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1907.05971},
}
Figure