Minors in random regular graphs

DOI10.1002/RSA.20285zbMATH Open1201.05086arXiv0803.3001OpenAlexW3083045382MaRDI QIDQ3055786FDOQ3055786

Authors: Nikolaos Fountoulakis, Daniela Kühn, Deryk Osthus 

Publication date: 9 November 2010

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Abstract: We show that there is a constant c>0 so that for any fixed r which is at least 3 a.a.s. an r-regular graph on n vertices contains a complete graph on c n^{1/2} vertices as a minor. This confirms a conjecture of Markstrom. Since any minor of an r-regular graph on n vertices has at most rn/2 edges, our bound is clearly best possible up to the value of the constant c. As a corollary, we also obtain the likely order of magnitude of the largest complete minor in a random graph G(n,p) during the phase transition (i.e. when pn is close to 1).

Full work available at URL: https://arxiv.org/abs/0803.3001

Recommendations

• Large complete minors in random subgraphs
• Complete minors in cubic graphs with few short cycles and random cubic graphs.
• Minors in expanding graphs

zbMATH Keywords

graph minorsrandom regular graphsHadwiger number

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph minors (05C83)

Cites Work

• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Hadwiger's conjecture is true for almost every graph
• Minors in expanding graphs
• Component behavior near the critical point of the random graph process
• Cycles in a random graph near the critical point
• The asymptotic number of labeled graphs with given degree sequences
• The Evolution of Random Graphs
• Random Regular Graphs: Asymptotic Distributions and Contiguity
• The Structure of a Random Graph at the Point of the Phase Transition
• Complete minors in cubic graphs with few short cycles and random cubic graphs.
• Title not available (Why is that?)

Cited In (11)

• Expansion in supercritical random subgraphs of the hypercube and its consequences
• Waiter-Client and Client-Waiter planarity, colorability and minor games
• Minimum degree and graph minors
• Identifying the minor set cover of dense connected bipartite graphs via random matching edge sets
• Rolling backwards can move you forward: on embedding problems in sparse expanders
• Complete minors in cubic graphs with few short cycles and random cubic graphs.
• Complete Minors in Graphs Without Sparse Cuts
• Large complete minors in random subgraphs
• Even cycle decompositions of 4-regular graphs and line graphs
• Minors in graphs of large \(\theta_r\)-girth
• Minimal functions on the random graph

This page was built for publication: Minors in random regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3055786)