2026-04-13T11:44:06Zhttps://recercat.cat/oai/request
oai:recercat.cat:2117/3654882026-01-18T06:38:06Zcom_2072_1033col_2072_452950
RECERCAT author Larrauri Borroto, Lázaro Alberto author Müller, Tobias author Noy Serrano, Marcos 2021-08-18 "This is the peer reviewed version of the following article: Larrauri, L.; Müller, T.; Noy, M. Limiting probabilities of first order properties of random sparse graphs and hypergraphs. "Random structures and algorithms", 18 Agost 2021, vol. 60, núm. 3, p. 506-526., which has been published in final form at https://onlinelibrary.wiley.com/doi/10.1002/rsa.21041. This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for Use of Self-Archived Versions. This article may not be enhanced, enriched or otherwise transformed into a derivative work, without express permission from Wiley or by statutory rights under applicable legislation. Copyright notices must not be removed, obscured or modified. The article must be linked to Wiley’s version of record on Wiley Online Library and any embedding, framing or otherwise making available the article or pages thereof by third parties from platforms, services and websites other than Wiley Online Library must be prohibited."Let Gn be the binomial random graph G(n, p = c/n) in the sparse regime, which as is well-known undergoes a phase transition at c = 1. Lynch (Random Structures Algorithms, 1992) showed that for every first order sentence f, the limiting probability that Gn satisfies f as n ¿ 8 exists, and moreover it is an analytic function of c. In this paper we consider the closure Lc in [0, 1] of the set Lc of all limiting probabilities of first order sentences in Gn. We show that there exists a critical value c0 ˜ 0.93 such that Lc = [0, 1] when c = c0, whereas Lc misses at least one subinterval when c < c0. We extend these results to random d-uniform sparse hypergraphs, where the probability of a hyperedge is given by p = c/nd-1 .Peer ReviewedPostprint (author's final draft) Open Access Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs Graph theory Grafs, Teoria de Classificació AMS::05 Combinatorics::05C Graph theory Limiting probabilities of first order properties of random sparse graphs and hypergraphs Article