An official website of the United States government
Let $$G$$ be a finite group acting transitively on $$[n]=\{1,2,\ldots,n\}$$, and let $$\Gamma=\mathrm{Cay}(G,T)$$ be a Cayley graph of $$G$$. The graph $$\Gamma$$ is called normal if $$T$$ is closed under conjugation. In this paper, we obtain an upper bound for the second (largest) eigenvalue of the adjacency matrix of the graph $$\Gamma$$ in terms of the second eigenvalues of certain subgraphs of $$\Gamma$$. 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)|\leqslant 5$$, where $$\mathrm{supp}(\tau)$$ is the set of points in $[n]$ non-fixed by $$\tau$$.
more »
« less
This content will become publicly available on January 1, 2026
Random Algebraic Graphs and Their Convergence to ErdőS–Rényi
ABSTRACT A random algebraic graph is defined by a group with a uniform distribution over it and a connection with expectation satisfying . The random graph with vertex set is formed as follows. First, independent variables are sampled uniformly from . Then, vertices are connected with probability . This model captures random geometric graphs over the sphere, torus, and hypercube; certain instances of the stochastic block model; and random subgraphs of Cayley graphs. The main question of interest to the current paper is: when is a random algebraic graph statistically and/or computationally distinguishable from ? Our results fall into two categories. (1) Geometric. We focus on the case and use Fourier‐analytic tools. We match and extend the following results from the prior literature: For hard threshold connections, we match for , and for ‐Lipschitz connections we extend the results of when to the non‐monotone setting. (2) Algebraic. We provide evidence for an exponential statistical‐computational gap. Consider any finite group and let be a set of elements formed by including each set of the form independently with probability Let be the distribution of random graphs formed by taking a uniformly random induced subgraph of size of the Cayley graph . Then, and are statistically indistinguishable with high probability over if and only if . However, low‐degree polynomial tests fail to distinguish and with high probability over when
more »
« less
- Award ID(s):
- 1940205
- PAR ID:
- 10569940
- Publisher / Repository:
- Wiley
- Date Published:
- Journal Name:
- Random Structures & Algorithms
- Volume:
- 66
- Issue:
- 1
- ISSN:
- 1042-9832
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
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
-
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
-
Abstract Consider a set of n vertices, where each vertex has a location in $$\mathbb{R}^d$$ that is sampled uniformly from the unit cube in $$\mathbb{R}^d$$ , and a weight associated to it. Construct a random graph by placing edges independently for each vertex pair with a probability that is a function of the distance between the locations and the vertex weights. Under appropriate integrability assumptions on the edge probabilities that imply sparseness of the model, after appropriately blowing up the locations, we prove that the local limit of this random graph sequence is the (countably) infinite random graph on $$\mathbb{R}^d$$ with vertex locations given by a homogeneous Poisson point process, having weights which are independent and identically distributed copies of limiting vertex weights. Our set-up covers many sparse geometric random graph models from the literature, including geometric inhomogeneous random graphs (GIRGs), hyperbolic random graphs, continuum scale-free percolation, and weight-dependent random connection models. We prove that the limiting degree distribution is mixed Poisson and the typical degree sequence is uniformly integrable, and we obtain convergence results on various measures of clustering in our graphs as a consequence of local convergence. Finally, as a byproduct of our argument, we prove a doubly logarithmic lower bound on typical distances in this general setting.more » « less
-
In a recent breakthrough, Kelley and Meka (FOCS 2023) obtained a strong upper bound on the density of sets of integers without non-trivial three-term arithmetic progressions. In this work, we extend their result, establishing similar bounds for all linear patterns defined by binary systems of linear forms, where “binary” indicates that every linear form depends on exactly two variables. Prior to our work, no strong bounds were known for such systems even in the finite field model setting. A key ingredient in our proof is a graph counting lemma. The classical graph counting lemma, developed by Thomason (Random Graphs 1985) and Chung, Graham, and Wilson (Combinatorica 1989), is a fundamental tool in combinatorics. For a fixed graph H, it states that the number of copies of H in a pseudorandom graph G is similar to the number of copies of H in a purely random graph with the same edge density as G. However, this lemma is only non-trivial when G is a dense graph. In this work, we prove a graph counting lemma that is also effective when G is sparse. Moreover, our lemma is well-suited for density increment arguments in additive number theory. As an immediate application, we obtain a strong bound for the Turán problem in abelian Cayley sum graphs: let Γ be a finite abelian group with odd order. If a Cayley sum graph on Γ does not contain any r-elique as a sub graph, it must have at most 2−Ωr(log1/16|Γ|)⋅|Γ|2 edges. These results hinge on the technology developed by Kelley and Meka and the follow-up work by Kelley, Lovett, and Meka (STOC 2024).more » « less
