Abstract

We study the validity of the first-order zero-one law for the binomial $k$-partite random graph in two settings: dense (the probability $p$ of appearance of an edge is a constant) and sparse ($p=n^{-\alpha }$, where $n$ is the cardinality of each part of the graph). On the way, we prove that, for every rational $\rho \ge 1$, there exists a bipartite strictly balanced graph with density $\rho$.

Keywords

Mathematical Subject Classification

Milestones

Authors