Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userInvertibility of the 3-core of Erdos Renyi Graphs with Growing Degree
104
0
0.0
(
0
)
Authors
Margalit Glasgow
Ask ChatGPT about the research
No Arabic abstract
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.
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$.
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.
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 best 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
