Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRandom growth on a Ramanujan graph
131
0
0.0
(
0
)
Added by
Andrew Newman
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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 maximize 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.
rate research
Read More
Let $X$ be an infinite graph of bounded degree; e.g., the Cayley graph of a free product of finite groups. If $G$ is a finite graph covered by $X$, it is said to be $X$-Ramanujan if its second-largest eigenvalue $lambda_2(G)$ is at most the spectral radius $rho(X)$ of $X$, and more generally $k$-quasi-$X$-Ramanujan if $lambda_k(G)$ is at most $rho(X)$. In case $X$ is the infinite $Delta$-regular tree, this reduces to the well known notion of a finite $Delta$-regular graph being Ramanujan. Inspired by the Interlacing Polynomials method of Marcus, Spielman, and Srivastava, we show the existence of infinitely many $k$-quasi-$X$-Ramanujan graphs for a variety of infinite $X$. In particular, $X$ need not be a tree; our analysis is applicable whenever $X$ is what we call an additive product graph. This additive product is a new construction of an infinite graph $mathsf{AddProd}(A_1, dots, A_c)$ from finite atom graphs $A_1, dots, A_c$ over a common vertex set. It generalizes the notion of the free product graph $A_1 * cdots * A_c$ when the atoms $A_j$ are vertex-transitive, and it generalizes the notion of the universal covering tree when the atoms $A_j$ are single-edge graphs. Key to our analysis is a new graph polynomial $alpha(A_1, dots, A_c;x)$ that we call the additive characteristic polynomial. It generalizes the well known matching polynomial $mu(G;x)$ in case the atoms $A_j$ are the single edges of $G$, and it generalizes the $r$-characteristic polynomial introduced in [Ravichandran16, Leake-Ravichandran18]. We show that $alpha(A_1, dots, A_c;x)$ is real-rooted, and all of its roots have magnitude at most $rho(mathsf{AddProd}(A_1, dots, A_c))$. This last fact is proven by generalizing Godsils notion of treelike walks on a graph $G$ to a notion of freelike walks on a collection of atoms $A_1, dots, A_c$.
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$.
The cutoff phenomenon was recently confirmed for random walks on Ramanujan graphs by the first author and Peres. In this work, we obtain analogs in higher dimensions, for random walk operators on any Ramanujan complex associated with a simple group $G$ over a local field $F$. We show that if $T$ is any $k$-regular $G$-equivariant operator on the Bruhat-Tits building with a simple combinatorial property (collision-free), the associated random walk on the $n$-vertex Ramanujan complex has cutoff at time $log_k n$. The high dimensional case, unlike that of graphs, requires tools from non-commutative harmonic analysis and the infinite-dimensional representation theory of $G$. Via these, we show that operators $T$ as above on Ramanujan complexes give rise to Ramanujan digraphs with a special property ($r$-normal), implying cutoff. Applications include geodesic flow operators, geometric implications, and a confirmation of the Riemann Hypothesis for the associated zeta functions over every group $G$, previously known for groups of type $widetilde A_n$ and $widetilde C_2$.
We study the distributional properties of horizontal visibility graphs associated with random restrictive growth sequences and random set partitions of size $n.$ Our main results are formulas expressing the expected degree of graph nodes in terms of simple explicit functions of a finite collection of Stirling and Bernoulli numbers.
For a binomial random variable $xi$ with parameters $n$ and $b/n$, it is well known that the median equals $b$ when $b$ is an integer. In 1968, Jogdeo and Samuels studied the behaviour of the relative difference between ${sf P}(xi=b)$ and $1/2-{sf P}(xi<b)$. They proved its monotonicity in $n$ and posed a question about its monotonicity in $b$. This question is motivated by the solved problem proposed by Ramanujan in 1911 on the monotonicity of the same quantity but for a Poisson random variable with an integer parameter $b$. In the paper, we answer this question and introduce a simple way to analyse the monotonicity of similar functions.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
