Families of trees decompose the random graph in any arbitrary way

Details Families of trees decompose the random graph in any arbitrary way Families of trees decompose the random graph in any arbitrary way

2002-10-22

arxiv.org/abs/math/0210339v1

Mathematics

Combinatorics

20 pages

Scientific paper

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 $\alpha_1 e(H_1) + ... + \alpha_k e(H_k) = m$ where each $\alpha_i$ is a nonnegative integer, there is a coloring of the edges of $G$ with $\alpha_1+...+\alpha_k$ colors such that exactly $\alpha_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$.

Affiliated with

Also associated with

No associations

Rating

Families of trees decompose the random graph in any arbitrary way does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Families of trees decompose the random graph in any arbitrary way, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Families of trees decompose the random graph in any arbitrary way will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-505923