اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOn the Cycle Space of a Random Graph
65
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Write $mathcal{C}(G)$ for the cycle space of a graph $G$, $mathcal{C}_kappa(G)$ for the subspace of $mathcal{C}(G)$ spanned by the copies of the $kappa$-cycle $C_kappa$ in $G$, $mathcal{T}_kappa$ for the class of graphs satisfying $mathcal{C}_kappa(G)=mathcal{C}(G)$, and $mathcal{Q}_kappa$ for the class of graphs each of whose edges lies in a $C_kappa$. We prove that for every odd $kappa geq 3$ and $G=G_{n,p}$, [max_p , Pr(G in mathcal{Q}_kappa setminus mathcal{T}_kappa) rightarrow 0;] so the $C_kappa$s of a random graph span its cycle space as soon as they cover its edges. For $kappa=3$ this was shown by DeMarco, Hamm and Kahn (2013).
قيم البحث
اقرأ أيضاً
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.
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.
The majority of graphs whose sandpile groups are known are either regular or simple. We give an explicit formula for a family of non-regular multi-graphs called thick cycles. A thick cycle graph is a cycle where multi-edges are permitted. Its sandpil
e group is the direct sum of cyclic groups of orders given by quotients of greatest common divisors of minors of its Laplacian matrix. We show these greatest common divisors can be expressed in terms of monomials in the graphs edge multiplicities.
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)$.
In this article we consider the cycle structure of compositions of pairs of involutions in the symmetric group S_n chosen uniformly at random. These can be modeled as modified 2-regular graphs, giving rise to exponential generating functions. A compo
sition of two random involutions in S_n typically has about n^(1/2) cycles, and the cycles are characteristically of length n^(1/2). Compositions of two random fixed-point-free involutions, on the other hand, typically have about log n cycles and are closely related to permutations with all cycle lengths even. The number of factorizations of a random permutation into two involutions appears to be asymptotically lognormally distributed, which we prove for a closely related probabilistic model. This study is motivated by the observation that the number of involutions in [n] is (n!)^(1/2) times a subexponential factor; more generally the number of permutations with all cycle lengths in a finite set S is n!^(1-1/m) times a subexponential factor, and the typical number of k-cycles is nearly n^(k/m)/k. Connections to pattern avoidance in involutions are also considered.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
