اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدThe Pseudoforest analogue for the Strong Nine Dragon Tree Conjecture is True
66
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We prove that for any positive integers $k$ and $d$, if a graph $G$ has maximum average degree at most $2k + frac{2d}{d+k+1}$, then $G$ decomposes into $k+1$ pseudoforests $C_{1},ldots,C_{k+1}$ such that there is an $i$ such that for every connected component $C$ of $C_{i}$, we have that $e(C) leq d$.
قيم البحث
اقرأ أيضاً
The Strong Nine Dragon Tree Conjecture asserts that for any integers $k$ and $d$ any graph with fractional arboricity at most $k + frac{d}{d+k+1}$ decomposes into $k+1$ forests, such that for at least one of the forests, every connected component con
tains at most $d$ edges. We prove this conjecture when $d leq k+1$. We also prove an approximate version of this conjecture, that is, we prove that for any positive integers $k$ and $d$, any graph with fractional arboricity at most $k + frac{d}{d+k+1}$ decomposes into $k+1$ forests, such that one for at least one of the forests, every connected component contains at most $d + frac{d(k (2lceil frac{d}{k+1} +2 rceil)^{lceil frac{d}{k+1} + 2) rceil} - k)}{k+1} $ edges.
We prove that there is $c>0$ such that for all sufficiently large $n$, if $T_1,dots,T_n$ are any trees such that $T_i$ has $i$ vertices and maximum degree at most $cn/log n$, then ${T_1,dots,T_n}$ packs into $K_n$. Our main result actually allows to
replace the host graph $K_n$ by an arbitrary quasirandom graph, and to generalize from trees to graphs of bounded degeneracy that are rich in bare paths, contain some odd degree vertices, and only satisfy much less stringent restrictions on their number of vertices.
In the 3SUM-Indexing problem the goal is to preprocess two lists of elements from $U$, $A=(a_1,a_2,ldots,a_n)$ and $B=(b_1,b_2,...,b_n)$, such that given an element $cin U$ one can quickly determine whether there exists a pair $(a,b)in A times B$ whe
re $a+b=c$. Goldstein et al.~[WADS2017] conjectured that there is no algorithm for 3SUM-Indexing which uses $n^{2-Omega(1)}$ space and $n^{1-Omega(1)}$ query time. We show that the conjecture is false by reducing the 3SUM-Indexing problem to the problem of inverting functions, and then applying an algorithm of Fiat and Naor [SICOMP1999] for inverting functions.
We show that all nontrivial members of the Kinoshita-Terasaka and Conway knot families satisfy the purely cosmetic surgery conjecture.
We prove that any quasirandom graph with $n$ vertices and $rn$ edges can be decomposed into $n$ copies of any fixed tree with $r$ edges. The case of decomposing a complete graph establishes a conjecture of Ringel from 1963.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
