Formation of a giant component in the intersection graph of a random chord diagram

DOI10.1016/J.JCTB.2017.02.001MaRDI QIDQ2396892zbMATH OpenOpenAlexFDO

Authors Hüseyin Acan, Boris Pittel

Publication date 26 May 2017

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

asymptoticsenumerationchord diagramcrossinggiant component

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Exact enumeration problems, generating functions (05A15)

Abstract: We study the number of chords and the number of crossings in the largest component of a random chord diagram when the chords are sparsely crossing. This is equivalent to studying the number of vertices and the number of edges in the largest component of the random intersection graph. Denoting the number of chords by n and the number of crossings by m, when m/nlog(n) tends to a limit in (0,2/pi^2), we show that the chord diagram chosen uniformly at random from all the diagrams with given parameters has a component containing almost all the crossings and a positive fraction of chords. On the other hand, when m < n/14, the size of the largest component is of size O(log n). One of the key analytical ingredients is an asymptotic expression for the number of chord diagrams with parameters n and m for m <(2/pi^2)nlog(n), based on the Touchard-Riordan formula and the Jacobi identity for Euler partition function.

Recommendations

• On a uniformly random chord diagram and its intersection graph
• Component evolution in general random intersection graphs
• The largest component in critical random intersection graphs
• Central limit theorem for the largest component of random intersection graph
• Publication:4502534

Cites work

• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 192838 (Why is no real title available?)
• scientific article; zbMATH DE number 3537726 (Why is no real title available?)
• scientific article; zbMATH DE number 1231230 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 2000846 (Why is no real title available?)
• scientific article; zbMATH DE number 1504583 (Why is no real title available?)
• scientific article; zbMATH DE number 3349081 (Why is no real title available?)
• A combinatorial proof of the log-concavity of a famous sequence counting permutations
• AN UPPER BOUND FOR THE NUMBER OF VASSILIEV KNOT INVARIANTS
• Another proof of the Harer-Zagier formula
• Application of the Berry-Esseen inequality to combinatorial estimates
• Central and local limit theorems applied to asymptotic enumeration
• Chords, trees and permutations
• Circle graph obstructions
• Counting non-isomorphic chord diagrams
• Crossings and nestings of matchings and partitions
• ENUMERATION OF CHORD DIAGRAMS AND AN UPPER BOUND FOR VASSILIEV INVARIANTS
• Euler circuits and DNA sequencing by hybridization
• Introduction to Vassiliev knot invariants
• Large deviations and moments for the Euler characteristic of a random surface
• Linearized chord diagrams and an upper bound for vassiliev invariants
• On Dimensions of a Random Solid Diagram
• On a class of linked diagrams. II: Asymptotics
• On a likely shape of the random Ferrers diagram
• On a surface formed by randomly gluing together polygonal discs
• On a uniformly random chord diagram and its intersection graph
• On the Convolution of Logarithmically Concave Sequences
• On the connected components of a random permutation graph with a given number of edges
• On the genus of a random graph
• Paths in graphs
• Poisson-Dirichlet distribution for random Belyi surfaces
• Sur Un Problème De Configurations Et Sur Les Fractions Continues
• Sur les partitions non croisées d'un cycle. (The non-crossed partitions of a cycle)
• The Distribution of Crossings of Chords Joining Pairs of 2n Points on a Circle
• The Euler characteristic of the moduli space of curves
• The asymptotics of monotone subsequences of involutions
• The diameter of a scale-free random graph
• The expected genus of a random chord diagram
• The genus of a random chord diagram is asymptotically normal
• The genus of a random graph
• Topological characteristics of random triangulated surfaces
• Touchard-Riordan formulas, T-fractions, and Jacobi's triple product identity
• Vassiliev invariants and a strange identity related to the Dedekind eta-function

Cited in

(1)

• On a uniformly random chord diagram and its intersection graph

This page was built for publication: Formation of a giant component in the intersection graph of a random chord diagram

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