A subfamily $\mathcal{G}\subseteq \mathcal{F}\subseteq 2^{[n]}$ of sets is a non-induced (weak) copy of a poset P in $\mathcal{F}$ if there exists a bijection $i:P\to \mathcal{G}$ such that $p{\le }_{P}q$ implies $i(p)\subseteq i(q)$. In the case where in addition $p{\le }_{P}q$ holds if and only if $i(p)\subseteq i(q)$, then $\mathcal{G}$ is an induced (strong) copy of P in $\mathcal{F}$. We consider the minimum number $\mathrm{sat}(n,P)$ [resp. ${\mathrm{sat}}^{⁎}(n,P)$] of sets that a family $\mathcal{F}\subseteq 2^{[n]}$ can have without containing a non-induced [induced] copy of P and being maximal with respect to this property, i.e., the addition of any $G\in 2^{[n]}\setminus \mathcal{F}$ creates a non-induced [induced] copy of P. We prove for any finite poset P that $\mathrm{sat}(n,P)\le 2^{|P|-2}$, a bound independent of the size n of the ground set. For induced copies of P, there is a dichotomy: for any poset P either ${\mathrm{sat}}^{⁎}(n,P)\le K_P$ for some constant depending only on P or ${\mathrm{sat}}^{⁎}(n,P)\ge {\log }_{2}n$. We classify several posets according to this dichotomy, and also show better upper and lower bounds on $\mathrm{sat}(n,P)$ and ${\mathrm{sat}}^{⁎}(n,P)$ for specific classes of posets. Our main new tool is a special ordering of the sets based on the colexicographic order. It turns out that if P is given, processing the sets in this order and adding the sets greedily into our family whenever this does not ruin non-induced [induced] P-freeness, we tend to get a small size non-induced [induced] P-saturating family.

The development of kernel-based inhomogeneous random graphs has provided models that are flexible enough to capture many observed characteristics of real networks, and that are also mathematically tractable. We specify a class of inhomogeneous random graph models, called random kernel graphs, that produces sparse graphs with tunable graph properties, and we develop an efficient generation algorithm to sample random instances from this model. As real-world networks are usually large, it is essential that the run-time of generation algorithms scales better than quadratically in the number of vertices n. We show that for many practical kernels our algorithm runs in time at most 𝒪(n(logn)²). As a practical example we show how to generate samples of power-law degree distribution graphs with tunable assortativity.

The frequency of the first digits of numbers drawn from an exponential probability density oscillate around the Benford frequencies. Analysis, simulations and empirical evidence show that datasets must have at least 10,000 entries for these oscillations to emerge from finite-sample noise. Anecdotal evidence from population data is provided.

We analyze the component evolution in inhomogeneous random intersection graphs when the average degree is close to 1. As the average degree increases, the size of the largest component in the random intersection graph goes through a phase transition. We give bounds on the size of the largest components before and after this transition. We also prove that the largest component after the transition is unique. These results are similar to the phase transition in Erd\H{o}s-R\'enyi random graphs; one notable difference is that the jump in the size of the largest component varies in size depending on the parameters of the random intersection graph.

A subfamily $\mathcal{G}\subseteq \mathcal{F}\subseteq 2^{[n]}$ of sets is a non-induced (weak) copy of a poset $P$ in $\mathcal{F}$ if there exists a bijection $i:P\rightarrow \mathcal{G}$ such that $p\le_P q$ implies $i(p)\subseteq i(q)$. In the case where in addition $p\le_P q$ holds if and only if $i(p)\subseteq i(q)$, then $\mathcal{G}$ is an induced (strong) copy of $P$ in $\mathcal{F}$. We consider the minimum number $sat(n,P)$ [resp.\ $sat^*(n,P)$] of sets that a family $\mathcal{F}\subseteq 2^{[n]}$ can have without containing a non-induced [induced] copy of $P$ and being maximal with respect to this property, i.e., the addition of any $G\in 2^{[n]}\setminus \mathcal{F}$ creates a non-induced [induced] copy of $P$. We prove for any finite poset $P$ that $sat(n,P)\le 2^{|P|-2}$, a bound independent of the size $n$ of the ground set. For induced copies of $P$, there is a dichotomy: for any poset $P$ either $sat^*(n,P)\le K_P$ for some constant depending only on $P$ or $sat^*(n,P)\ge \log_2 n$. We classify several posets according to this dichotomy, and also show better upper and lower bounds on $sat(n,P)$ and $sat^*(n,P)$ for specific classes of posets. Our main new tool is a special ordering of the sets based on the colexicographic order. It turns out that if $P$ is given, processing the sets in this order and adding the sets greedily into our family whenever this does not ruin non-induced [induced] $P$-freeness, we tend to get a small size non-induced [induced] $P$-saturating family.