The spherical random geometric graph $G(n,d,p)$ is obtained by sampling $n$ independent points uniformly on the unit sphere $\mathbb{S}^{d-1}\subseteq\mathbb{R}^d$ and joining pairs of points which are sufficiently close, where the threshold is chosen so that the edge probability is $p$. The central question related to this model, and to a broad class of other models, is the following: when does the underlying geometry affect the resulting graph in a way which makes it distinguishable from the Erd\H{o}s--R\'enyi random graph $G(n,p)$, as measured in total variation distance? The precise answer to this question was conjectured by Bubeck, Ding, Eldan, and R\'acz, who predicted that $G(n,d,p)$ and $G(n,p)$ are indistinguishable precisely when $d \gg n^3p^3(\log p^{-1})^3$, and provided a test for distinguishing these models in the low-dimensional regime. Although this conjecture attracted considerable attention from researchers in probability, theoretical computer science, and high-dimensional statistics, it was previously fully proved only in the constant-density case. In this paper, we resolve the distinguishability conjecture in the broad range $1/3 \geq p \geq n^{-1/5} \text{polylog}(n)$. The key ingredient of our proof is a stronger statement which gives a precise asymptotic formula for the probability that $G(n,d,p)$ realizes a prescribed graph $H$: above the conjectured threshold, this probability is at most $(1+o(1))$ times the corresponding probability for $G(n,p)$, with the signed triangle count of $H$ appearing as the leading correction term.
We consider a random subgraph $G_p(n,r,<s)$ of the complete distance graph $G(n,r,<s)$ whose vertices are the $r$-element subsets of the set $\{1,\dots,n\}$ and whose edges join pairs of subsets that intersect in fewer than $s$ elements; each edge survives independently of the others with probability $p$. The independence number of the graph $G(n,r,<s)$ equals $C_{n-s}^{r-s}$ -- this is the classical Erdos-Ko-Rado theorem. We prove that, for $r=r(n)\to\infty$, $s=s(n)\to\infty$, $s=o(r)$, $r^2=o(n)$ and $p\ge 16\,sr^2\ln(n/r)/n$, with probability tending to 1 the independence number of the random graph $G_p(n,r,<s)$ also equals $C_{n-s}^{r-s}$, i.e., the Erdos-Ko-Rado result is stable under random sparsification of the graph. Thereby, in the range of parameters $s\to\infty$, $s=o(r)$, a recent result of Raigorodskii and Karas is strengthened: the lower bound on the probability $p$ that guarantees stability is lowered by a factor of about $r/s$.
Consider a random geometric graph $G_M(n;r)$ on a compact Riemannian manifold $M$, whose vertices are a cloud of $n$ independently sampled points, and whose edges connect vertices at distance $\le r$. We show that, in the thermodynamic (i.e. bounded expected average degree) regime, if $G_M(n;r)$ is supercritical in the sense of continuum percolation, then the first homology group $H_1(M)$ of $M$ can be correctly inferred from $G_M(n;r)$ with high probability as $n \to \infty$. Specifically, one can obtain $H_1(M)$ by taking the cycle space of $G_M(n;r)$ and quotienting out all the cycles of metric diameter $O(r|\log r|)$ (or of graph diameter $O(|\log r|)$). Our method of estimating $H_1(M)$ exploits a coarse-topological fact about supercritical percolation, as opposed to usual methods, which examine the topology of neighborhoods of the point cloud. Whereas previous methods use combinatorial models which require $O(n \log n)$ edges, our method only requires $O(n)$ edges. We also show that, in all phases of the thermodynamic regime, if one instead takes the quotient by cycles of metric diameter $o(r|\log r|)$, with high probability, one will not recover $H_1(M)$. Thus $\Theta(r|\log r|)$ is the ``right scale.''On the way, we show that an arbitrary compact $d$-dimensional Riemannian manifold has a \emph{first homological percolation threshold} in the sense of Bobrowski and Skraba \cite{BS2020} which coincides with the continuum percolation threshold on $\R^d$, a result previously only known for the flat torus. This strongly suggests that our results are optimal, in the sense that $H_1(M)$ cannot be inferred from $G_M(n;r)$ in the subcritical thermodynamic regime. All results hold for homology with arbitrary coefficients.
Let $X_H$ denote the number of copies of a fixed graph $H$ in $G_{n, p}$. Gilmer and Kopparty conjectured that $X_H$ satisfies a local central limit theorem (LCLT) provided that $H$ is connected, $p \gg n^{-1/m(H)}$, and $n^2 (1-p) \gg 1$, where $m(H)$ is the maximum density. Following the work of Berkowitz, Sah and Sawhney confirmed this conjecture for every constant $p$, leaving the regime where $p=o(1)$ open. In this regime, the only case addressed in the literature is when $H=K_3$, where, in a recent paper, Ara\'ujo and Mattos confirmed the conjecture for $p \in (4n^{-1/2}, 1/2)$. This, together with a general result of R\"ollin and Ross, essentially settles the conjecture for the triangle. We generalise these results by showing that an LCLT holds for $H = K_r$ (for any fixed $r \ge 3$) in the regime $n^{-1/m(H)}\ll p\leq 1/2$, essentially settling the conjecture for cliques.
Asaf Cohen Antonir, Ilay Hoshen, Maksim Zhukovskii· 0 citations
For a simple graph $G$ of order $n$, let $S_2(G)=\lambda_1(G)+\lambda_2(G)$ denote its spectral sum. We determine, for every $n\geq5$, the exact maximum of $S_2(G)$ and all equality cases. The unique maximizer, up to isomorphism, is the complement of the disjoint union of a suitably balanced complete bipartite graph and isolated vertices, with the sizes of its three parts determined by $n$ modulo $7$. Denoting this graph by $K_n^\star$, we further show that $ S_2(K_n^\star)\leq\frac{8n}{7}-2,$ with equality exactly when $7\mid n$. This proves a conjecture of Kumar, Liu, Monterde, Pragada and Tait, which strengthens the Aouchiche--Hansen 2010 conjecture by extending it from connected graphs to all graphs and by asserting uniqueness of the extremal graph. The result also subsumes the 2008 conjecture of Ebrahimi B., Mohar, Nikiforov, and Ahmady. The proof combines Ky Fan's variational principle with a spectral inequality for weighted Ferrers quotients to reduce the problem to an explicit family whose complements have incidence rank one. Exact integer optimization and a separate equality analysis then yield the maximum and uniqueness.
Let $H \sim H^{k}_c(n,p)$ be an edge-colored random $k$-uniform hypergraph on the vertex set $[n]$, where each edge $e \in \binom{[n]}{k}$ is included independently with probability $p$ and is uniformly and independently assigned a color from the color set $[c]$. For $k = 2$, Ferber and Krivelevich (2016) established that if $c = (1+o(1))n$ and $p = (\log n + \log \log n + \omega(n))/n$, then with high probability the edge-colored random graph $H \sim H^2_c(n,p)$ contains a rainbow Hamilton Berge cycle. Subsequently, Bal, Berkowitz, Devlin, and Schacht (2021) determined the threshold for the appearance of a (non-rainbow) Hamilton Berge cycle in random $k$-uniform hypergraphs. In this paper, we generalize the results to all integers $k \ge 3$. We prove that if $c = (1+o(1))n$ and $p = (k-1)! \frac{\log n + \log\log n + \omega(n)}{n^{k-1}}$, then with high probability $H \sim H^{k}_c(n,p)$ contains a rainbow Hamilton Berge cycle. Furthermore, both conditions on $c$ and $p$ are asymptotically tight. \noindent\emph{Key words:} Rainbow subgraph, Hamiltonicity, Berge cycle, Random hypergraph.
We study whether an observed graph can distinguish a random graph generated by latent geometry from one with independent edges. In the geometric model, vertex positions are independent and uniform on a high-dimensional sphere. Conditional on these positions, edges occur independently, with probabilities determined by a connection function $K$ of the inner products of their endpoints. The comparison model is an Erd\H{o}s-R\'enyi graph with the same edge density. A general spectral conjecture asserts that if the cubic spectral trace, which corresponds to the signed triangle mean, is sufficiently small in the sense that \[ n^3[\operatorname{tr}(\kappa^3)]^2\longrightarrow0, \] where $n$ is the number of vertices and $\kappa$ is the centered and standardized spherical kernel operator, then the total variation distance between the two graph distributions tends to zero. Consequently, the lower limit of the sum of the two error probabilities of any sequence of tests is at least one. We give a counterexample to the formulation allowing dimension-dependent connection functions without monotonicity or a common-sign condition on the spectrum. Our quadratic connection functions are uniformly bounded away from zero and one. Their cubic trace vanishes identically through cancellation between positive and negative eigenvalues, whereas their quartic trace is strictly positive. When $d=\max\{3,\lfloor n^{1/20}\rfloor\}$, a signed four-cycle test has a sum of error probabilities tending to zero, and the total variation distance instead tends to one. A perturbation making the cubic trace strictly nonzero still satisfies the stated cubic-trace condition and yields strong detection. The construction and detection result follow, respectively, from a finite-rank spectral decomposition of the spherical kernel and estimates of the mean and variance of the four-cycle statistic.
Unknown authors· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
