For any fixed $k$, we prove a lower bound on the $k$th largest modulus of an eigenvalue of the non-backtracking matrix $B$. Specifically, consider any deterministic or random family of graphs that converges locally to the unimodular Galton-Watson tree with root degree distribution $D$, and set $\kappa:=\mathbb E[D(D-1)]/\mathbb E[D]$. Given $\kappa>1$ and an exponential-moment bound on the empirical degree distributions, we show that $|\lambda_k(B)|\geq\sqrt{\kappa}-o_N(1)$, where $N$ is the number of vertices. When restricted to locally tree-like regular graphs, this recovers a well-known consequence of the Ihara-Bass formula. In the specific case where the graph is generated through the Erd\H{o}s-R\'{e}nyi model with expected degree $d>1$, this proves a conjecture of Bordenave, Lelarge, and Massouli\'{e}. To do this, we show that the normalized log-determinant of the Bethe-Hessian of the graph is bounded by that of the Bethe-Hessian of its local limit. This bound is violated if the eigenvalues of the non-backtracking matrix are too small. We establish this using an effective-conductance interpretation of the tree Green's function recursion.
We prove that, for every constant $\varepsilon>0$ and every function $f:\Sigma^n\to\{0, 1\}$, there is a coalition of $O(n/\sqrt{\log n})$ coordinates and a target output $b\in\{0, 1\}$ such that, after the remaining coordinates are sampled uniformly and independently, the coalition can choose its values to make the ou...
Alon, Bishnoi, Das and Neri constructed sequences of strong blocking sets in $(k-1)$-dimension projective space $P({\bf F}_q, k-1)$ with sizes at most $Cqk$, where $k$ goes to the infinity and $C$ is a fixed positive constant not depending on $q$, in their paper published in Transactions AMS, vol. 277, pp. 5389-5410, 2...
The permanent of an $n\times n$ $0/1$ matrix $A$ equals the number of perfect matchings in the bipartite graph with edges defined by $A$. Jerrum, Sinclair, and Vigoda (2004) presented an FPRAS for approximating the permanent of any nonnegative matrix using a novel simulated-annealing algorithm. The running time was imp...
Xiao-Yu Chen, Eric Vigoda, Xiong-Xin Yang· 2 citations
We present an exposition of an argument, discovered by GPT-6 Pro, that gives an optimal bound for the polynomial Littlewood-Offord problem. Namely, let $F$ be a degree-$d$ multilinear polynomial that contains $r$ degree-$d$ monomials involving disjoint sets of variables. Then, for i.i.d. Rademacher random variables $\x...
Assuming that $\zeta(s)$ has no nontrivial zero with $\mathrm{Re}\, s>7/8$, as asserted in a recent unrefereed preprint of OpenAI, we obtain $\Lambda \le 13963/100000 = 0.13963$ for the de Bruijn-Newman constant. A published Polymath boundary computation supplies a finite-region strip of half-width $1/5$. We derive an...
It is proved that, unless SETH fails, for any $\varepsilon, \delta>0$, $k \in \mathbb{N}$, and function $f\colon \mathbb{N}\to \mathbb{N}$, there is no data structure which maintains a $(2-\varepsilon)-approximation of the degeneracy of $G$ with initialization time and amortized update time.
Konrad Majewski, Michał Pilipczuk· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
