On a uniformly random chord diagram and its intersection graph

DOI10.1016/J.DISC.2016.11.004zbMATH Open1362.05051arXiv1501.01489OpenAlexW2963972646MaRDI QIDQ2397541FDOQ2397541

Hüseyin Acan

Publication date: 22 May 2017

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: A chord diagram refers to a set of chords with distinct endpoints on a circle. The intersection graph of a chord diagram $calC$ is defined by substituting the chords of $calC$ with vertices and by adding edges between two vertices whenever the corresponding two chords cross each other. Let $C_n$ and $G_n$ denote the chord diagram chosen uniformly at random from all chord diagrams with $n$ chords and the corresponding intersection graph, respectively. We analyze $C_n$ and $G_n$ as $n$ tends to infinity. In particular, we study the degree of a random vertex in $G_n$, the $k$-core of $G_n$, and the number of strong components of the directed graph obtained from $G_n$ by orienting edges by flipping a fair coin for each edge. We also give two equivalent evolutions of a random chord diagram and show that, with probability approaching $1$, a chord diagram produced after $m$ steps of these evolutions becomes monolithic as $m$ tends to infinity and stays monolithic afterward forever.

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

Recommendations

• Formation of a giant component in the intersection graph of a random chord diagram
• Terminal chords in connected chord diagrams
• Linear chord diagrams with long chords
• The expected genus of a random chord diagram
• Enumeration problems on the expansion of a chord diagram

zbMATH Keywords

evolutionchord diagram\(k\)-coredegree of a chordintersection graph of a chord diagrammonolithic chord diagram

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Planar graphs; geometric and topological aspects of graph theory (05C10)

Cites Work

• Title not available (Why is that?)
• Emergence of Scaling in Random Networks
• The degree sequence of a scale-free random graph process
• On the Vassiliev knot invariants
• The Euler characteristic of the moduli space of curves
• Introduction to Vassiliev knot invariants
• Topological classification and enumeration of RNA structures by genus
• The Distribution of Crossings of Chords Joining Pairs of 2n Points on a Circle
• Crossings and nestings of matchings and partitions
• The asymptotics of monotone subsequences of involutions
• Combinatorial Computational Biology of RNA
• RNA folding and large \(N\) matrix theory
• Title not available (Why is that?)
• ENUMERATION OF CHORD DIAGRAMS AND AN UPPER BOUND FOR VASSILIEV INVARIANTS
• Invariant tensor formulas via chord diagrams
• Title not available (Why is that?)
• Counting non-isomorphic chord diagrams
• Sur Un Problème De Configurations Et Sur Les Fractions Continues
• Limiting distribution of maximal crossing and nesting of Poissonized random matchings
• On a class of linked diagrams. II: Asymptotics
• The expected genus of a random chord diagram
• The genus of a random chord diagram is asymptotically normal
• Linearized chord diagrams and an upper bound for vassiliev invariants
• Formation of a giant component in the intersection graph of a random chord diagram
• Hamilton cycles in a random tournament

Cited In (3)

• Lower bounds for the probability of a union via chordal graphs
• Formation of a giant component in the intersection graph of a random chord diagram
• Enumeration of even and odd chord diagrams

This page was built for publication: On a uniformly random chord diagram and its intersection graph

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