Let $\lambda_k(G)$ be the $k$th eigenvalue of the normalized Laplacian of a finite undirected weighted graph, and let $\rho_G(k)$ be the minimum possible maximum conductance of $k$ disjoint nonempty vertex sets. We prove \[ \rho_G(k)\le C[1+\log(k+1)]^5\sqrt{\lambda_k(G)} \] for an absolute constant $C$. The construction gives exactly $k$ sets and a bound in terms of $\lambda_k(G)$, with all boundaries and volumes measured in the original graph. More strongly, it yields $k$ nonnegative functions with pairwise disjoint supports and Rayleigh quotients $O([1+\log(k+1)]^{10}\lambda_k(G))$. The proof uses independent local cutoffs whose lost covariance is controlled by conditioning on the loss along a principal direction in each cell. A regularized spectral embedding bounds cutoff energy on the entire original low eigenspace, while an adaptive construction reduces the remaining coefficient dimension by at least half at each stage. A dimension argument then converts almost rank-one local covariances into exactly $k$ scalar witnesses.
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
Let $G$ be a connected graph, and let $\lambda_1(G)>\lambda_2(G)$ denote its two largest adjacency eigenvalues. The spectral gap of $G$ is defined as the difference $\lambda_1(G) - \lambda_2(G)$. For integers $r\geq 2$ and $s\geq 0$, the double kite $DK(r,s)$ is formed by taking two vertex-disjoint copies of the comple...
Let $G$ be a graph of order $n$ with the adjacency eigenvalues $\lambda_1(G) \geq \dots \geq \lambda_n(G) $. Let $c(v)$ denote the maximum order of a clique containing vertex $v$. We prove the vertex-localized positive square-energy inequality \[ \sqrt{s_+(G)} \leq \sum_{v\in V}\left(1-\frac1{c(v)}\right), \] where \[...
Abhay Jayarajan, M. Kannan, Shivaramakrishna Pragada et al.· 0 citations
Fix $k\ge 3$, and let $f_k(N)$ be the largest harmonic sum of a subset of $[N]$ containing no $k$ distinct integers with a common pairwise least common multiple. We prove that $f_k(N)=(\log N)^{\gamma_k+o(1)}$ for a well-defined exponent $\gamma_k\in(0,1]$. Following the weighted-pressure idea of Chojecki, we give a se...
For a fixed integer $k\ge 2$, let $kK_3$ denote the vertex-disjoint union of $k$ triangles. A recent fixed-size spectral theorem of Das and Yamini asserts that, for all sufficiently large $m$, every $kK_3$-free graph $G$ of size $m$ satisfies $\lambda(G)\le (k-1)+\sqrt{m-k(k-1)},$ and equality holds if and only if $(2k...
Let $G$ be a simple graph with maximum degree $\Delta\ge 3$, and let $P(G,k)$ denote its chromatic polynomial. For each positive integer $k$, the list-color function $P_{\ell}(G,k)$ is the minimum number of $L$-colorings of $G$ over all $k$-assignments $L$. In this paper, we prove that $P_{\ell}(G,k)=P(G,k)$ for every...
Mei-Qiao Zhang, Feng-Ming Dong· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.