Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the edit distance function of the random graph
85
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Given a hereditary property of graphs $mathcal{H}$ and a $pin [0,1]$, the edit distance function ${rm ed}_{mathcal{H}}(p)$ is asymptotically the maximum proportion of edge-additions plus edge-deletions applied to a graph of edge density $p$ sufficient to ensure that the resulting graph satisfies $mathcal{H}$. The edit distance function is directly related to other well-studied quantities such as the speed function for $mathcal{H}$ and the $mathcal{H}$-chromatic number of a random graph. Let $mathcal{H}$ be the property of forbidding an ErdH{o}s-R{e}nyi random graph $Fsim mathbb{G}(n_0,p_0)$, and let $varphi$ represent the golden ratio. In this paper, we show that if $p_0in [1-1/varphi,1/varphi]$, then a.a.s. as $n_0toinfty$, begin{align*} {rm ed}_{mathcal{H}}(p) = (1+o(1)),frac{2log n_0}{n_0} cdotminleft{ frac{p}{-log(1-p_0)}, frac{1-p}{-log p_0} right}. end{align*} Moreover, this holds for $pin [1/3,2/3]$ for any $p_0in (0,1)$.
rate research
Read More
The edit distance function of a hereditary property $mathscr{H}$ is the asymptotically largest edit distance between a graph of density $pin[0,1]$ and $mathscr{H}$. Denote by $P_n$ and $C_n$ the path graph of order $n$ and the cycle graph of order $n$, respectively. Let $C_{2n}^*$ be the cycle graph $C_{2n}$ with a diagonal, and $widetilde{C_n}$ be the graph with vertex set ${v_0, v_1, ldots, v_{n-1}}$ and $E(widetilde{C_n})=E(C_n)cup {v_0v_2}$. Marchant and Thomason determined the edit distance function of $C_6^{*}$. Peck studied the edit distance function of $C_n$, while Berikkyzy et al. studied the edit distance of powers of cycles. In this paper, by using the methods of Peck and Martin, we determine the edit distance function of $C_8^{*}$, $widetilde{C_n}$ and $P_n$, respectively.
Given a hereditary property $mathcal H$ of graphs and some $pin[0,1]$, the edit distance function $operatorname{ed}_{mathcal H}(p)$ is (asymptotically) the maximum proportion of edits (edge-additions plus edge-deletions) necessary to transform any graph of density $p$ into a member of $mathcal H$. For any fixed $pin[0,1]$, $operatorname{ed}_{mathcal H}(p)$ can be computed from an object known as a colored regularity graph (CRG). This paper is concerned with those points $pin[0,1]$ for which infinitely many CRGs are required to compute $operatorname{ed}_{mathcal H}$ on any open interval containing $p$; such a $p$ is called an accumulation point. We show that, as expected, $p=0$ and $p=1$ are indeed accumulation points for some hereditary properties; we additionally determine the slope of $operatorname{ed}_{mathcal H}$ at these two extreme points. Unexpectedly, we construct a hereditary property with an accumulation point at $p=1/4$. Finally, we derive a significant structural property about those CRGs which occur at accumulation points.
The random reversal graph offers new perspectives, allowing to study the connectivity of genomes as well as their most likely distance as a function of the reversal rate. Our main result shows that the structure of the random reversal graph changes dramatically at $lambda_n=1/binom{n+1}{2}$. For $lambda_n=(1-epsilon)/binom{n+1}{2}$, the random graph consists of components of size at most $O(nln(n))$ a.s. and for $(1+epsilon)/binom{n+1}{2}$, there emerges a unique largest component of size $sim wp(epsilon) cdot 2^ncdot n$!$ a.s.. This giant component is furthermore dense in the reversal graph.
We consider the generalized game Lights Out played on a graph and investigate the following question: for a given positive integer $n$, what is the probability that a graph chosen uniformly at random from the set of graphs with $n$ vertices yields a universally solvable game of Lights Out? When $n leq 11$, we compute this probability exactly by determining if the game is universally solvable for each graph with $n$ vertices. We approximate this probability for each positive integer $n$ with $n leq 87$ by applying a Monte Carlo method using 1,000,000 trials. We also perform the analogous computations for connected graphs.
Scene Graph, as a vital tool to bridge the gap between language domain and image domain, has been widely adopted in the cross-modality task like VQA. In this paper, we propose a new method to edit the scene graph according to the user instructions, which has never been explored. To be specific, in order to learn editing scene graphs as the semantics given by texts, we propose a Graph Edit Distance Reward, which is based on the Policy Gradient and Graph Matching algorithm, to optimize neural symbolic model. In the context of text-editing image retrieval, we validate the effectiveness of our method in CSS and CRIR dataset. Besides, CRIR is a new synthetic dataset generated by us, which we will publish it soon for future use.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
