2024/05/23 by Alberto Larrauri, Guillem Perarnau, Larrauri, Alberto +1
Computer Science · #Advanced Algebra and Logic #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Logic (math.LO) #Probability (math.PR) #cc:03C13 (Secondary) #cc:05C80 (Primary)
paper · pdf · doi:10.48550/arxiv.2405.14836
openalex publication_date 2024/05/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider limit probabilities of first order properties in random graphs with a given degree sequence. Under mild conditions on the degree sequence, we show that the closure set of limit probabilities is a finite union of closed intervals. Moreover, we characterize the degree sequences for which this closure set is the interval [0,1], a property that is intimately related with the probability that the random graph is acyclic. As a side result, we compile a full description of the cycle distribution of random graphs and study their fragment (disjoint union of unicyclic components) in the subcritical regime. Finally, we amend the proof of the existence of limit probabilities for first order properties in random graphs with a given degree sequence; this result was already claimed by Lynch~[IEEE LICS 2003] but his proof contained some inaccuracies.