On some k-fold generalizations of Lovász theta and their sandwich theorems
Abstract
We study several k-fold generalizations of the Lovász theta function associated with the maximum k-colorable induced subgraph problem. The first is the Narasimhan--Manber parameter ϑk. We prove that, for graphs whose adjacency matrix belongs to a homogeneous partially coherent algebra, this parameter is recovered by the theta number of the Cartesian product with the complete graph on k vertices. This class includes distance-regular and $1$-walk-regular graphs, and thus our result generalizes a theorem by Sinjorgo and Sotirov (2022) for graphs that are vertex- and edge-transitive. We introduce a new parameter φk obtained from orthonormal representations of graphs and show the inequality φk ≤ ϑk. For both parameters, we study the smallest k for which the parameter is equal to the number of vertices; these saturation parameters yield lower bounds on the chromatic number. We determine which vertex-weighted versions of these parameters are gauges, and discuss a natural definition for the k-fold theta body of a graph. We conclude with open questions comparing ϑk, φk, ϑ(G□ Kk), and related convexifications.
Related
- Sharp Lovasz-Theta Bounds on Random Graphs
- A Bernstein Theorem for the Self-Shrinking J-Equation and Some Generalizations
- Some generalizations of Oort's conjecture
- Some vanishing theorems on (p,q) double form and curvature operator of the second kind
- Orbit span of a design and some saturation theorems in commutative Schurian association schemes
BibTeX
@misc{silva2026some,
title = {{On some k-fold generalizations of Lovász theta and their sandwich theorems}},
author = {Marcel K Carli Silva and Gabriel Coutinho and Thiago Oliveira and Levent Tunçel},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.06312},
eprint = {2609.06312},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.06312},
}
RIS
TY - UNPB
TI - On some k-fold generalizations of Lovász theta and their sandwich theorems
AU - Marcel K Carli Silva
AU - Gabriel Coutinho
AU - Thiago Oliveira
AU - Levent Tunçel
PY - 2026
DA - 2026/09/06
PB - arXiv
DO - 10.48550/arxiv.2609.06312
UR - https://arxiv.org/abs/2609.06312
AB - We study several k-fold generalizations of the Lovász theta function associated with the maximum k-colorable induced subgraph problem. The first is the Narasimhan--Manber parameter ϑ_k. We prove that, for graphs whose adjacency matrix belongs to a homogeneous partially coherent algebra, this parameter is recovered by the theta number of the Cartesian product with the complete graph on k vertices. This class includes distance-regular and $1$-walk-regular graphs, and thus our result generalizes a theorem by Sinjorgo and Sotirov (2022) for graphs that are vertex- and edge-transitive. We introduce a new parameter φ_k obtained from orthonormal representations of graphs and show the inequality φ_k ≤ ϑ_k. For both parameters, we study the smallest k for which the parameter is equal to the number of vertices; these saturation parameters yield lower bounds on the chromatic number. We determine which vertex-weighted versions of these parameters are gauges, and discuss a natural definition for the k-fold theta body of a graph. We conclude with open questions comparing ϑ_k, φ_k, ϑ(G□ K_k), and related convexifications.
ER -