Crossings in Randomly Embedded Graphs

2022/05/09 by Santiago Arenas-Velilla, Arenas-Velilla, Santiago, Octavio Arizmendi +1
Computer Science · Mathematics · #05C80 #Combinatorics (math.CO) #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Stochastic processes and statistical mechanics #Topological and Geometric Data Analysis

paper · pdf · doi:10.48550/arxiv.2205.03995

openalex publication_date 2022/05/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider the number of crossings in a graph which is embedded randomly on a convex set of points. We give an estimate to the normal distribution in Kolmogorov distance which implies a convergence rate of order n^-1/2 for various families of graphs, including random chord diagrams or full cycles.

Related

• Central limit theorem for crossings in randomly embedded graphs
• Limit theorems for the number of crossings and stress in projections of the random geometric graph
• Convergence rates of limit theorems in random chord diagrams
• Convergence Rate for The Number of Crossing in a Random Labelled Tree
• Crossing Numbers and Stress of Random Graphs