Minors in random regular graphs

DOI10.1002/RSA.20285MaRDI QIDQ3055786zbMATH OpenOpenAlexFDO

Authors Nikolaos Fountoulakis, Daniela Kühn, Deryk Osthus

Publication date 9 November 2010

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

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

zbMATH Keywords

graph minorsrandom regular graphsHadwiger number

Mathematics Subject Classification ID

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

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).

Recommendations

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

Cites work

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

Cited in

(12)

• scientific article; zbMATH DE number 1495914 (Why is no real title available?)
• 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)