We establish the conjecture by de Klerk and Pasechnik (2002), claiming that the semidefinite bounds $\vartheta^{(r)}(G)(r\geq 0)$ for the stability number $\alpha(G)$ are exact at $r=\alpha(G)-1$, by exhibiting an explicit sum-of-squares certificate. This certificate allows us to recover a known characterization of the minimizers of the Motzkin-Straus formulation for $1/\alpha(G)$. Additionally, we give sum-of-squares copositivity certificates for the matrices satisfying the Hoffman--Pereira sign condition, a crucial condition for characterizing copositive matrices with $\{-1,0,1\}$ entries.
Motivated by the Merino--Welsh conjecture, we consider the smallest $c\ge0$, denoted by $c_*$, for which the inequality $T_M(c,0)T_M(0,c)\ge T_M(1,1)^2$ holds for every loopless and coloopless finite matroid $M$. The counterexamples constructed by Beke, Cs\'aji, Csikv\'ari, and Pituk [\emph{Adv. Math.} \textbf{446} (20...
Stone (Ph.D.\ thesis, Department of Operations Research, Stanford University, 1981) proved that every matrix in $U \cap Q_0$ is a $P_0$-matrix and conjectured that the same conclusion holds for the larger class $E_0^f \cap Q_0$ of fully semimonotone $Q_0$-matrices. Murthy and Parthasarathy [SIAM J.\ Matrix Anal.\ Appl....
Let $5\leq p_1<\cdots<p_r$ be primes, put $P=p_1\cdots p_r$, and let $g_P(2n)$ count the unordered decompositions $2n=h+k$ for which both summands are coprime to $6P$. We derive an explicit finite inclusion--exclusion formula for $g_P(2n)$ by parametrizing the admissible residue classes and combining the local restrict...
Let $M=\widetilde H^*(MO(2);\mathbb F_2)$ and let $\mathcal A(1)$ be the subalgebra of the mod $2$ Steenrod algebra generated by $\operatorname{Sq}^1$ and $\operatorname{Sq}^2$. In this work, we determine the quotient $\mathbb F_2\otimes_{\mathcal A(1)}M$ in every internal degree $h\geq0$, where internal degree $h$ cor...
The Bilu--Linial conjecture asks whether every finite $d$-regular graph with $d \geq 2$ admits an edge signing $\sigma$ whose signed adjacency matrix $A_\sigma$ has spectral radius at most $2\sqrt{d-1}$. We prove that every signing meeting the mixed-root condition $r_{A_\sigma}\leq\sqrt{2(d-1)}$ satisfies \[ \rho(A_\si...
We prove two main algorithmic results in spectral discrepancy. First, we give a deterministic polynomial-time rounding theorem for rational positive semidefinite matrices of arbitrary rank. The algorithm starts from any rational fractional signing and assigns one sign per original matrix. Its discrepancy is less than $...
A. Jadbabaie, A. Saberi, Suvrit Sra· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
