Asymptotic Properties of Some Minor-Closed Classes of Graphs. (September 2014)

• Record Type: Journal Article
• Authors: BOUSQUET-MÉLOU, MIREILLE; WELLER, KERSTIN; Broutin, Nicolas; Fill, James Allen; Nebel, Markus; Ward, Mark Daniel
• Is Part Of: Combinatorics, probability and computing. Volume 23:Number 5(2014:Sep.)
• Page Start: 749
• Page End: 795
• Publication Date: 2014-09
• Subjects: Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548314000303
• Languages: English
• ISSNs: 0963-5483

Abstract

<abstract abstract-type="normal"> <title> <x content-type="archive" xml:space="preserve">Abstract</x> </title> <p>Let <inline-formula><alternatives><inline-graphic xlink:href="ark:/27927/pgh1238jc39" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><tex-math><![CDATA[${\cal A}$]]></tex-math></alternatives></inline-formula> be a minor-closed class of labelled graphs, and let <inline-formula><alternatives><inline-graphic xlink:href="ark:/27927/pgh1238jc16" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><tex-math><![CDATA[${\cal G}_{n}$]]></tex-math></alternatives></inline-formula> be a random graph sampled uniformly from the set of <italic>n</italic>-vertex graphs of <inline-formula><alternatives><inline-graphic xlink:href="ark:/27927/pgh1238jc39" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><tex-math><![CDATA[${\cal A}$]]></tex-math></alternatives></inline-formula>. When <italic>n</italic> is large, what is the probability that <inline-formula><alternatives><inline-graphic xlink:href="ark:/27927/pgh1238jc16" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><tex-math><![CDATA[${\cal G}_{n}$]]></tex-math></alternatives></inline-formula> is connected? How many components does it have? How large is its biggest component? Thanks to the work of McDiarmid and his collaborators, these questions are now solved when all excluded minors are 2-connected.</p> <p>Using exact enumeration, we study a collection of classes <inline-formula><alternatives><inline-graphic xlink:href="ark:/27927/pgh1238jc39" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><tex-math><![CDATA[${\cal A}$]]></tex-math></alternatives></inline-formula> excluding non-2-connected minors, and show that their asymptotic behaviour may be rather different from the 2-connected case. This behaviour largely depends on the nature of the dominant singularity of the generating function <italic>C</italic>(<italic>z</italic>) that counts connected graphs of <inline-formula><alternatives><inline-graphic xlink:href="ark:/27927/pgh1238jc39" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><tex-math><![CDATA[${\cal A}$]]></tex-math></alternatives></inline-formula>. We classify our examples accordingly, thus taking a first step towards a classification of minor-closed classes of graphs. Furthermore, we investigate a parameter that has not received any attention in this context yet: the size of the root component. It follows non-Gaussian limit laws (Beta and Gamma), and clearly merits a systematic investigation.</p> </abstract>