Decomposing a graph into expanding subgraphs. Issue 1 (13th August 2017)

• Record Type: Journal Article
• Authors: Moshkovitz, Guy; Shapira, Asaf
• Is Part Of: Random structures & algorithms. Volume 52:Issue 1(2018)
• Page Start: 158
• Page End: 178
• Publication Date: 2017-08-13
• Subjects: graph decomposition -- graph expansion -- hypercube -- small set expansion; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20727
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : A paradigm that was successfully applied in the study of both pure and algorithmic problems in graph theory can be colloquially summarized as stating that any graph is close to being the disjoint union of expanders . Our goal in this paper is to show that in several of the instantiations of the above approach, the quantitative bounds that were obtained are essentially best possible. Three examples of our results are the following: A classical result of Lipton, Rose and Tarjan from 1979 states that if F is a hereditary family of graphs and every graph in F has a vertex separator of size n / ( log ⁡ n ) 1 + o ( 1 ), then every graph in F has O ( n ) edges. We construct a hereditary family of graphs with vertex separators of size n / ( log ⁡ n ) 1 − o ( 1 ) such that not all graphs in the family have O ( n ) edges. Trevisan and Arora‐Barak‐Steurer have recently shown that given a graph G, one can remove only 1% of its edges to obtain a graph in which each connected component has good expansion properties. We show that in both of these decomposition results, the expansion properties they guarantee are essentially best possible, even when one is allowed to remove 99% of G 's edges. Sudakov and the second author have recently shown that every graph with average degree d contains an n ‐vertex subgraph with average degree at least ( 1 − o ( 1 ) ) d and vertex expansion 1 / ( log ⁡ n ) 1 + o ( 1 ) . We show that one cannot guarantee a better vertex expansion even if allowing the average degree to be O (1). The above results are obtained as corollaries of a new family of graphs which we construct in this paper. These graphs have a super‐linear number of edges and nearly logarithmic girth, yet each of their subgraphs has (optimally) poor expansion properties.