اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدShotgun Assembly of Erdos-Renyi Random Graphs
110
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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$.
قيم البحث
اقرأ أيضاً
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 th
ere 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.
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.
Using Monte Carlo simulations we study the Ising model with spin S=1/2 and 1 on {it directed} and {it undirected} Erdos-Renyi (ER) random graphs, with $z$ neighbors for each spin. In the case with spin S=1/2, the {it undirected} and {it directed} ER
graphs present a spontaneous magnetization in the universality class of mean field theory, where in both {it directed} and {it undirected} ER graphs the model presents a spontaneous magnetization at $p = z/N$ ($z=2, 3, ...,N$), but no spontaneous magnetization at $p = 1/N$ which is the percolation threshold. For both {it directed} and {it undirected} ER graphs with spin S=1 we find a first-order phase transition for z=4 and 9 neighbors.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
