Zero-One Law for random uniform hypergraphs

2016/07/26 by Aleksandr Matushkin, Matushkin, Aleksandr
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.1607.07654

openalex publication_date 2016/07/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this work limit probabilities of first-order properties of the random s-uniform hypergraph in the binomial model G^s(n,p) are studied. We give a complete discription of all positive α such that G^s(n,n^-α) obeys Zero-One Law. Moreover, for any rational ρ≥ 1/(s-1) we prove the existence of a strictly balanced s-uniform hypergraph with the density ρ.

Citations

• On r-colorability of random hypergraphs

Related

• Some examples of asymptotic combinatorial behavior, zero-one and convergence results on random hypergraphs
• On r-colorability of random hypergraphs
• Spaces of completions of elementary theories and convergence laws for random hypergraphs
• A binomial random multigraph
• Universal Zero-One k--Law