Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userProof of Aldous spectral gap conjecture
259
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Aldous spectral gap conjecture asserts that on any graph the random walk process and the random transposition (or interchange) process have the same spectral gap. We prove the conjecture using a recursive strategy. The approach is a natural extension of the method already used to prove the validity of the conjecture on trees. The novelty is an idea based on electric network reduction, which reduces the problem to the proof of an explicit inequality for a random transposition operator involving both positive and negative rates. The proof of the latter inequality uses suitable coset decompositions of the associated matrices on permutations.
rate research
Read More
Let $S_n$ denote the symmetric group on $n$ elements, and $Sigmasubseteq S_{n}$ a symmetric subset of permutations. Aldous spectral gap conjecture, proved by Caputo, Liggett and Richthammer [arXiv:0906.1238], states that if $Sigma$ is a set of transpositions, then the second eigenvalue of the Cayley graph $mathrm{Cay}left(S_{n},Sigmaright)$ is identical to the second eigenvalue of the Schreier graph on $n$ vertices depicting the action of $S_{n}$ on $left{ 1,ldots,nright}$. Inspired by this seminal result, we study similar questions for other types of sets in $S_{n}$. Specifically, we consider normal sets: sets that are invariant under conjugation. Relying on character bounds due to Larsen and Shalev [2008], we show that for large enough $n$, if $Sigmasubset S_{n}$ is a full conjugacy class, then the second eigenvalue of $mathrm{Cay}left(S_{n},Sigmaright)$ is roughly identical to the second eigenvalue of the Schreier graph depicting the action of $S_{n}$ on ordered $4$-tuples of elements from $left{ 1,ldots,nright}$. We further show that this type of result does not hold when $Sigma$ is an arbitrary normal set, but a slightly weaker one does hold. We state a conjecture in the same spirit regarding an arbitrary symmetric set $Sigmasubset S_{n}$, which yields surprisingly strong consequences.
Aldous [(2007) Preprint] defined a gossip process in which space is a discrete $Ntimes N$ torus, and the state of the process at time $t$ is the set of individuals who know the information. Information spreads from a site to its nearest neighbors at rate 1/4 each and at rate $N^{-alpha}$ to a site chosen at random from the torus. We will be interested in the case in which $alpha<3$, where the long range transmission significantly accelerates the time at which everyone knows the information. We prove three results that precisely describe the spread of information in a slightly simplified model on the real torus. The time until everyone knows the information is asymptotically $T=(2-2alpha/3)N^{alpha/3}log N$. If $rho_s$ is the fraction of the population who know the information at time $s$ and $varepsilon$ is small then, for large $N$, the time until $rho_s$ reaches $varepsilon$ is $T(varepsilon)approx T+N^{alpha/3}log (3varepsilon /M)$, where $M$ is a random variable determined by the early spread of the information. The value of $rho_s$ at time $s=T(1/3)+tN^{alpha/3}$ is almost a deterministic function $h(t)$ which satisfies an odd looking integro-differential equation. The last result confirms a heuristic calculation of Aldous.
An extension of the Gaussian correlation conjecture (GCC) is proved for multivariate gamma distributions (in the sense of Krishnamoorthy and Parthasarathy). The classical GCC for Gaussian probability measures is obtained by the special case with one degree of freedom.
A typical decomposition question asks whether the edges of some graph $G$ can be partitioned into disjoint copies of another graph $H$. One of the oldest and best known conjectures in this area, posed by Ringel in 1963, concerns the decomposition of complete graphs into edge-disjoint copies of a tree. It says that any tree with $n$ edges packs $2n+1$ times into the complete graph $K_{2n+1}$. In this paper, we prove this conjecture for large $n$.
Consider the Aldous Markov chain on the space of rooted binary trees with $n$ labeled leaves in which at each transition a uniform random leaf is deleted and reattached to a uniform random edge. Now, fix $1le k < n$ and project the leaf mass onto the subtree spanned by the first $k$ leaves. This yields a binary tree with edge weights that we call a decorated $k$-tree with total mass $n$. We introduce label swapping dynamics for the Aldous chain so that, when it runs in stationarity, the decorated $k$-trees evolve as Markov chains themselves, and are projectively consistent over $kle n$. The construction of projectively consistent chains is a crucial step in the construction of the Aldous diffusion on continuum trees by the present authors, which is the $nrightarrow infty$ continuum analogue of the Aldous chain and will be taken up elsewhere. Some of our results have been generalized to Fords alpha model trees.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
