Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userGlobal eigenvalue fluctuations of random biregular bipartite graphs
65
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We compute the eigenvalue fluctuations of uniformly distributed random biregular bipartite graphs with fixed and growing degrees for a large class of analytic functions. As a key step in the proof, we obtain a total variation distance bound for the Poisson approximation of the number of cycles and cyclically non-backtracking walks in random biregular bipartite graphs, which might be of independent interest. As an application, we translate the results to adjacency matrices of uniformly distributed random regular hypergraphs.
rate research
Read More
We consider the spectral gap of a uniformly chosen random $(d_1,d_2)$-biregular bipartite graph $G$ with $|V_1|=n, |V_2|=m$, where $d_1,d_2$ could possibly grow with $n$ and $m$. Let $A$ be the adjacency matrix of $G$. Under the assumption that $d_1geq d_2$ and $d_2=O(n^{2/3}),$ we show that $lambda_2(A)=O(sqrt{d_1})$ with high probability. As a corollary, combining the results from Tikhomirov and Youssef (2019), we confirm a conjecture in Cook (2017) that the second singular value of a uniform random $d$-regular digraph is $O(sqrt{d})$ for $1leq dleq n/2$ with high probability. This also implies that the second eigenvalue of a uniform random $d$-regular digraph is $O(sqrt{d})$ for $1leq dleq n/2$ with high probability. Assuming $d_2=O(1)$ and $d_1=O(n^2)$, we further prove that for a random $(d_1,d_2)$-biregular bipartite graph, $|lambda_i^2(A)-d_1|=O(sqrt{d_1(d_2-1)})$ for all $2leq ileq n+m-1$ with high probability. The proofs of the two results are based on the size biased coupling method introduced in Cook, Goldstein, and Johnson (2018) for random $d$-regular graphs and several new switching operations we defined for random bipartite biregular graphs.
This note gives a detailed proof of the following statement. Let $din mathbb{N}$ and $m,n ge d + 1$, with $m + n ge binom{d+2}{2} + 1$. Then the complete bipartite graph $K_{m,n}$ is generically globally rigid in dimension $d$.
For each $n ge 1$, let $mathrm{d}^n=(d^{n}(i),1 le i le n)$ be a sequence of positive integers with even sum $sum_{i=1}^n d^n(i) ge 2n$. Let $(G_n,T_n,Gamma_n)$ be uniformly distributed over the set of simple graphs $G_n$ with degree sequence $mathrm{d}^n$, endowed with a spanning tree $T_n$ and rooted along an oriented edge $Gamma_n$ of $G_n$ which is not an edge of $T_n$. Under a finite variance assumption on degrees in $G_n$, we show that, after rescaling, $T_n$ converges in distribution to the Brownian continuum random tree as $n to infty$. Our main tool is a new version of Pitmans additive coalescent (https://doi.org/10.1006/jcta.1998.2919), which can be used to build both random trees with a fixed degree sequence, and random tree-weighted graphs with a fixed degree sequence. As an input to the proof, we also derive a Poisson approximation theorem for the number of loops and multiple edges in the superposition of a fixed graph and a random graph with a given degree sequence sampled according to the configuration model; we find this to be of independent interest.
In this paper we study height fluctuations of random lozenge tilings of polygonal domains on the triangular lattice through nonintersecting Bernoulli random walks. For a large class of polygons which have exactly one horizontal upper boundary edge, we show that these random height functions converge to a Gaussian Free Field as predicted by Kenyon and Okounkov [28]. A key ingredient of our proof is a dynamical version of the discrete loop equations as introduced by Borodin, Guionnet and Gorin [5], which might be of independent interest.
In this paper we study the impact of random exponential edge weights on the distances in a random graph and, in particular, on its diameter. Our main result consists of a precise asymptotic expression for the maximal weight of the shortest weight paths between all vertices (the weighted diameter) of sparse random graphs, when the edge weights are i.i.d. exponential random variables.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
