اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدTangled Paths: A Random Graph Model from Mallows Permutations
141
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We introduce the random graph $mathcal{P}(n,q)$ which results from taking the union of two paths of length $ngeq 1$, where the vertices of one of the paths have been relabelled according to a Mallows permutation with real parameter $0<q(n)leq 1$. This random graph model, the tangled path, goes through an evolution: if $q$ is close to $0$ the graph bears resemblance to a path and as $q$ tends to $1$ it becomes an expander. In an effort to understand the evolution of $mathcal{P}(n,q)$ we determine the treewidth and cutwidth of $mathcal{P}(n,q)$ up to log factors for all $q$. We also show that the property of having a separator of size one has a sharp threshold. In addition, we prove bounds on the diameter, and vertex isoperimetric number for specific values of $q$.
قيم البحث
اقرأ أيضاً
We define and study a model of winding for non-colliding particles in finite trees. We prove that the asymptotic behavior of this statistic satisfies a central limiting theorem, analogous to similar results on winding of bounded particles in the plan
e. We also propose certain natural open questions and conjectures, whose confirmation would provide new insights on configuration spaces of trees.
The behavior of a certain random growth process is analyzed on arbitrary regular and non-regular graphs. Our argument is based on the Expander Mixing Lemma, which entails that the results are strongest for Ramanujan graphs, which asymptotically maxim
ize the spectral gap. Further, we consider ErdH{o}s--Renyi random graphs and compare our theoretical results with computational experiments on flip graphs of point configurations. The latter is relevant for enumerating triangulations.
We determine the rank of a random matrix over an arbitrary field with prescribed numbers of non-zero entries in each row and column. As an application we obtain a formula for the rate of low-density parity check codes. This formula vindicates a conje
cture of Lelarge (2013). The proofs are based on coupling arguments and a novel random perturbation, applicable to any matrix, that diminishes the number of short linear relations.
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 break
ing 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.
A notion of $t$-designs in the symmetric group on $n$ letters was introduced by Godsil in 1988. In particular $t$-transitive sets of permutations form a $t$-design. We derive special lower bounds for $t=1$ and $t=2$ by a power moment method. For gene
ral $n,t$ we give a %linear programming lower bound . For $nge 4$ and $t=2,$ this bound is strong enough to show a lower bound on the size of such $t$-designs of $n(n-1)dots (n-t+1),$ which is best possible when sharply $t$-transitive sets of permutations exist. This shows, in particular, that tight $2$-designs do not exist.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
