Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the Relativized Alon Second Eigenvalue Conjecture I: Main Theorems, Examples, and Outline of Proof
140
0
0.0
(
0
)
Added by
Joel Friedman
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
This is the first in a series of six articles devoted to showing that a typical covering map of large degree to a fixed, regular graph has its new adjacency eigenvalues within the bound conjectured by Alon for random regular graphs. Many of the techniques we develop hold whether or not the base graph is regular. Our first main theorem in this series of articles is that if the base graph is $d$-regular, then for any $epsilon>0$, as the degree, $n$, of the covering map tends to infinity, some new adjacency eigenvalue of the map is larger in absolute value that $2(d-1)^{1/2}+epsilon$ with probability at most order $1/n$. Our second main theorem is that if, in addition, the base graph is Ramanujan, then this probability is bounded above and below by $1/n$ to the power of a positive integer that we call the {em tangle power} of the model, i.e., of the probability spaces of random covering maps of degree $n$. The tangle power is fairly easy to bound from below, and at times to compute exactly; it measures the probability that certain {em tangles} appear in the random covering graph, where a {em tangle} is a local event that forces the covering graph to have a new eigenvalue strictly larger than $2(d-1)^{1/2}$. Our main theorems are relativizations of Alons conjecture on the second eigenvalue of random regular graphs of large degree. In this first article of the series, we introduce all the terminology needed in this series, motivate this terminology, precisely state all the results in the remaining articles, and make some remarks about their proofs. As such, this article provides an overview of the entire series of articles; furthermore, the rest of the articles in this series may be read independently of one another.
rate research
Read More
This is the fifth in a series of articles devoted to showing that a typical covering map of large degree to a fixed, regular graph has its new adjacency eigenvalues within the bound conjectured by Alon for random regular graphs. In this article we use the results of Articles~III and IV in this series to prove that if the base graph is regular, then as the degree, $n$, of the covering map tends to infinity, some new adjacency eigenvalue has absolute value outside the Alon bound with probability bounded by $O(1/n)$. In addition, we give upper and lower bounds on this probability that are tight to within a multiplicative constant times the degree of the covering map. These bounds depend on two positive integers, the emph{algebraic power} (which can also be $+infty$) and the emph{tangle power} of the model of random covering map. We conjecture that the algebraic power of the models we study is always $+infty$, and in Article~VI we prove this when the base graph is regular and emph{Ramanujan}. When the algebraic power of the model is $+infty$, then the results in this article imply stronger results, such as (1) the upper and lower bounds mentioned above are matching to within a multiplicative constant, and (2) with probability smaller than any negative power of the degree, the some new eigenvalue fails to be within the Alon bound only if the covering map contains one of finitely many tangles as a subgraph (and this event has low probability).
This is the second in a series of articles devoted to showing that a typical covering map of large degree to a fixed, regular graph has its new adjacency eigenvalues within the bound conjectured by Alon for random regular graphs. The first main result in this article concerns the function $f(k,n)$ defined as the number of SNBC (strictly non-backtracking closed) walks of length $k$ of a given homotopy type in a random covering graph of degree $n$ of a fixed graph. We prove the existence of asymptotic expansions in powers of $1/n$ for $f(k,n)$, where the coefficients---functions of $k$---are proven to have some desirable properties; namely, these coefficients are approximately a sum of polynomials times exponential functions. The second main result is a generalization of the first, where the number of SNBC walks of length $k$ is multiplied by an indicator function that the covering graph contains a certain type of {em tangle}; the second result requires more terminology, although its proof uses the same basic tools used to prove the first result. % The motivation for the second main result will be clear in % the third article in this series of articles. The results in this article are mostly straightforward generalizations of methods used in previous works. However, this article (1) factors these methods into a number of short, conceptually simple, and independent parts, (2) writes each independent part in more general terms, and (3) significantly simplifies of one of the previous computations. As such we expect that this article will make it easier to apply trace methods to related models of random graphs.
This is the sixth in a series of articles devoted to showing that a typical covering map of large degree to a fixed, regular graph has its new adjacency eigenvalues within the bound conjectured by Alon for random regular graphs. In this article we show that if the fixed graph is regular Ramanujan, then the {em algebraic power} of the model of random covering graphs is $+infty$. This implies a number of interesting results, such as (1) one obtains the upper and lower bounds---matching to within a multiplicative constant---for the probability that a random covering map has some new adjacency eigenvalue outside the Alon bound, and (2) with probability smaller than any negative power of the degree of the covering map, some new eigenvalue fails to be within the Alon bound without the covering map containing one of finitely many tangles as a subgraph (and this tangle containment event has low probability).
This is the third in a series of articles devoted to showing that a typical covering map of large degree to a fixed, regular graph has its new adjacency eigenvalues within the bound conjectured by Alon for random regular graphs. In this paper we consider random graphs that are random covering graphs of large degree $n$ of a fixed base graph. We prove the existence of asympototic expansion in $1/n$ for the expected value of the number of strictly non-backtracking closed walks of length $k$ times the indicator function that the graph is free of certain {em tangles}; moreover, we prove that the coefficients of these expansions are nice functions of $k$, namely approximately equal to a sum of polynomials in $k$ times exponential functions of $k$. Our results use the methods of Friedman used to resolve Alons original conjecture, combined with the results of Article~II in this series of articles. One simplification in this article over the previous methods of Friedman is that the regularlized traces used in this article, which we call {em certified traces}, are far easier to define and work with than the previously utilized {em selective traces}.
This is the fourth in a series of articles devoted to showing that a typical covering map of large degree to a fixed, regular graph has its new adjacency eigenvalues within the bound conjectured by Alon for random regular graphs. In this paper we prove a {em Sidestepping Theorem} that is more general and easier to use than earlier theorems of this kind. Such theorems concerns a family probability spaces ${{mathcal{M}}_n}$ of $ntimes n$ matrices, where $n$ varies over some infinite set, $N$, of natural numbers. Many trace methods use simple Markov bounds to bound the expected spectral radius of elements of ${mathcal{M}}_n$: this consists of choosing one value, $k=k(n)$, for each $nin N$, and proving expected spectral radius bounds based on the expected value of the trace of the $k=k(n)$-power of elements of ${mathcal{M}}_n$. {em Sidestepping} refers to bypassing such simple Markov bounds, obtaining improved results using a number of values of $k$ for each fixed $nin N$. In more detail, if the $Min {mathcal{M}}_n$ expected value of ${rm Trace}(M^k)$ has an asymptotic expansion in powers of $1/n$, whose coefficients are well behaved functions of $k$, then one can get improved bounds on the spectral radius of elements of ${mathcal{M}}_n$ that hold with high probability. Such asymptotic expansions are shown to exist in the third article in this series for the families of matrices that interest us; in the fifth and sixth article in this series we will apply the Sidestepping Theorem in this article to prove the main results in this series of articles. This article is independent of all other articles in this series; it can be viewed as a theorem purely in probability theory, concerning random matrices or, equivalently, the $n$ random variables that are the eigenvalues of the elements of ${mathcal{M}}_n$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
