اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدDistinct Fringe Subtrees in Random Trees
66
0
0.0
(
0
)
نشر من قبل
Louisa Seelbach Benkner
تاريخ النشر
2021
مجال البحث
الهندسة المعلوماتية
والبحث باللغة
English
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
A fringe subtree of a rooted tree is a subtree induced by one of the vertices and all its descendants. We consider the problem of estimating the number of distinct fringe subtrees in two types of random trees: simply generated trees and families of increasing trees (recursive trees, $d$-ary increasing trees and generalized plane-oriented recursive trees). We prove that the order of magnitude of the number of distinct fringe subtrees (under rather mild assumptions on what `distinct means) in random trees with $n$ vertices is $n/sqrt{log n}$ for simply generated trees and $n/log n$ for increasing trees.
قيم البحث
اقرأ أيضاً
A fringe subtree of a rooted tree is a subtree consisting of one of the nodes and all its descendants. In this paper, we are specifically interested in the number of non-isomorphic trees that appear in the collection of all fringe subtrees of a binar
y tree. This number is analysed under two different random models: uniformly random binary trees and random binary search trees. In the case of uniformly random binary trees, we show that the number of non-isomorphic fringe subtrees lies between $c_1n/sqrt{ln n}(1+o(1))$ and $c_2n/sqrt{ln n}(1+o(1))$ for two constants $c_1 approx 1.0591261434$ and $c_2 approx 1.0761505454$, both in expectation and with high probability, where $n$ denotes the size (number of leaves) of the uniformly random binary tree. A similar result is proven for random binary search trees, but the order of magnitude is $n/ln n$ in this case. Our proof technique can also be used to strengthen known results on the number of distinct fringe subtrees (distinct in the sense of ordered trees). This quantity is of the same order of magnitude in both cases, but with slightly different constants in the upper and lower bounds.
For a connected graph, a {em minimum vertex separator} is a minimum set of vertices whose removal creates at least two connected components. The vertex connectivity of the graph refers to the size of the minimum vertex separator and a graph is $k$-ve
rtex connected if its vertex connectivity is $k$, $kgeq 1$. Given a $k$-vertex connected graph $G$, the combinatorial problem {em vertex connectivity augmentation} asks for a minimum number of edges whose augmentation to $G$ makes the resulting graph $(k+1)$-vertex connected. In this paper, we initiate the study of $r$-vertex connectivity augmentation whose objective is to find a $(k+r)$-vertex connected graph by augmenting a minimum number of edges to a $k$-vertex connected graph, $r geq 1$. We shall investigate this question for the special case when $G$ is a tree and $r=2$. In particular, we present a polynomial-time algorithm to find a minimum set of edges whose augmentation to a tree makes it 3-vertex connected. Using lower bound arguments, we show that any tri-vertex connectivity augmentation of trees requires at least $lceil frac {2l_1+l_2}{2} rceil$ edges, where $l_1$ and $l_2$ denote the number of degree one vertices and degree two vertices, respectively. Further, we establish that our algorithm indeed augments this number, thus yielding an optimum algorithm.
For $n > 2k geq 4$ we consider intersecting families $mathcal F$ consisting of $k$-subsets of ${1, 2, ldots, n}$. Let $mathcal I(mathcal F)$ denote the family of all distinct intersections $F cap F$, $F eq F$ and $F, Fin mathcal F$. Let $mathcal A$
consist of the $k$-sets $A$ satisfying $|A cap {1, 2, 3}| geq 2$. We prove that for $n geq 50 k^2$ $|mathcal I(mathcal F)|$ is maximized by $mathcal A$.
For a family $mathcal F$, let $mathcal D(mathcal F)$ stand for the family of all sets that can be expressed as $Fsetminus G$, where $F,Gin mathcal F$. A family $mathcal F$ is intersecting if any two sets from the family have non-empty intersection. I
n this paper, we study the following question: what is the maximum of $|mathcal D(mathcal F)|$ for an intersecting family of $k$-element sets? Frankl conjectured that the maximum is attained when $mathcal F$ is the family of all sets containing a fixed element. We show that this holds if $n>50klog k$ and $k>50$. At the same time, we provide a counterexample for $n< 4k.$
We study hypergraph discrepancy in two closely related random models of hypergraphs on $n$ vertices and $m$ hyperedges. The first model, $mathcal{H}_1$, is when every vertex is present in exactly $t$ randomly chosen hyperedges. The premise of this is
closely tied to, and motivated by the Beck-Fiala conjecture. The second, perhaps more natural model, $mathcal{H}_2$, is when the entries of the $m times n$ incidence matrix is sampled in an i.i.d. fashion, each with probability $p$. We prove the following: 1. In $mathcal{H}_1$, when $log^{10}n ll t ll sqrt{n}$, and $m = n$, we show that the discrepancy of the hypergraph is almost surely at most $O(sqrt{t})$. This improves upon a result of Ezra and Lovett for this range of parameters. 2. In $mathcal{H}_2$, when $p= frac{1}{2}$, and $n = Omega(m log m)$, we show that the discrepancy is almost surely at most $1$. This answers an open problem of Hoberg and Rothvoss.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
