اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدLights Out On A Random Graph
170
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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$ sufficien
t 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)$.
We study the distributional properties of horizontal visibility graphs associated with random restrictive growth sequences and random set partitions of size $n.$ Our main results are formulas expressing the expected degree of graph nodes in terms of
simple explicit functions of a finite collection of Stirling and Bernoulli numbers.
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 d
ramatically 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 prove an asymptotic formula for the number of orientations with given out-degree (score) sequence for a graph $G$. The graph $G$ is assumed to have average degrees at least $n^{1/3 + varepsilon}$ for some $varepsilon > 0$, and to have strong mixin
g properties, while the maximum imbalance (out-degree minus in-degree) of the orientation should be not too large. Our enumeration results have applications to the study of subdigraph occurrences in random orientations with given imbalance sequence. As one step of our calculation, we obtain new bounds for the maximum likelihood estimators for the Bradley-Terry model of paired comparisons.
The behavior of a certain random growth process is analyzed on arbitrary regular and non-regular graphs. Our argument is based on the Expander Mixing Lemma, which entails that the results are strongest for Ramanujan graphs, which asymptotically maxim
ize the spectral gap. Further, we consider ErdH{o}s--Renyi random graphs and compare our theoretical results with computational experiments on flip graphs of point configurations. The latter is relevant for enumerating triangulations.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
