On a uniformly random chord diagram and its intersection graph

DOI10.1016/J.DISC.2016.11.004MaRDI QIDQ2397541zbMATH OpenOpenAlexFDO

Authors Hüseyin Acan

Publication date 22 May 2017

Published in Discrete Mathematics (Search for Journal in Brave)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 475121 (Why is no real title available?)
• scientific article; zbMATH DE number 1504583 (Why is no real title available?)
• Combinatorial Computational Biology of RNA
• Counting non-isomorphic chord diagrams
• Crossings and nestings of matchings and partitions
• ENUMERATION OF CHORD DIAGRAMS AND AN UPPER BOUND FOR VASSILIEV INVARIANTS
• Emergence of Scaling in Random Networks
• Formation of a giant component in the intersection graph of a random chord diagram
• Hamilton cycles in a random tournament
• Introduction to Vassiliev knot invariants
• Invariant tensor formulas via chord diagrams
• Limiting distribution of maximal crossing and nesting of Poissonized random matchings
• Linearized chord diagrams and an upper bound for vassiliev invariants
• On a class of linked diagrams. II: Asymptotics
• On the Vassiliev knot invariants
• RNA folding and large \(N\) matrix theory
• Sur Un Problème De Configurations Et Sur Les Fractions Continues
• 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 degree sequence of a scale-free random graph process
• The expected genus of a random chord diagram
• The genus of a random chord diagram is asymptotically normal
• Topological classification and enumeration of RNA structures by genus

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)