2003/05/25 by Raphael Yuster, Yuster, Raphael · 1 citation
Computer Science · Engineering · Mathematics · #05C70 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Optimization and Packing Problems #graph theory and CDMA systems #math.CO #msc:05C70
paper · pdf · doi:10.48550/arxiv.math/0305350
8 pages
openalex publication_date 2003/05/25 · arxiv created 2003/07/27 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let \cal F be a family of graphs. For a graph G, the \em \cal F-packing number, denoted ν\cal F(G), is the maximum number of pairwise edge-disjoint elements of \cal F in G. A function ψ from the set of elements of \cal F in G to [0,1] is a \em fractional \cal F-packing of G if ∑_e ∈ H ∈ \cal F ψ(H) ≤ 1 for each e ∈ E(G). The \em fractional \cal F-packing number, denoted ν^*\cal F(G), is defined to be the maximum value of ∑_H ∈ G \choose \cal F ψ(H) over all fractional \cal F-packings ψ. Our main result is that ν^*\cal F(G)-ν\cal F(G) = o(|V(G)|2). Furthermore, a set of ν\cal F(G) -o(|V(G)|2) edge-disjoint elements of \cal F in G can be found in randomized polynomial time. For the special case \cal F=\H0\ we obtain a significantly simpler proof of a recent difficult result of Haxell and Rödl \citeHaRo that ν^*H0(G)-νH0(G) = o(|V(G)|2).