Near-critical bipartite configuration models and their associated intersection graphs

2024/10/15 by David Clancy, Clancy, David
Computer Science · #05C80 #FOS: Mathematics #Graph Theory and Algorithms #Interconnection Networks and Systems #Parallel Computing and Optimization Techniques #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.2410.11975

openalex publication_date 2024/10/15 · openalex created_date 2024/10/20 · openalex updated_date 2026/07/28

Abstract

Recently, van der Hofstad, Komjáthy, and Vadon (2022) identified the critical point for the emergence of a giant connected component for the bipartite configuration model (BCM) and used this to analyze its associated random intersection graph (RIG) (2021). We extend some of this analysis to understand the graph at, and near, criticality. In particular, we show that under certain moment conditions on the empirical degree distributions, the number of vertices in each connected component listed in decreasing order of their size converges, after appropriate re-normalization, to the excursion lengths of a certain thinned Lévy process. Our approach allows us to obtain the asymptotic triangle counts in the RIG built from the BCM. Our limits agree with the limits recently identified by Wang (2023) for the RIG built from the bipartite Erdős-Rényi random graph.

Related

• Component sizes of rank-2 multiplicative random graphs
• Large random intersection graphs inside the critical window and triangle counts
• Critical window for connectivity in the Configuration Model
• Component behaviour and excess of random bipartite graphs near the critical point
• Small maximal clusters are very unlikely in critical random graphs