Small complete minors above the extremal edge density
From MaRDI portal
Publication:313429
DOI10.1007/S00493-015-3013-2zbMATH Open1363.05241arXiv1208.3568OpenAlexW1970872869MaRDI QIDQ313429FDOQ313429
Authors: Asaf Shapira, Benny Sudakov 
Publication date: 9 September 2016
Published in: Combinatorica (Search for Journal in Brave)
Abstract: A fundamental result of Mader from 1972 asserts that a graph of high average degree contains a highly connected subgraph with roughly the same average degree. We prove a lemma showing that one can strengthen Mader's result by replacing the notion of high connectivity by the notion of vertex expansion. Another well known result in graph theory states that for every integer t there is a smallest real c(t) so that every n-vertex graph with c(t)n edges contains a K_t-minor. Fiorini, Joret, Theis and Wood conjectured that if an n-vertex graph G has (c(t)+epsilon)n edges then G contains a K_t-minor of order at most C(epsilon)log n. We use our extension of Mader's theorem to prove that such a graph G must contain a K_t-minor of order at most C(epsilon)log n loglog n. Known constructions of graphs with high girth show that this result is tight up to the loglog n factor.
Full work available at URL: https://arxiv.org/abs/1208.3568
Recommendations
- Two Minor Problems
- Disjoint complete minors and bipartite minors
- A Linear-Time Algorithm for Finding a Complete Graph Minor in a Dense Graph
- Minors in graphs of large \(\theta_r\)-girth
- Minors in expanding graphs
- Dense minors in graphs of large girth
- Clique minors in graphs and their complements
- \(K_4\)-minor-free induced subgraphs of sparse connected graphs
- \(K_{s,t}\) minors in \((s+t)\)-chromatic graphs. II
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- The extremal function for complete minors
- Graph minors. XIII: The disjoint paths problem
- Homomorphiesätze für Graphen
- Homomorphieeigenschaften und mittlere Kantendichte von Graphen
- An extremal function for contractions of graphs
- Expander graphs and their applications
- Lower bound of the Hadwiger number of graphs by their average degree
- Minors in expanding graphs
- Ramanujan graphs
- A Separator Theorem for Nonplanar Graphs
- Small topological complete subgraphs of ``dense graphs
- A sublinear bipartiteness tester for bounded degree graphs
- Highly linked graphs
- Approximation algorithms for unique games
- Title not available (Why is that?)
- Small complete minors above the extremal edge density
- Small minors in dense graphs
- Title not available (Why is that?)
- Pseudo-random graphs
Cited In (17)
- Minors in expanding graphs
- Rolling backwards can move you forward: on embedding problems in sparse expanders
- Tree densities in sparse graph classes
- A note on sublinear separators and expansion
- Title not available (Why is that?)
- Finding and using expanders in locally sparse graphs
- Small complete minors above the extremal edge density
- Towards the Erdős-Gallai cycle decomposition conjecture
- Logarithmically small minors and topological minors
- Short proofs of some extremal results. II.
- Rainbow Turán number of clique subdivisions
- Polynomial expansion and sublinear separators
- A tight Erdős-Pósa function for wheel minors
- Towards the Erdős-Gallai cycle decomposition conjecture
- Hypergraphs with no tight cycles
- Finding large expanders in graphs: from topological minors to induced subgraphs
- Compact topological minors in graphs
This page was built for publication: Small complete minors above the extremal edge density
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q313429)
