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

DOI10.1016/J.JCTB.2017.02.001zbMATH Open1362.05117arXiv1406.2867OpenAlexW2963624814MaRDI QIDQ2396892FDOQ2396892

Authors: Hüseyin Acan, Boris Pittel 

Publication date: 26 May 2017

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

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.

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

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

zbMATH Keywords

asymptoticsenumerationchord diagramcrossinggiant component

Mathematics Subject Classification ID

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

Cites Work

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

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)