اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOn the probability that a random subtree is spanning
62
0
0.0
(
0
)
تأليف
Stephan Wagner
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We consider the quantity $P(G)$ associated with a graph $G$ that is defined as the probability that a randomly chosen subtree of $G$ is spanning. Motivated by conjectures due to Chin, Gordon, MacPhee and Vincent on the behaviour of this graph invariant depending on the edge density, we establish first that $P(G)$ is bounded below by a positive constant provided that the minimum degree is bounded below by a linear function in the number of vertices. Thereafter, the focus is shifted to the classical ErdH{o}s-Renyi random graph model $G(n,p)$. It is shown that $P(G)$ converges in probability to $e^{-1/(ep_{infty})}$ if $p to p_{infty} > 0$ and to $0$ if $p to 0$.
قيم البحث
اقرأ أيضاً
This extends a theorem of Davenport and Erdos on sequences of rational integers to sequences of integral ideals in arbitrary number fields $K$. More precisely, we introduce a logarithmic density for sets of integral ideals in $K$ and provide a formul
a for the logarithmic density of the set of so-called $mathscr A$-free ideals, i.e. integral ideals that are not multiples of any ideal from a fixed set $mathscr A$.
We study the large-$n$ limit of the probability $p_{2n,2k}$ that a random $2ntimes 2n$ matrix sampled from the real Ginibre ensemble has $2k$ real eigenvalues. We prove that, $$lim_{nrightarrow infty}frac {1}{sqrt{2n}} log p_{2n,2k}=lim_{nrightarrow
infty}frac {1}{sqrt{2n}} log p_{2n,0}= -frac{1}{sqrt{2pi}}zetaleft(frac{3}{2}right),$$ where $zeta$ is the Riemann zeta-function. Moreover, for any sequence of non-negative integers $(k_n)_{ngeq 1}$, $$lim_{nrightarrow infty}frac {1}{sqrt{2n}} log p_{2n,2k_n}=-frac{1}{sqrt{2pi}}zetaleft(frac{3}{2}right),$$ provided $lim_{nrightarrow infty} left(n^{-1/2}log(n)right) k_{n}=0$.
The bandwidth theorem [Mathematische Annalen, 343(1):175--205, 2009] states that any $n$-vertex graph $G$ with minimum degree $(frac{k-1}{k}+o(1))n$ contains all $n$-vertex $k$-colourable graphs $H$ with bounded maximum degree and bandwidth $o(n)$. I
n [arXiv:1612.00661] a random graph analogue of this statement is proved: for $pgg (frac{log n}{n})^{1/Delta}$ a.a.s. each spanning subgraph $G$ of $G(n,p)$ with minimum degree $(frac{k-1}{k}+o(1))pn$ contains all $n$-vertex $k$-colourable graphs $H$ with maximum degree $Delta$, bandwidth $o(n)$, and at least $C p^{-2}$ vertices not contained in any triangle. This restriction on vertices in triangles is necessary, but limiting. In this paper we consider how it can be avoided. A special case of our main result is that, under the same conditions, if additionally all vertex neighbourhoods in $G$ contain many copies of $K_Delta$ then we can drop the restriction on $H$ that $Cp^{-2}$ vertices should not be in triangles.
The Mahonian statistic is the number of
A subtree of a tree is any induced subgraph that is again a tree (i.e., connected). The mean subtree order of a tree is the average number of vertices of its subtrees. This invariant was first analyzed in the 1980s by Jamison. An intriguing open ques
tion raised by Jamison asks whether the maximum of the mean subtree order, given the order of the tree, is always attained by some caterpillar. While we do not completely resolve this conjecture, we find some evidence in its favor by proving different features of trees that attain the maximum. For example, we show that the diameter of a tree of order $n$ with maximum mean subtree order must be very close to $n$. Moreover, we show that the maximum mean subtree order is equal to $n - 2log_2 n + O(1)$. For the local mean subtree order, which is the average order of all subtrees containing a fixed vertex, we can be even more precise: we show that its maximum is always attained by a broom and that it is equal to $n - log_2 n + O(1)$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
