More Like this

1. Random walk on group extensions

   https://doi.org/10.1090/tran/9309  

   Golsefidy, S Alireza; Srinivas, Srivatsa (January 2025, Transactions of the American Mathematical Society)

   We study random walks on various group extensions. Under certain bounded generation and bounded scaled conditions, we estimate the spectral gap of a random walk on a quasi-random-by-nilpotent group in terms of the spectral gap of its projection to the quasi-random part. We also estimate the spectral gap of a random-walk on a product of two quasi-random groups in terms of the spectral gap of its projections to the given factors. Based on these results, we estimate the spectral gap of a random walk on the ${\mathbb{F}}_q$-points of a perfect algebraic group $\mathbb{G}$in terms of the spectral gap of its projections to the almost simple factors of the semisimple quotient of $\mathbb{G}$. These results extend a work of Lindenstrauss and Varjú and an earlier work of the authors. Moreover, using a result of Breuillard and Gamburd, we show that there is an infinite set $\mathcal{P}$of primes of density one such that, if $k$is a positive integer and $\mathbb{G}=\mathbb{U}⋊<\#comment/>({\mathrm{SL}}_2{)}_{\mathbb{Q}}^m$is a perfect group and $\mathbb{U}$is a unipotent group, then the family of all the Cayley graphs of $\mathbb{G}\left(\mathbb{Z}/\underset{i=1}{\overset{k}{\prod <\#comment/>}}{p}_i\mathbb{Z}\right)$, $p_i\in <\#comment/>\mathcal{P}$, is a family of expanders. 

   more » « less
2. Sample-Path Large Deviations for Unbounded Additive Functionals of the Reflected Random Walk

   https://doi.org/10.1287/moor.2020.0094  

   Bazhba, Mihail; Blanchet, Jose; Rhee, Chang-Han; Zwart, Bert (March 2024, Mathematics of Operations Research)

   We prove a sample-path large deviation principle (LDP) with sublinear speed for unbounded functionals of certain Markov chains induced by the Lindley recursion. The LDP holds in the Skorokhod space [Formula: see text] equipped with the [Formula: see text] topology. Our technique hinges on a suitable decomposition of the Markov chain in terms of regeneration cycles. Each regeneration cycle denotes the area accumulated during the busy period of the reflected random walk. We prove a large deviation principle for the area under the busy period of the Markov random walk, and we show that it exhibits a heavy-tailed behavior. Funding: The research of B. Zwart and M. Bazhba is supported by the Nederlandse Organisatie voor Wetenschappelijk Onderzoek [Grant 639.033.413]. The research of J. Blanchet is supported by the National Science Foundation (NSF) [Grants 1915967, 1820942, and 1838576] as well as the Defense Advanced Research Projects Agency [Grant N660011824028]. The research of C.-H. Rhee is supported by the NSF [Grant CMMI-2146530]. 

   more » « less
3. Constraining the clustering transition for colorings of sparse random graphs

   Anastos, M.; Frieze, A.; Pegden, W. (January 2018, The electronic journal of combinatorics)

   Let $$\Omega_q$$ denote the set of proper $[q]$-colorings of the random graph $$G_{n,m}, m=dn/2$$ and let $$H_q$$ be the graph with vertex set $$\Omega_q$$ and an edge $$\set{\s,\t}$$ where $$\s,\t$$ are mappings $$[n]\to[q]$$ iff $$h(\s,\t)=1$$. Here $$h(\s,\t)$$ is the Hamming distance $$|\set{v\in [n]:\s(v)\neq\t(v)}|$$. We show that w.h.p. $$H_q$$ contains a single giant component containing almost all colorings in $$\Omega_q$$ if $$d$$ is sufficiently large and $$q\geq \frac{cd}{\log d}$$ for a constant $c>3/2$. 

   more » « less
4. The second eigenvalue of some normal Cayley graphs of highly transitive groups

   Huang, Xueyi; Huang, Qiongxiang; Cioaba, Sebastian M (June 2019, The Electronic journal of combinatorics)

   Let $$\Gamma$$ be a finite group acting transitively on $$[n]=\{1,2,\ldots,n\}$$, and let $$G=\mathrm{Cay}(\Gamma,T)$$ be a Cayley graph of $$\Gamma$$. The graph $$G$$ is called normal if $$T$$ is closed under conjugation. In this paper, we obtain an upper bound for \textcolor[rgb]{0,0,1}{the second (largest) eigenvalue} of the adjacency matrix of the graph $$G$$ in terms of the second eigenvalues of certain subgraphs of $$G$$ (see Theorem 2.6). Using this result, we develop a recursive method to determine the second eigenvalues of certain Cayley graphs of $$S_n$$ and we determine the second eigenvalues of a majority of the connected normal Cayley graphs (and some of their subgraphs) of $$S_n$$ with $$\max_{\tau\in T}|\mathrm{supp}(\tau)|\leq 5$$, where $$\mathrm{supp}(\tau)$$ is the set of points in $[n]$ non-fixed by $$\tau$$. 

   more » « less
5. The second eigenvalue of some normal Cayley graphs of highly transitive groups

   Huang, Xueyi; Huang, Qiongxiang; Cioaba, Sebastian M (June 2019, The Electronic journal of combinatorics)

   Let $$\Gamma$$ be a finite group acting transitively on $$[n]=\{1,2,\ldots,n\}$$, and let $$G=\mathrm{Cay}(\Gamma,T)$$ be a Cayley graph of $$\Gamma$$. The graph $$G$$ is called normal if $$T$$ is closed under conjugation. In this paper, we obtain an upper bound for \textcolor[rgb]{0,0,1}{the second (largest) eigenvalue} of the adjacency matrix of the graph $$G$$ in terms of the second eigenvalues of certain subgraphs of $$G$$ (see Theorem 2.6). Using this result, we develop a recursive method to determine the second eigenvalues of certain Cayley graphs of $$S_n$$ and we determine the second eigenvalues of a majority of the connected normal Cayley graphs (and some of their subgraphs) of $$S_n$$ with $$\max_{\tau\in T}|\mathrm{supp}(\tau)|\leq 5$$, where $$\mathrm{supp}(\tau)$$ is the set of points in $[n]$ non-fixed by $$\tau$$. 

   more » « less