Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userShotgun assembly of unlabeled Erdos-Renyi graphs
66
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Given an unlabeled graph $G$ on $n$ vertices, let ${N_{G}(v)}_{v}$ be the collection of subgraphs of $G$, where for each vertex $v$ of $G$, $N_{G}(v)$ is the subgraph of $G$ induced by vertices of $G$ of distance at most one from $v$. We show that there are universal constants $C,c>0$ with the following property. Let the sequence $(p_n)_{n=1}^infty$ satisfy $n^{-1/2}log^C nleq p_nleq c$. For each $n$, let $Gamma_n$ be an unlabeled $G(n,p_n)$ Erdos-Renyi graph. Then with probability $1-o(1)$, any unlabeled graph $tilde Gamma_n$ on $n$ vertices with ${N_{tilde Gamma_n}(v)}_{v}={N_{Gamma_n}(v)}_{v}$ must coincide with $Gamma_n$. This establishes $p_n= tilde Theta(n^{-1/2})$ as the transition for the density parameter $p_n$ between reconstructability and non-reconstructability of Erdos-Renyi graphs from their $1$--neighborhoods, answering a question of Gaudio and Mossel.
rate research
Read More
Graph shotgun assembly refers to the problem of reconstructing a graph from a collection of local neighborhoods. In this paper, we consider shotgun assembly of ErdH{o}s-Renyi random graphs $G(n, p_n)$, where $p_n = n^{-alpha}$ for $0 < alpha < 1$. We consider both reconstruction up to isomorphism as well as exact reconstruction (recovering the vertex labels as well as the structure). We show that given the collection of distance-$1$ neighborhoods, $G$ is exactly reconstructable for $0 < alpha < frac{1}{3}$, but not reconstructable for $frac{1}{2} < alpha < 1$. Given the collection of distance-$2$ neighborhoods, $G$ is exactly reconstructable for $0 < alpha < frac{1}{2}$, but not reconstructable for $frac{3}{4} < alpha < 1$.
Through Monte Carlo Simulation, the well-known majority-vote model has been studied with noise on directed random graphs. In order to characterize completely the observed order-disorder phase transition, the critical noise parameter $q_c$, as well as the critical exponents $beta/nu$, $gamma/nu$ and $1/nu$ have been calculated as a function of the connectivity $z$ of the random graph.
Reaction networks are commonly used within the mathematical biology and mathematical chemistry communities to model the dynamics of interacting species. These models differ from the typical graphs found in random graph theory since their vertices are constructed from elementary building blocks, i.e., the species. In this paper, we consider these networks in an ErdH os-Renyi framework and, under suitable assumptions, derive a threshold function for the network to have a deficiency of zero, which is a property of great interest in the reaction network community. Specifically, if the number of species is denoted by $n$ and if the edge probability is denote by $p_n$, then we prove that the probability of a random binary network being deficiency zero converges to 1 if $frac{p_n}{r(n)}to 0$, as $n to infty$, and converges to 0 if $frac{p_n}{r(n)}to infty$, as $n to infty$, where $r(n)=frac{1}{n^3}$.
Let $A in mathbb{R}^{n times n}$ be the adjacency matrix of an ErdH{o}s Renyi graph $G(n, d/n)$ for $d = omega(1)$ and $d leq 3log(n)$. We show that as $n$ goes to infinity, with probability that goes to $1$, the adjacency matrix of the $3$-core of $G(n, d/n)$ is invertible.
We develop a quantitative large deviations theory for random Bernoulli tensors. The large deviation principles rest on a decomposition theorem for arbitrary tensors outside a set of tiny measure, in terms of a novel family of norms generalizing the cut norm. Combined with associated counting lemmas, these yield sharp asymptotics for upper tails of homomorphism counts in the $r$-uniform ErdH{o}s--Renyi hypergraph for any fixed $rge 2$, generalizing and improving on previous results for the ErdH{o}s--Renyi graph ($r=2$). The theory is sufficiently quantitative to allow the density of the hypergraph to vanish at a polynomial rate, and additionally yields (joint) upper and lower tail asymptotics for other nonlinear functionals of interest.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
