Random graphs containing few disjoint excluded minors. Issue 2 (27th July 2012)

• Record Type: Journal Article
• Authors: McDiarmid, Colin; Kurauskas, Valentas
• Is Part Of: Random structures & algorithms. Volume 44:Issue 2(2014)
• Page Start: 240
• Page End: 268
• Publication Date: 2012-07-27
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20447
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>The Erdős‐Pósa theorem (1965) states that in each graph <italic>G</italic> which contains at most <italic>k</italic> disjoint cycles, there is a 'blocking' set <italic>B</italic> of at most <italic>f</italic>(<italic>k</italic>) vertices such that the graph <italic>G</italic> – <italic>B</italic> is acyclic. Robertson and Seymour (1986) give an extension concerning any minor‐closed class <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2sb8x" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley::media:rsa20447:rsa20447-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi mathvariant="script">A</mml:mi></mml:math></alternatives> of graphs, as long as <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2sb9g" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley::media:rsa20447:rsa20447-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi mathvariant="script">A</mml:mi></mml:math></alternatives> does not contain all planar graphs: in each graph <italic>G</italic> which contains at most <italic>k</italic> disjoint excluded minors for <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2sb4q" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley::media:rsa20447:rsa20447-math-0003" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi mathvariant="script">A</mml:mi></mml:math></alternatives>, there is a set <italic>B</italic> of at most <italic>g</italic>(<italic>k</italic>) vertices such that <italic>G</italic> – <italic>B</italic> is in <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2sb58" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley::media:rsa20447:rsa20447-math-0004" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi mathvariant="script">A</mml:mi></mml:math></alternatives>.</p> <p>In an earlier paper (Kurauskas and McDiarmid, Combin, Probab Comput 20 (2011) 763–775), we showed that, amongst all graphs on vertex set <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2sb6t" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley::media:rsa20447:rsa20447-math-0005" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo stretchy="false">[</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="false">]</mml:mo><mml:mo>=</mml:mo><mml:mo>{</mml:mo><mml:mn>1</mml:mn><mml:mo>, </mml:mo><mml:mo>…</mml:mo><mml:mo>, </mml:mo><mml:mi>n</mml:mi><mml:mo>}</mml:mo></mml:mrow></mml:math></alternatives> which contain at most <italic>k</italic> disjoint cycles, all but an exponentially small proportion contain a blocking set of just <italic>k</italic> vertices.</p> <p>In the present paper we build on the previous work, and give an extension concerning any minor‐closed graph class <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2sb7c" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley::media:rsa20447:rsa20447-math-0006" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi mathvariant="script">A</mml:mi></mml:math></alternatives> with 2‐connected excluded minors, as long as <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2sbb1" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley::media:rsa20447:rsa20447-math-0007" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi mathvariant="script">A</mml:mi></mml:math></alternatives> does not contain all fans (here a 'fan' is a graph consisting of a path together with a vertex joined to each vertex on the path). We show that amongst all graphs <italic>G</italic> on <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2sbck" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley::media:rsa20447:rsa20447-math-0008" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo stretchy="false">[</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="false">]</mml:mo></mml:mrow></mml:math></alternatives> which contain at most <italic>k</italic> disjoint excluded minors for <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2sbd4" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley::media:rsa20447:rsa20447-math-0009" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi mathvariant="script">A</mml:mi></mml:math></alternatives>, all but an exponentially small proportion contain a set <italic>B</italic> of <italic>k</italic> vertices such that <italic>G</italic> – <italic>B</italic> is in <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2s5w8" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley::media:rsa20447:rsa20447-math-0010" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi mathvariant="script">A</mml:mi></mml:math></alternatives>. (This is not the case when <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2s5vq" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley::media:rsa20447:rsa20447-math-0011" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi mathvariant="script">A</mml:mi></mml:math></alternatives> contains all fans.) For a random graph <italic>R</italic><sub><italic>n</italic></sub> sampled uniformly from the graphs on <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2s5zc" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley::media:rsa20447:rsa20447-math-0012" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo stretchy="false">[</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="false">]</mml:mo></mml:mrow></mml:math></alternatives> with at most <italic>k</italic> disjoint excluded minors for <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2s5xt" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley::media:rsa20447:rsa20447-math-0013" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi mathvariant="script">A</mml:mi></mml:math></alternatives>, we consider also vertex degrees and the uniqueness of small blockers, the clique number and chromatic number, and the probability of being connected. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 240‐268, 2014</p> </abstract>