We study several $k$-fold generalizations of the Lov\'asz theta function associated with the maximum $k$-colorable induced subgraph problem. The first is the Narasimhan--Manber parameter $\vartheta_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 $\varphi_k$ obtained from orthonormal representations of graphs and show the inequality $\varphi_k \leq \vartheta_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 $\vartheta_k$, $\varphi_k$, $\vartheta(G\square K_k)$, and related convexifications.
The Kahn--Lov\'{a}sz theorem gives a sharp upper bound on the number of perfect matchings in a graph in terms of its degree sequence, extending the classical Br\'{e}gman--Minc inequality for bipartite graphs. In this paper, we establish an asymptotically sharp extension of the Kahn--Lov\'{a}sz theorem to $F$-factors fo...
For a convex body $K \subset \mathbb R^d$ let $\Delta(K)$ be the expected distance between two independent uniform points of $K$, and let $\theta(K)$ be the corresponding expectation for normalized surface measure on $\partial K$. The Zaporozhets-Tarasov conjecture asserts $\Delta(K) \le \theta(K)$. We prove this conje...
Hypercube graphs are fundamental model spaces of positive curvature in discrete comparison geometry. Let $G$ be a finite, connected, simple, unweighted graph with Bakry--\'Emery curvature bounded below by $K$. We call $G$ Lichnerowicz-sharp if its first non-zero non-normalized Laplacian eigenvalue $\lambda_1=K$. We pro...
The celebrated conjecture of Lov\'asz from 1969 asks whether every connected vertex-transitive graph has a Hamiltonian path. Buci\'c, Christoph, Pokrovskiy and Steiner recently proved that every such graph on $n$ vertices contains a cycle of length $n^{2/3-o(1)}$. In this paper, we improve this bound to $n^{1-o(1)}$. O...
Let $S_k(G)$ denote the sum of the $k$ largest eigenvalues of a graph $G$. Motivated by the classical Hoffman program for the spectral radius of a graph, we investigate an additive Hoffman-type problem for $S_k(G)$. For each fixed $k\geq 2$ and sufficiently large order $n$, we characterize all connected graphs satisfyi...
Shao-Wei Sun, Meng-Yao Guo, Hong-Yan Ge et al.· 0 citations
In this paper, we resolve a 30-year-old conjecture of Spielman and Teng concerning the performance of the spectral partitioning method on graphs embeddable on an orientable surface of genus $g\ge 1$. In particular, for such a graph $G$ with $n$ vertices and maximum degree $\Delta$, we show that the second-smallest eige...
Benedikt Kolbe, Jack Spalding-Jamieson· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
