Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAn Approximate Version of the Strong Nine Dragon Tree Conjecture
119
0
0.0
(
0
)
Authors
Benjamin Moore
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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$.
We prove that for any $varepsilon>0$, for any large enough $t$, there is a graph $G$ that admits no $K_t$-minor but admits a $(frac32-varepsilon)t$-colouring that is frozen with respect to Kempe changes, i.e. any two colour classes induce a connected component. This disproves three conjectures of Las Vergnas and Meyniel from 1981.
We say that the families $mathcal F_1,ldots, mathcal F_{s+1}$ of $k$-element subsets of $[n]$ are cross-dependent if there are no pairwise disjoint sets $F_1,ldots, F_{s+1}$, where $F_iin mathcal F_i$ for each $i$. The rainbow version of the ErdH os Matching Conjecture due to Aharoni and Howard and independently to Huang, Loh and Sudakov states that $min_{i} |mathcal F_i|le maxbig{{nchoose k}-{n-schoose k}, {(s+1)k-1choose k}big}$. In this paper, we prove this conjecture for $n>3e(s+1)k$ and $s>10^7$. One of the main tools in the proof is a concentration inequality due to Frankl and the author.
Loebl, Komlos, and Sos conjectured that any graph with at least half of its vertices of degree at least k contains every tree with at most k edges. We propose a version of this conjecture for skewed trees, i.e., we consider the class of trees with at most k edges such that the sizes of the colour classes of the trees have a given ratio. We show that our conjecture is asymptotically correct for dense graphs. The proof relies on the regularity method. Our result implies bounds on Ramsey number of several trees of given skew.
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
