اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدRandom sampling of colourings of sparse random graphs with a constant number of colours
99
0
0.0
(
0
)
نشر من قبل
Charilaos Efthymiou
تاريخ النشر
2008
مجال البحث
الهندسة المعلوماتية
والبحث باللغة
English
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
In this work we present a simple and efficient algorithm which, with high probability, provides an almost uniform sample from the set of proper k-colourings on an instance of a sparse random graph G(n,d/n), where k=k(d) is a sufficiently large constant. Our algorithm is not based on the Markov Chain Monte Carlo method (M.C.M.C.). Instead, we provide a novel proof of correctness of our Algorithm that is based on interesting spatial mixing properties of colourings of G(n,d/n). Our result improves upon previous results (based on M.C.M.C.) that required a number of colours growing unboundedly with n.
قيم البحث
اقرأ أيضاً
A lower bound is obtained for the greatest possible number of colors in an interval colourings of some regular graphs.
We prove that the number of Hamilton cycles in the random graph G(n,p) is n!p^n(1+o(1))^n a.a.s., provided that pgeq (ln n+ln ln n+omega(1))/n. Furthermore, we prove the hitting-time version of this statement, showing that in the random graph process
, the edge that creates a graph of minimum degree 2 creates (ln n/e)^n(1+o(1))^n Hamilton cycles a.a.s.
When we try to solve a system of linear equations, we can consider a simple iterative algorithm in which an equation including only one variable is chosen at each step, and the variable is fixed to the value satisfying the equation. The dynamics of t
his algorithm is captured by the peeling algorithm. Analyses of the peeling algorithm on random hypergraphs are required for many problems, e.g., the decoding threshold of low-density parity check codes, the inverting threshold of Goldreichs pseudorandom generator, the load threshold of cuckoo hashing, etc. In this work, we deal with random hypergraphs including superlinear number of hyperedges, and derive the tight threshold for the succeeding of the peeling algorithm. For the analysis, Wormalds method of differential equations, which is commonly used for analyses of the peeling algorithm on random hypergraph with linear number of hyperedges, cannot be used due to the superlinear number of hyperedges. A new method called the evolution of the moment generating function is proposed in this work.
For complete graphs and n-cubes bounds are found for the possible number of colours in an interval edge colourings.
We prove a $pre$-$asymptotic$ bound on the total variation distance between the uniform distribution over two types of undirected graphs with $n$ nodes. One distribution places a prescribed number of $k_T$ triangles and $k_S$ edges not involved in a
triangle independently and uniformly over all possibilities, and the other is the uniform distribution over simple graphs with exactly $k_T$ triangles and $k_S$ edges not involved in a triangle. As a corollary, for $k_S = o(n)$ and $k_T = o(n)$ as $n$ tends to infinity, the total variation distance tends to $0$, at a rate that is given explicitly. Our main tool is Chen-Stein Poisson approximation, hence our bounds are explicit for all finite values of the parameters.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
