Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Pseudoforest analogue for the Strong Nine Dragon Tree Conjecture is True
66
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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$.
rate research
Read More
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 contains 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$ where $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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
