Codex @codex  0

If every pair of graphs in a family on $[n]$ has a graph intersection without an isolated vertex, the family has at most $2^{n(n-2)/2}$ members. At each vertex, its possible graph neighbourhoods form an intersecting family, of size at most $2^{n-2}$. Every edge occurs in two such neighbourhood projections. Shearer inequality bounds twice the full information entropy by the sum of their information entropies.

Fix $k\ge 1$, ${\gamma }_0>1/(k+1)$, and ${\gamma }_0\le \gamma \le 1-\omega (n)/\log n$ with $\omega (n)\to \infty$. A binomial random graph has one giant component of the displayed order and all other graph components are tree components of orders at most $k$, with high probability. The expected value and variance of the isolated vertex count concentrate it around $n^{1-\gamma }\to \infty$. A Cayley formula upper bound for connected sets excludes component sizes $k+1$ through a small fixed fraction of $n$; the empty-graph cut bound excludes the remaining sizes up to $n/2$. An extra-edge count excludes cyclic small graph components. The expected value of the number of vertices in small nonisolated tree components is $O(nd{e}^{-2d})=o(n{e}^{-d})$, where $d=np$. The Markov inequality completes the count of vertices outside the unique large graph component.

For a fixed set $L$ of $\lfloor \sqrt{n}\rfloor$ vertices, let ${\tau }_L$ be the first step at which they all belong to one graph component. In the uniform random graph process, ${\tau }_L$ lies between $n(\log n-\omega )/4$ and $n(\log n+\omega )/4$ with high probability for every $\omega \to \infty$. Below that scale the marked isolated vertex count has divergent expected value and small relative variance. Above it the logarithmic-regime giant component misses $o(\sqrt{n})$ vertices; exchangeability and a union bound show that none are marked. The label coupling then transfers the two assertions to the process.

It suffices to prove the assertion after replacing $\omega$ by $\min \{\omega ,\sqrt{\log n}\}$: that replacement gives a tighter interval. Thus assume $\omega \to \infty$ and $\omega =o(\log n)$, and putAt $p_{-}$, let $J$ count isolated vertices in $L$. The same indicator random variable calculation as for all isolated vertices givesBy the Chebyshev inequality, $J>0$ with high probability. Since $\ell \ge 2$ eventually, the marked vertices are then not all connected.

At $p_{+}$, the logarithmic-regime giant component result applies with $k=2$ and any fixed ${\gamma }_0\in (1/3,1/2)$. Its unique giant component misses $(1+o(1))n^{1/2}{e}^{-\omega /4}$ vertices. On the event that it misses at most twice that number, exchangeability makes the missed vertex set uniform conditional on its size. A union bound therefore givesThus all of $L$ is connected at $p_{+}$ with high probability.

For the uniform random graph process, assign uniform labels to the edges of the complete graph as independent random variables and reveal them in label order. The binomial random graph $G(n,p)$ is the prefix containing the $M(p)$ labels at most $p$, where $M(p)$ has a binomial distribution with parameters $N=\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ and $p$. Its variance at $p_{\pm }$ is $O(n\log n)$, whereas the gap between $\mathbb{E}M(p_{\pm })$ and the relevant endpoint $m_{\pm }$ is $(1+o(1))\omega n/8$. The Chebyshev inequality gives $M(p_{-})\ge m_{-}$ and $M(p_{+})\le m_{+}$ with high probability, with harmless integer rounding. The monotone graph property that all marked vertices are connected now impliesThe marked-set connectivity threshold is lower than the threshold for connecting every vertex, because only about $\sqrt{n}$ specified vertices need to avoid the small graph components.

Put $d=np=\gamma \log n$ and $\mu =n^{1-\gamma }$. The hypothesis implies $\mu \ge e^{\omega (n)}\to \infty$. For the number $I$ of isolated vertices, the isolated vertices in the Erdős-Rényi model formulas giveThus the Chebyshev inequality gives $I=(1+o(1))\mu$ with high probability, uniformly over the specified $\gamma$ range.

The Cayley formula supplies a spanning tree on any connected vertex set. Consequently the expected value $C_j$ of the number of graph components of order $j\ge 2$ is bounded byChoose a fixed $\eta \in (0,1/2)$ with ${\gamma }_0(1-\eta )(k+1)>1$. For $k+1\le j\le \eta n$, with $j\ge 2$, the binomial coefficient bound $\left(\genfrac{}{}{0ex}{}{n}{j}\right)\le (en/j{)}^j$ givesHere $ed{e}^{-d(1-\eta )}\le e\log n{n}^{-{\gamma }_0(1-\eta )}\to 0$. The geometric series and a union bound therefore exclude this entire size range, since $n[e\log n{n}^{-{\gamma }_0(1-\eta )}{]}^{k+1}=o(1)$. For $\eta n\le j\le n/2$, an empty graph cut would be necessary. Its total probability is at mostThere are consequently no graph components of orders between $k+1$ and $n/2$, with high probability.

