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.
We give a unified proof of algorithmic weak and Szemerédi regularity lemmas for several well‐studied classes of sparse graphs, for which only weak regularity lemmas were previously known. These include core‐dense graphs, low threshold rank graphs, and (a version of)
- NSF-PAR ID:
- 10304580
- Publisher / Repository:
- Wiley Blackwell (John Wiley & Sons)
- Date Published:
- Journal Name:
- Random Structures & Algorithms
- Volume:
- 61
- Issue:
- 1
- ISSN:
- 1042-9832
- Page Range / eLocation ID:
- p. 62-83
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
more » « less
Abstract -
more » « less
Efficient algorithms for approximate counting and sampling in spin systems typically apply in the so‐called high‐temperature regime, where the interaction between neighboring spins is “weak.” Instead, recent work of Jenssen, Keevash, and Perkins yields polynomial‐time algorithms in the low‐temperature regime on bounded‐degree (bipartite) expander graphs using polymer models and the cluster expansion. In order to speed up these algorithms (so the exponent in the run time does not depend on the degree bound) we present a Markov chain for polymer models and show that it is rapidly mixing under exponential decay of polymer weights. This yields, for example, an
‐time sampling algorithm for the low‐temperature ferromagnetic Potts model on bounded‐degree expander graphs. Combining our results for the hard‐core and Potts models with Markov chain comparison tools, we obtain polynomial mixing time for Glauber dynamics restricted to appropriate portions of the state space. -
more » « less
Abstract Consider the upper tail probability that the homomorphism count of a fixed graph
H within a large sparse random graphG n exceeds its expected value by a fixed factor. Going beyond the Erdős–Rényi model, we establish here explicit, sharp upper tail decay rates for sparse random d n ‐regular graphs (providedH has a regular 2‐core), and for sparse uniform random graphs. We further deal with joint upper tail probabilities for homomorphism counts of multiple graphs(extending the known results for ), and for inhomogeneous graph ensembles (such as the stochastic block model), we bound the upper tail probability by a variational problem analogous to the one that determines its decay rate in the case of sparse Erdős–Rényi graphs. -
more » « less
Abstract In this paper we provide an algorithm that generates a graph with given degree sequence uniformly at random. Provided that
, where is the maximal degree and m is the number of edges, the algorithm runs in expected timeO (m ). Our algorithm significantly improves the previously most efficient uniform sampler, which runs in expected timefor the same family of degree sequences. Our method uses a novel ingredient which progressively relaxes restrictions on an object being generated uniformly at random, and we use this to give fast algorithms for uniform sampling of graphs with other degree sequences as well. Using the same method, we also obtain algorithms with expected run time which is (i) linear for power‐law degree sequences in cases where the previous best was O (n 4.081), and (ii)O (nd +d 4) ford ‐regular graphs when, where the previous best was O (nd 3). -
more » « less
Abstract We consider the mapping properties of the integral operator arising in nonlocal slender body theory (SBT) for the model geometry of a straight, periodic filament. It is well known that the classical singular SBT integral operator suffers from high wavenumber instabilities, making it unsuitable for approximating the
slender body inverse problem , where the fiber velocity is prescribed and the integral operator must be inverted to find the force density along the fiber. Regularizations of the integral operator must therefore be used instead. Here, we consider two regularization methods: spectral truncation and the‐regularization of Tornberg and Shelley (2004). We compare the mapping properties of these approximations to the underlying partial differential equation (PDE) solution, which for the inverse problem is simply the Stokes Dirichlet problem with data constrained to be constant on cross sections. For the straight‐but‐periodic fiber with constant radius , we explicitly calculate the spectrum of the operator mapping fiber velocity to force for both the PDE and the approximations. We prove that the spectrum of the original SBT operator agrees closely with the PDE operator at low wavenumbers but differs at high frequencies, allowing us to define a truncated approximation with a wavenumber cutoff . For both the truncated and ‐regularized approximations, we obtain rigorous ‐based convergence to the PDE solution as : A fiber velocity with regularity gives convergence, while a fiber velocity with at least regularity yields convergence. Moreover, we determine the dependence of the ‐regularized error estimate on the regularization parameter .
