More Like this

1. Spectrum of random d ‐regular graphs up to the edge

   https://doi.org/10.1002/cpa.22176  

   Huang, Jiaoyang; Yau, Horng‐Tzer (September 2023, Communications on Pure and Applied Mathematics)

   Abstract Consider the normalized adjacency matrices of randomd‐regular graphs onNvertices with fixed degree . We prove that, with probability for any , the following two properties hold as provided that : (i) The eigenvalues are close to the classical eigenvalue locations given by the Kesten–McKay distribution. In particular, the extremal eigenvalues are concentrated with polynomial error bound inN, that is, . (ii) All eigenvectors of randomd‐regular graphs are completely delocalized. 

   more » « less
2. Local Access to Random Walks , January 2022

   Biswas, A.S.; Pyne, E.; Rubinfeld, R. (January 2022, Innovations in Theoretical Computer Science (ITCS 2022))

   For a graph G on n vertices, naively sampling the position of a random walk of at time t requires work Ω(t). We desire local access algorithms supporting positionG(t) queries, which return the position of a random walk from some fixed start vertex s at time t, where the joint distribution of returned positions is 1/ poly(n) close to those of a uniformly random walk in ℓ1 distance. We first give an algorithm for local access to random walks on a given undirected d-regular graph with eO( 1 1−λ √ n) runtime per query, where λ is the second-largest eigenvalue of the random walk matrix of the graph in absolute value. Since random d-regular graphs G(n, d) are expanders with high probability, this gives an eO(√ n) algorithm for a graph drawn from G(n, d) whp, which improves on the naive method for small numbers of queries. We then prove that no algorithm with subconstant error given probe access to an input d-regular graph can have runtime better than Ω(√ n/ log(n)) per query in expectation when the input graph is drawn from G(n, d), obtaining a nearly matching lower bound. We further show an Ω(n1/4) runtime per query lower bound even with an oblivious adversary (i.e. when the query sequence is fixed in advance). We then show that for families of graphs with additional group theoretic structure, dramatically better results can be achieved. We give local access to walks on small-degree abelian Cayley graphs, including cycles and hypercubes, with runtime polylog(n) per query. This also allows for efficient local access to walks on polylog degree expanders. We show that our techniques apply to graphs with high degree by extending or results to graphs constructed using the tensor product (giving fast local access to walks on degree nϵ graphs for any ϵ ∈ (0, 1]) and Cartesian product. 

   more » « less
3. Metastability of the Potts Ferromagnet on Random Regular Graphs

   https://doi.org/10.1007/s00220-023-04644-6  

   Coja-Oghlan, Amin; Galanis, Andreas; Goldberg, Leslie Ann; Ravelomanana, Jean Bernoulli; Štefankovič, Daniel; Vigoda, Eric (February 2023, Communications in Mathematical Physics)

   Abstract We study the performance of Markov chains for theq-state ferromagnetic Potts model on random regular graphs. While the cases of the grid and the complete graph are by now well-understood, the case of random regular graphs has resisted a detailed analysis and, in fact, even analysing the properties of the Potts distribution has remained elusive. It is conjectured that the performance of Markov chains is dictated by metastability phenomena, i.e., the presence of “phases” (clusters) in the sample space where Markov chains with local update rules, such as the Glauber dynamics, are bound to take exponential time to escape, and therefore cause slow mixing. The phases that are believed to drive these metastability phenomena in the case of the Potts model emerge as local, rather than global, maxima of the so-called Bethe functional, and previous approaches of analysing these phases based on optimisation arguments fall short of the task. Our first contribution is to detail the emergence of the two relevant phases for theq-state Potts model on thed-regular random graph for all integers$$q,d\ge 3$$ $q,d\ge 3$, and establish that for an interval of temperatures, delineated by the uniqueness and a broadcasting threshold on thed-regular tree, the two phases coexist (as possible metastable states). The proofs are based on a conceptual connection between spatial properties and the structure of the Potts distribution on the random regular graph, rather than complicated moment calculations. This significantly refines earlier results by Helmuth, Jenssen, and Perkins who had established phase coexistence for a small interval around the so-called ordered-disordered threshold (via different arguments) that applied for largeqand$$d\ge 5$$ $d\ge 5$. Based on our new structural understanding of the model, our second contribution is to obtain metastability results for two classical Markov chains for the Potts model. We first complement recent fast mixing results for Glauber dynamics by Blanca and Gheissari below the uniqueness threshold, by showing an exponential lower bound on the mixing time above the uniqueness threshold. Then, we obtain tight results even for the non-local and more elaborate Swendsen–Wang chain, where we establish slow mixing/metastability for the whole interval of temperatures where the chain is conjectured to mix slowly on the random regular graph. The key is to bound the conductance of the chains using a random graph “planting” argument combined with delicate bounds on random-graph percolation. 

   more » « less
4. Local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree

   https://doi.org/10.1002/rsa.21149  

   El Alaoui, Ahmed; Montanari, Andrea; Sellke, Mark (May 2023, Random Structures & Algorithms)

   Abstract Given a graph of degree over vertices, we consider the problem of computing a near maximum cut or a near minimum bisection in polynomial time. For graphs of girth , we develop a local message passing algorithm whose complexity is , and that achieves near optimal cut values among all ‐local algorithms. Focusing on max‐cut, the algorithm constructs a cut of value , where is the value of the Parisi formula from spin glass theory, and (subscripts indicate the asymptotic variables). Our result generalizes to locally treelike graphs, that is, graphs whose girth becomes after removing a small fraction of vertices. Earlier work established that, for random ‐regular graphs, the typical max‐cut value is . Therefore our algorithm is nearly optimal on such graphs. An immediate corollary of this result is that random regular graphs have nearly minimum max‐cut, and nearly maximum min‐bisection among all regular locally treelike graphs. This can be viewed as a combinatorial version of the near‐Ramanujan property of random regular graphs. 

   more » « less
5. Irregular subgraphs

   https://doi.org/10.1017/S0963548322000220  

   Alon, Noga; Wei, Fan (March 2023, Combinatorics, Probability and Computing)

   Abstract We suggest two related conjectures dealing with the existence of spanning irregular subgraphs of graphs. The first asserts that any $$d$$ -regular graph on $$n$$ vertices contains a spanning subgraph in which the number of vertices of each degree between $$0$$ and $$d$$ deviates from $$\frac{n}{d+1}$$ by at most $$2$$ . The second is that every graph on $$n$$ vertices with minimum degree $$\delta$$ contains a spanning subgraph in which the number of vertices of each degree does not exceed $$\frac{n}{\delta +1}+2$$ . Both conjectures remain open, but we prove several asymptotic relaxations for graphs with a large number of vertices $$n$$ . In particular we show that if $$d^3 \log n \leq o(n)$$ then every $$d$$ -regular graph with $$n$$ vertices contains a spanning subgraph in which the number of vertices of each degree between $$0$$ and $$d$$ is $$(1+o(1))\frac{n}{d+1}$$ . We also prove that any graph with $$n$$ vertices and minimum degree $$\delta$$ contains a spanning subgraph in which no degree is repeated more than $$(1+o(1))\frac{n}{\delta +1}+2$$ times. 

   more » « less