Decompositions into subgraphs of small diameter - Mathematics > CombinatoricsReport as inadecuate

Decompositions into subgraphs of small diameter - Mathematics > Combinatorics - Download this document for free, or read online. Document in PDF available to download.

Abstract: We investigate decompositions of a graph into a small number of low diametersubgraphs. Let Pn,\epsilon,d be the smallest k such that every graph G=V,Eon n vertices has an edge partition E=E 0 \cup E 1 \cup

. \cup E k such that|E 0| \leq \epsilon n^2 and for all 1 \leq i \leq k the diameter of thesubgraph spanned by E i is at most d. Using Szemer\-edi-s regularity lemma,Polcyn and Ruci\-nski showed that Pn,\epsilon,4 is bounded above by aconstant depending only \epsilon. This shows that every dense graph can bepartitioned into a small number of ``small worlds- provided that few edges canbe ignored. Improving on their result, we determine Pn,\epsilon,d within anabsolute constant factor, showing that Pn,\epsilon,2 = \Thetan is unboundedfor \epsilon < 1-4, Pn,\epsilon,3 = \Theta1-\epsilon^2 for \epsilon >n^{-1-2} and Pn,\epsilon,4 = \Theta1-\epsilon for \epsilon > n^{-1}. Wealso prove that if G has large minimum degree, all the edges of G can becovered by a small number of low diameter subgraphs. Finally, we extend some ofthese results to hypergraphs, improving earlier work of Polcyn, R\-odl,Ruci\-nski, and Szemer\-edi.

Author: Jacob Fox, Benny Sudakov



Related documents