A note on the Ratio and Inertia Bounds for the k k -Independence Number
Jun Gao, Jie Ma, Oleg Pikhurko · 2026
Read A note on the Ratio and Inertia Bounds for the k k -Independence Number by Jun Gao, Jie Ma, Oleg Pikhurko (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-01761.txt.
Introduction
Gao, Ma, and Pikhurko write a short graph theory note from 2026. Their topic is how to bound a graph power's free set. A graph power joins points that lie close in the graph. A free set holds no joined pair of points. Three past authors gave ratio and inertia bounds for this case.
The note weighs those bounds against two known tools. One tool is the theta function of Lovasz. The other is a weighted inertia bound. The authors show both tools do at least as well. The theta bound can be computed fast in graph size. That makes it a strong choice for this task.
Catalog record
| CREATOR | Jun Gao, Jie Ma, Oleg Pikhurko |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 17 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.01761
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A note on the Ratio and Inertia Bounds for the k k -Independence Number Jun Gao, Jie Ma, Oleg Pikhurko Abstract The k k -th power G k G^{k} of a graph G G is the graph on the same vertex set where the edge set consists of those pairs of distinct vertices of G G that are at distance at most k k from each other. A. Abiad, G. Coutinho, and M. A. Fiol [ On the k k -independence number of graphs , Discrete Mathematics 342 (2019), 2875–2885] proposed extensions of the classical ratio (for regular graphs) and inertia bounds to the independence number of G k G^{k} for k ⩾ 2 k\geqslant 2 . Continuing a line of work comparing these two parameters with other known bounds, we show that the ϑ \vartheta -function of L. Lovász and the weighted inertia bound of A. R. Calderbank and P. Frankl, when applied directly to G k G^{k} , perform at least as well as the ratio and inertia bounds of Abiad–Coutinho–Fiol, respectively. In particular, ϑ ( G k ) \vartheta(G^{k}) provides a polynomial-time computable upper bound on the independence number of G k G^{k} that is at least as strong as the ratio bound when the latter applies (i.e., when the graph G G is regular). 1 Introduction Let G=(V,E) be a graph with vertex set [n]:=\{1,\dots,n\} and k be a positive integer. The k -independence number of G , written \alpha_{k}(G) , is the size of a largest subset S\subseteq V such that any two distinct vertices of S are at distance greater than k in G . Equivalently, \alpha_{k}(G)=\alpha(G^{k}) is the standard independence number of the k -th power G^{k} of G , which is the graph on the same vertex set where two distinct vertices u and v are joined if they are at distance at most k in G . The parameter \alpha_{k} naturally arises in coding theory: in many natural ambient discrete metric spaces ({\mathcal{X}},d) one can build a graph G on {\mathcal{X}} such that an error correcting/detecting code of minimum distance k+1 corresponds exactly to a k -independent set in G . Abiad, Coutinho and Fiol [ 1 ] introduced two upper bounds on \alpha_{k}(G) , which are defined as follows. For a symmetric matrix X\in{\mathbbm{R}}^{n\times n} , let \lambda_{1}(X)\geqslant\dots\geqslant\lambda_{n}(X) denote its eigenvalues. Let A\in\{0,1\}^{n\times n} be the adjacency matrix of G . For p\in{\mathbbm{R}}_{k}[x] (that is, p is a real polynomial of degree at most k ), define W(p):=\max_{u\in V}(p(A))_{u,u},\qquad w(p):=\min_{u\in V}(p(A))_{u,u},\qquad\lambda(p):=\min_{i\in[2,n]}p(\lambda_{i}(A)). (1) Define {\mathcal{I}}_{k}(G) as the minimum over all p\in{\mathbbm{R}}_{k}[x] of {\mathcal{I}}^{p}_{k}(G):=\min\bigl\{\,|\{i:p(\lambda_{i}(A))\geqslant w(p)\}|,\ |\{i:p(\lambda_{i}(A))\leqslant W(p)\}|\,\bigr\}. Furthermore, if G is regular then define {\mathcal{R}}_{k}(G) as the infimum of {\mathcal{R}}^{p}_{k}(G):=n\cdot\frac{W(p)-\lambda(p)}{p(\lambda_{1}(A))-\lambda(p)}, (2) over all p\in{\mathbbm{R}}_{k}[x] with p(\lambda_{1}(A))>\lambda(p) . Theorem 1 (Inertia Bound, Abiad, Coutinho and Fiol [ 1 , Theorem 3.1] ) For every graph G and every integer k\geqslant 1 , it holds that \alpha_{k}(G)\leqslant{\mathcal{I}}_{k}(G) . Theorem 2 (Ratio Bound, Abiad, Coutinho and Fiol [ 1 , Theorem 3.2] ) For every regular graph G and every integer k\geqslant 1 , it holds that \alpha_{k}(G)\leqslant{\mathcal{R}}_{k}(G) . For k=1 , we get the well-known bounds on \alpha(G) due to Cvetković [ 5 ] and Hoffman [ 9 ] , see [ 1 ] . The functions {\mathcal{I}}_{k}(G) and {\mathcal{R}}_{k}(G) have been actively studied, including their comparisons with other known upper bounds on \alpha(G^{k}) for various families of graphs G . We refer the reader to the recent survey by Abiad, Peters and Ravagnani [ 2 ] . Both of these bounds require choosing a polynomial p . As discussed in [ 2 ] , this task (for either of the bounds) can be expressed as a mixed integer linear program (MILP). The number of Boolean variables in the provided MILPs is equal to the number of distinct eigenvalues of G which can potentially be as large as the number of vertices in G . So this MILP is not well suited for practical calculations. Very recently, Abiad, van Hoesel and Michaux [ 3 ] presented a polynomial-time (in |V(G)| ) algorithm for determining the value of the Inertia Bound {\mathcal{I}}_{k}(G) for every fixed k . For the Ratio Bound {\mathcal{R}}_{k}(G) , the original paper of Abiad, Coutinho and Fiol [ 1 ] provided a closed-form expression for k=2 . An analogous closed-form expression for k=3 was obtained by Kavi and Newman [ 12 ] . Fiol [ 7 ] showed that if the number of closed walks in G of any given length \ell\leqslant k and starting at a vertex u does not depend on u then {\mathcal{R}}_{k}(G) can be computed by a linear program. A polynomial-time algorithm that computes {\mathcal{R}}_{k}(G) in general is not known. A well-known parameter that upper bounds \alpha(G) is the \vartheta -function of Lovász [ 14 ] (who used it to determine the Shannon capacity of the 5-cycle). One of its equivalent definitions ( [ 14 , Theorem 3] ) which is convenient in this note is \vartheta(G):=\min\{\lambda_{1}(X):X\in\mathcal{L}_{G}\}, (3) where \mathcal{L}_{G} is the set of n\times n symmetric matrices X such that X_{i,j}=1 for every i,j\in[n] that are equal or non-adjacent in G . Here we show that the value of the \vartheta -function on G^{k} is at most the Ratio Bound {\mathcal{R}}_{k}(G) . Theorem 3 For every regular graph G and every integer k\geqslant 1 , it holds that \vartheta(G^{k})\leqslant{\mathcal{R}}_{k}(G) . As we already remarked, \vartheta(G)\geqslant\alpha(G) for any graph G . Also, \vartheta(G^{k}) can be computed in polynomial time in n on input (G,k) as a semi-definite program with one n\times n -matrix variable. Thus, \vartheta(G^{k}) provides a polynomially computable upper bound on \alpha_{k}(G) for an arbitrary graph G that, by Theorem 3 , performs at least as well as the Ratio Bound {\mathcal{R}}_{k}(G) of Abiad, Coutinho and Fiol [ 1 ] for regular graphs. Next, we compare the Inertia Bound {\mathcal{I}}_{k}(G) with the strengthening of Cvetković’ bound [ 5 ] that was introduced by Calderbank and Frankl [ 4 ] and is defined as follows. A weighted adjacency matrix of G is a symmetric matrix X\in{\mathbbm{R}}^{n\times n} such that X_{i,j}=0 whenever i,j\in[n] are equal or non-adjacent in G . Note that we allow arbitrary real values for adjacent indices i and j . The parameter n_{\geqslant 0}(G) , which we call the Weighted Inertia Bound here, is defined as the minimum number of non-negative eigenvalues attained by any such matrix: n_{\geqslant 0}(G):=\min_{X\in\mathcal{H}_{G}}\left|\{i\in[n]:\lambda_{i}(X)\geqslant 0\}\right|, where \mathcal{H}_{G} denotes the set of weighted adjacency matrices of G . It can be derived by eigenvalue interlacing that n_{\geqslant 0}(G)\geqslant\alpha(G) ; see [ 4 ] . Also, the classical bound by Cvetković [ 5 ] is obtained by allowing X to be A or -A only. It was verified that n_{\geqslant 0}(G)=\alpha(G) for all graphs with at most 10 vertices (see the discussion in [ 6 , Section 6] ), and Godsil [ 8 ] asked if equality always holds. However, Sinkovic [ 15 ] showed that there are graphs (namely the 17-vertex Paley graph or this graph minus a vertex) with n_{\geqslant 0}(G) strictly larger than \alpha(G) . Examples of graphs where these two parameters are strikingly far apart were constructed by Kwan and Wigderson [ 13 ] and