اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدInvertibility of the 3-core of Erdos Renyi Graphs with Growing Degree
104
0
0.0
(
0
)
تأليف
Margalit Glasgow
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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.
A (not necessarily proper) vertex colouring of a graph has clustering $c$ if every monochromatic component has at most $c$ vertices. We prove that planar graphs with maximum degree $Delta$ are 3-colourable with clustering $O(Delta^2)$. The previous b
est bound was $O(Delta^{37})$. This result for planar graphs generalises to graphs that can be drawn on a surface of bounded Euler genus with a bounded number of crossings per edge. We then prove that graphs with maximum degree $Delta$ that exclude a fixed minor are 3-colourable with clustering $O(Delta^5)$. The best previous bound for this result was exponential in $Delta$.
Let $G$ be an $n$-vertex graph and let $L:V(G)rightarrow P({1,2,3})$ be a list assignment over the vertices of $G$, where each vertex with list of size 3 and of degree at most 5 has at least three neighbors with lists of size 2. We can determine $L$-
choosability of $G$ in $O(1.3196^{n_3+.5n_2})$ time, where $n_i$ is the number of vertices in $G$ with list of size $i$ for $iin {2,3}$. As a corollary, we conclude that the 3-colorability of any graph $G$ with minimum degree at least 6 can be determined in $O(1.3196^{n-.5Delta(G)})$ time.
We find precise asymptotic estimates for the number of planar maps and graphs with a condition on the minimum degree, and properties of random graphs from these classes. In particular we show that the size of the largest tree attached to the core of
a random planar graph is of order c log(n) for an explicit constant c. These results provide new information on the structure of random planar graphs.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
