Small complete minors above the extremal edge density
From MaRDI portal
(Redirected from Publication:313429)
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.
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
- scientific article; zbMATH DE number 1003278 (Why is no real title available?)
- scientific article; zbMATH DE number 3641497 (Why is no real title available?)
- scientific article; zbMATH DE number 1870233 (Why is no real title available?)
- scientific article; zbMATH DE number 878896 (Why is no real title available?)
- A Separator Theorem for Nonplanar Graphs
- A sublinear bipartiteness tester for bounded degree graphs
- An extremal function for contractions of graphs
- Approximation algorithms for unique games
- Expander graphs and their applications
- Graph minors. XIII: The disjoint paths problem
- Highly linked graphs
- Homomorphieeigenschaften und mittlere Kantendichte von Graphen
- Homomorphiesätze für Graphen
- Lower bound of the Hadwiger number of graphs by their average degree
- Minors in expanding graphs
- Pseudo-random graphs
- Ramanujan graphs
- Small complete minors above the extremal edge density
- Small minors in dense graphs
- Small topological complete subgraphs of ``dense graphs
- The extremal function for complete minors
Cited in
(17)- Towards the Erdős-Gallai cycle decomposition conjecture
- Hypergraphs with no tight cycles
- Finding and using expanders in locally sparse graphs
- Logarithmically small minors and topological minors
- Towards the Erdős-Gallai cycle decomposition conjecture
- Compact topological minors in graphs
- Minors in expanding graphs
- Tree densities in sparse graph classes
- A tight Erdős-Pósa function for wheel minors
- Finding large expanders in graphs: from topological minors to induced subgraphs
- Rainbow Turán number of clique subdivisions
- A note on sublinear separators and expansion
- Polynomial expansion and sublinear separators
- Small complete minors above the extremal edge density
- Short proofs of some extremal results. II.
- scientific article; zbMATH DE number 1870233 (Why is no real title available?)
- Rolling backwards can move you forward: on embedding problems in sparse expanders
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)
