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)
- PAR ID:
- 10304580
- Publisher / Repository:
- Wiley Blackwell (John Wiley & Sons)
- Date Published:
- Journal Name:
- Random Structures & Algorithms
- Volume:
- 61
- Issue:
- 1
- ISSN:
- 1042-9832
- Format(s):
- Medium: X Size: p. 62-83
- Size(s):
- p. 62-83
- Sponsoring Org:
- National Science Foundation
More Like this
-
more » « less
Abstract -
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
Advancing the sparse regularity method, we prove one‐sided and two‐sided regularity inheritance lemmas for subgraphs of bijumbled graphs, improving on results of Conlon, Fox, and Zhao. These inheritance lemmas also imply improved
H ‐counting lemmas for subgraphs of bijumbled graphs, for someH . -
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 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).
