Families of trees decompose the random graph in any arbitrary way
| dc.creator | Yuster, Raphael | |
| dc.date | 2002-10-22 | |
| dc.date.accessioned | 2026-07-07T04:52:13Z | |
| dc.date.available | 2026-07-07T04:52:13Z | |
| dc.description | Let $F=\{H_1,...,H_k\}$ be a family of graphs. A graph $G$ with $m$ edges is called {\em totally $F$-decomposable} if for {\em every} linear combination of the form $α_1 e(H_1) + ... + α_k e(H_k) = m$ where each $α_i$ is a nonnegative integer, there is a coloring of the edges of $G$ with $α_1+...+α_k$ colors such that exactly $α_i$ color classes induce each a copy of $H_i$, for $i=1,...,k$. We prove that if $F$ is any fixed family of trees then $\log n/n$ is a sharp threshold function for the property that the random graph $G(n,p)$ is totally $F$-decomposable. In particular, if $H$ is a tree, then $\log n/n$ is a sharp threshold function for the property that $G(n,p)$ contains $\lfloor e(G)/e(H) \rfloor$ edge-disjoint copies of $H$. | |
| dc.description | 20 pages | |
| dc.identifier | https://arxiv.org/abs/math/0210339 | |
| dc.identifier | http://arxiv.org/abs/math/0210339 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/65389 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C80 | |
| dc.title | Families of trees decompose the random graph in any arbitrary way | |
| dc.type | text |