اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدThe Ising antiferromagnet and max cut on random regular graphs
165
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
The Ising antiferromagnet is an important statistical physics model with close connections to the {sc Max Cut} problem. Combining spatial mixing arguments with the method of moments and the interpolation method, we pinpoint the replica symmetry breaking phase transition predicted by physicists. Additionally, we rigorously establish upper bounds on the {sc Max Cut} of random regular graphs predicted by Zdeborova and Boettcher [Journal of Statistical Mechanics 2010]. As an application we prove that the information-theoretic threshold of the disassortative stochastic block model on random regular graphs coincides with the Kesten-Stigum bound.
قيم البحث
اقرأ أيضاً
The max-flow and max-coflow problem on directed graphs is studied in the common generalization to regular spaces, i.e., to kernels or row spaces of totally unimodular matrices. Exhibiting a submodular structure of the family of paths within this mode
l we generalize the Edmonds-Karp variant of the classical Ford-Fulkerson method and show that the number of augmentations is quadratically bounded if augmentations are chosen along shortest possible augmenting paths.
Consider random $d$-regular graphs, i.e., random graphs such that there are exactly $d$ edges from each vertex for some $dge 3$. We study both the configuration model version of this graph, which has occasional multi-edges and self-loops, as well as
the simple version of it, which is a $d$-regular graph chosen uniformly at random from the collection of all $d$-regular graphs. In this paper, we discuss mixing times of Glauber dynamics for the Ising model with an external magnetic field on a random $d$-regular graph, both in the quenched as well as the annealed settings. Let $beta$ be the inverse temperature, $beta_c$ be the critical temperature and $B$ be the external magnetic field. Concerning the annealed measure, we show that for $beta > beta_c$ there exists $hat{B}_c(beta)in (0,infty)$ such that the model is metastable (i.e., the mixing time is exponential in the graph size $n$) when $beta> beta_c$ and $0 leq B < hat{B}_c(beta)$, whereas it exhibits the cut-off phenomenon at $c_star n log n$ with a window of order $n$ when $beta < beta_c$ or $beta > beta_c$ and $B>hat{B}_c(beta)$. Interestingly, $hat{B}_c(beta)$ coincides with the critical external field of the Ising model on the $d$-ary tree (namely, above which the model has a unique Gibbs measure). Concerning the quenched measure, we show that there exists $B_c(beta)$ with $B_c(beta) leq hat{B}_c(beta)$ such that for $beta> beta_c$, the mixing time is at least exponential along some subsequence $(n_k)_{kgeq 1}$ when $0 leq B < B_c(beta)$, whereas it is less than or equal to $Cnlog n$ when $B>hat{B}_c(beta)$. The quenched results also hold for the model conditioned on simplicity, for the annealed results this is unclear.
Switches are operations which make local changes to the edges of a graph, usually with the aim of preserving the vertex degrees. We study a restricted set of switches, called triangle switches. Each triangle switch creates or deletes at least one tri
angle. Triangle switches can be used to define Markov chains which generate graphs with a given degree sequence and with many more triangles (3-cycles) than is typical in a uniformly random graph with the same degrees. We show that the set of triangle switches connects the set of all $d$-regular graphs on $n$ vertices, for all $dgeq 3$. Hence, any Markov chain which assigns positive probability to all triangle switches is irreducible on these graphs. We also investigate this question for 2-regular graphs.
We study $2k$-factors in $(2r+1)$-regular graphs. Hanson, Loten, and Toft proved that every $(2r+1)$-regular graph with at most $2r$ cut-edges has a $2$-factor. We generalize their result by proving for $kle(2r+1)/3$ that every $(2r+1)$-regular graph
with at most $2r-3(k-1)$ cut-edges has a $2k$-factor. Both the restriction on $k$ and the restriction on the number of cut-edges are sharp. We characterize the graphs that have exactly $2r-3(k-1)+1$ cut-edges but no $2k$-factor. For $k>(2r+1)/3$, there are graphs without cut-edges that have no $2k$-factor, as studied by Bollobas, Saito, and Wormald.
Minimum Bisection denotes the NP-hard problem to partition the vertex set of a graph into two sets of equal sizes while minimizing the width of the bisection, which is defined as the number of edges between these two sets. We first consider this prob
lem for trees and prove that the minimum bisection width of every tree $T$ on $n$ vertices satisfies $MinBis(T) leq 8 n Delta(T) / diam(T)$. Second, we generalize this to arbitrary graphs with a given tree decomposition $(T,X)$ and give an upper bound on the minimum bisection width that depends on the structure of $(T,X)$. Moreover, we show that a bisection satisfying our general bound can be computed in time proportional to the encoding length of the tree decomposition when the latter is provided as input.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