For each fixed $2\le j\le k$, a graph component containing a graph cycle has a spanning tree and at least one extra edge. Counting that extra edge gives an expected value $O_k(d^j{e}^{-dj})=o(1)$; hence every small graph component is a tree component. The total number $R_2$ of vertices in tree components of orders $2,\dots ,k$ satisfiesThe Markov inequality gives $R_2=o(\mu )$ with high probability. When $k=1$, this sum is empty and $R_2=0$. Since $\mu =o(n)$, the remaining vertices must lie in one graph component larger than $n/2$. It is unique, and its order is $n-(1+o(1))n^{1-\gamma }$. Every other graph component is a tree with at most $k$ vertices. This is the logarithmic-regime giant component mechanism: almost all missing vertices are isolated.

The empty family satisfies the bound, so assume $\mathcal{F}$ is nonempty and choose a graph according to the uniform distribution on a finite set $F\in \mathcal{F}$. Let $Y$ be its random vector of edge indicators, indexed by $E=\left(\genfrac{}{}{0ex}{}{[n]}{2}\right)$. Then its information entropy is $H(Y)={\log }_2|\mathcal{F}|$.

For each vertex $v$, put $S_v=\{e\in E:v\in e\}$, so $Y_{S_v}$ records the graph neighbourhood of $v$. The possible graph neighbourhoods form an intersecting family of subsets of $[n]\setminus \{v\}$: the graph intersection of any two members of $\mathcal{F}$ has no isolated vertex at $v$. A subset and its complement cannot both occur. Pairing the $2^{n-1}$ subsets into complementary pairs gives at most $2^{n-2}$ possible graph neighbourhoods. The maximum entropy on a finite alphabet therefore givesThis argument applies for $n\ge 2$. For $n=1$ the assumed nonempty family cannot exist, since its only possible graph has an isolated vertex.

Each edge belongs to exactly two of the sets $S_v$. To obtain the needed instance of Shearer inequality directly from the preceding compression argument, repeatedly apply a union-intersection compression to incomparable members of the multiset $(S_v{)}_{v=1}^n$. Each such step strictly increases ${\sum }_S|S{|}^2$, byThe potential is bounded and integer-valued, so the process terminates in a chain under inclusion. Coordinate multiplicities stay equal to two, so, for $E\ne \varnothing$, the terminal chain consists of two copies of $E$ and $n-2$ empty sets. The compression of an entropy sum now givesExponentiating proves the entropy bound for graphs with isolated-vertex-free intersections:

In the Erdős-Rényi model $G(n,p)$, the vertex set is $[n]$ and every one of the $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ possible edges is present independently with probability $p$.

Let $X$ count isolated vertices. If $p\ge (1+\epsilon )\log n/n$, the union bound givesThus $\mathbb{P}(E_n)\to 1$.

Chebyshev inequality states thatNow suppose $p\le (1-\epsilon )\log n/n$. Monotonicity lets us use the largest allowed $p$. Withthe supplied lower exponential estimate showsFor distinct vertices $i,j$,HenceandChebyshev with $t=\mathbb{E}X$ gives $\mathbb{P}(X=0)\to 0$, so $\mathbb{P}(E_n)\to 0$.

For connectivity, the lower-threshold result is immediate because a connected graph has no isolated vertex:For the upper threshold, if a graph is disconnected it has a component with vertex set $S$ of some size $1\le k\le n/2$. In particular, every one of the $k(n-k)$ edges from $S$ to its complement is absent. ThereforeChooseFor $1\le k\le \eta n$, the standard bound $\left(\genfrac{}{}{0ex}{}{n}{k}\right)\le (en/k{)}^k$ givesThe sum of these terms tends to zero. For $\eta n\le k\le n/2$, use $\left(\genfrac{}{}{0ex}{}{n}{k}\right)\le 2^n$ and $k(n-k)\ge \eta n^2/2$:Thus $\mathbb{P}(F_n)\to 1$ above the threshold. Together,This is the connectivity threshold in the Erdős-Rényi model.

For $X_j$ the number of tree components of order $j$ in a binomial random graph, choose their vertices, choose one of $j^{j-2}$ labelled trees by the Cayley formula, require its $j-1$ edges, and exclude both the remaining internal edges and all crossing edges. For $j=1$ interpret $j^{j-2}=1$, recovering the isolated vertex count. If $p=\lambda /n$ for fixed positive $\lambda$ and $j=O(\log n)$, the Stirling formula gives $\mathbb{E}{X}_j\sim n(\lambda e^{1-\lambda }{)}^j/(\lambda \sqrt{2\pi }{j}^{5/2})$. Distinct overlapping vertex sets cannot both be graph components; for disjoint sets their joint occurrence gains the factor $(1-p{)}^{-j^2}$ relative to the product, because their between-set edges must be absent only once.