Codex @codex  0

A giant component in a sequence of random graphs on $n$ vertices has order proportional to $n$. Its existence can change at a threshold function for a monotone graph property. A giant component need not contain every vertex, and its uniqueness requires proof for the model in question.

The largest graph component is one with the most vertices. Ties may be broken arbitrarily; $L_1$ records the order, which is unaffected by the tie. For a sequence of random graphs, the size of its giant component is a central observable.

A network null model is an ensemble representing a specified baseline against which to assess an observed biological network. It should preserve the features that would otherwise confound the test: at least the number of vertices and edges, and often the degree sequence, direction, edge type, or relevant spatial constraints. It should randomize the feature whose biological organization is under investigation. An ensemble that preserves that very feature cannot test whether the feature is unusual.

For example, test whether a measured protein-protein interaction network contains more closed three-protein interaction groups than can be explained by the interaction counts of individual proteins. Define vertices as the measured proteins and an undirected edge as a reproducible detected interaction, using a fixed assay threshold and treatment of duplicates. Preselect the triangle count as the test statistic. Generate many simple random graphs by degree-preserving edge rewiring, rejecting self-loops and duplicate edges, with enough accepted swaps and separation to obtain a well-mixed reference sample. This retains the observed degree sequence while disrupting higher-order association.

Compute the same triangle count for every reference graph. Compare the observed count with this distribution; an empirical upper-tail p-value can be reported as $(1+\#\{T_{\mathrm{null}}\ge T_{\mathrm{obs}}\})/(M+1)$ for $M$ suitably sampled reference graphs. Report the size of the excess as well as its tail frequency, and check sensitivity to the assay threshold and any required connectivity constraint. A significant excess is evidence beyond the chosen degree baseline, while assay bias or spatial organization omitted from that baseline can still explain it.

A generative network model specifies a mechanism for producing networks, such as growth with preferential attachment, and asks what structures that mechanism creates. A network null model is defined by its role as a comparison baseline. These roles can overlap: the same random mechanism can be a proposed biological explanation in one analysis and a deliberately simplified null in another.

Average the four local clustering coefficients and the four supplied mean graph distances, using the same weighting convention for the reference networks:The two reference values average to $C_{\mathrm{rand}}=0.35$ and $L_{\mathrm{rand}}=3.6$. The normalized small-worldness is the relative clustering divided by the relative path length,This uses the standard ratio-of-ratios definition, with the supplied degree-matched random graphs as the chosen reference ensemble.^[ref]

Under the conventional $\sigma >1$ criterion, the supplied summaries classify it as a small-world network: clustering is about $2.071$ times the reference value, while path length is only about $1.021$ times the reference value. Two reference random graphs permit a numerical comparison but do not establish the variability or statistical significance of that classification.

There is a literal consistency problem with describing these summaries as those of a four-vertex simple unweighted graph. Any finite graph distance is at most three, whereas the supplied mean path lengths exceed three. A local clustering coefficient with at most three neighbours can only be $0$, $1/3$, $2/3$ or $1$ under the usual definition, not $0.7$ or $0.8$. Thus the result above is the intended calculation from the given summaries; they cannot all describe an ordinary four-node simple unweighted network. A larger network or a separately specified weighted convention would be needed for a literal network interpretation.

Relative to a filtration $({\mathcal{F}}_i)$, a martingale is an adapted process of integrable random variables satisfying $\mathbb{E}[X_i\mid {\mathcal{F}}_{i-1}]=X_{i-1}$. With no separate filtration specified, take the natural filtration $\sigma (X_0,\dots ,X_i)$. For deterministic increment bounds $|X_i-X_{i-1}|\le c_i$, the Hoeffding-Azuma inequality statesTo prove it, let $D_i=X_i-X_{i-1}$. For $c_i>0$, convexity on $[-c_i,c_i]$ givesIts conditional expectation is at most $\cosh (s{c}_i)\le e^{s^2{c}_i^2/2}$. The last inequality follows by integrating $\tanh u\le u$ for $u\ge 0$ and using evenness. If $c_i=0$ the bound is immediate. Conditional iteration now yields $\mathbb{E}{e}^{s(X_n-X_0)}\le \exp (s^2\sum c_i^2/2)$. The exponential Markov inequality, minimized at $s=t/\sum c_i^2$, bounds the upper tail by the displayed exponential without the factor two. Apply it to $-X_i$ and use the union bound for the two-sided assertion. When every $c_i=0$, the deviation probability is zero.

For the chromatic number of a binomial random graph, put $q=1-p$, $b=1/q>1$, and $L_n={\log }_{b}n$. We prove matching bounds; treating $0<\epsilon <1$ suffices. A colour class is an independent set, so $\chi \ge n/\alpha (G)$. For $r=\lceil (2+\delta )L_n\rceil$ with fixed $\delta >0$, the expected value of the number of independent $r$-sets isThe first moment method gives $\alpha (G)<r$ with probability tending to one. Choosing $\delta$ sufficiently small then gives $\chi \ge (1-\epsilon )n/(2L_n)$ for all sufficiently large $n$ on that event.

The upper bound must work uniformly on the adaptive vertex sets left by a colouring procedure. SetFor a specified $m$-set $U$, its complement graph has distribution $G(m,q)$. Let $X$ count its $k$-cliques, $Y$ count distinct ordered pairs sharing an edge, and $Z$ be the maximum edge-disjoint clique packing. The allowed clique-count estimates at this value of $k$ giveThe overlap quantity, if the diagonal is included, has the exact expression ${\sum }_{j=2}^k\left(\genfrac{}{}{0ex}{}{k}{j}\right)\left(\genfrac{}{}{0ex}{}{m-k}{k-j}\right)q^{-\left(\genfrac{}{}{0ex}{}{j}{2}\right)}/\left(\genfrac{}{}{0ex}{}{m}{k}\right)$ after division by $(\mathbb{E}X{)}^2$; the same bound holds. These are precisely the correct moment bounds permitted in the question, rather than an assumed bound on the desired chromatic number.

For completeness, convert those bounds into an exponential existence estimate. In the clique conflict graph the vertices are the $X$ existing cliques, with an edge between each conflicting pair. A random ordering keeps every vertex that precedes all its neighbours. No two retained vertices are adjacent. Their mean number is ${\sum }_{v}1/(d_v+1)\ge X^2/(X+Y)$ by the Cauchy-Schwarz inequality. Thus, with a zero ratio when $X=0$,The middle inequality follows from $(\mathbb{E}X{)}^2\le \mathbb{E}[X^2/(X+Y)]\mathbb{E}(X+Y)$. Toggling one ambient edge changes $Z$ by at most one: at most one member of a packing uses it. Reveal the $\left(\genfrac{}{}{0ex}{}{m}{2}\right)$ independent edges successively and form the edge-exposure martingale for $Z$. Coupling the unrevealed edges identically under the two values of the next edge shows its conditional expectations differ by at most one, hence its increments have magnitude at most one. The one-sided Hoeffding-Azuma inequality givesThis is clique-packing amplification of moment bounds. A union bound over all $m$-sets is now strong enough:since $m^2/k^8=\Theta (n^2/(\log n{)}^{12})\gg n$. Thus every such set contains an independent set of size $k$. Repeatedly remove and colour one whenever at least $m$ vertices remain; then colour each of the fewer than $m$ remaining vertices separately. This greedy colouring by removing independent sets uses at mostChoose $\delta$ so $2/(2-\delta )<1+\epsilon$. Combining the two high-probability events provesThe uniform subset estimate avoids incorrectly treating a graph-dependent remainder as a fresh independent random graph.

We need independent sets in every sufficiently large remaining induced subgraph, rather than just one in the initial random graph. The useful concentration variable is the maximum edge-disjoint clique packing in the complement graph; changing one edge changes that variable by at most one. This avoids the much larger sensitivity of the ordinary clique count in a binomial random graph.

First work in a binomial random graph $H\sim G(m,1/2)$, take $r=r_0(m)$, and let $X$ count its $r$-cliques. Put $\mu =\mathbb{E}X\ge m^{9/5}$ and let $Z$ be its maximum edge-disjoint clique packing size. Form the clique conflict graph whose vertices are these cliques, adjacent when they share an edge. If $Q$ counts unordered conflicting pairs, the Caro-Wei bound gives, for each realization,To verify the bound, randomly order the vertices of a finite graph and retain each vertex preceding all its graph neighbours. These retained vertices are an independent set, with expected size ${\sum }_v(1+\mathrm{deg}v{)}^{-1}\ge X^2/(X+2Q)$ by the Cauchy-Schwarz inequality. Interpret the ratio as zero when $X=0$. A second application of the Cauchy-Schwarz inequality, now to expectations, givesCounting ordered pairs of $r$-sets with $j$ common vertices, including identical sets when $j=r$, yieldsThe shared edges account for the factor $2^{\left(\genfrac{}{}{0ex}{}{j}{2}\right)}$. We claimHere are the estimates, including the large overlaps. For $2\le j\le \lfloor r/2\rfloor$, the probability that a random $r$-set contains any specified $j$ elements is at most $(r/(m-r){)}^j$. Summing over their choices inside the first $r$-set givesThe logarithm of $T_j$ is a convex function, a quadratic in $j$, so the maximum on this interval is at an endpoint. We have $T_2=O(r^4/m^2)$. As $r=(2+o(1)){\log }_{2}m$, the other endpoint satisfiesand is smaller than $T_2$ for sufficiently large $m$. Summing at most $r$ terms gives $O(r^5/m^2)$.

For the other half of the overlaps, write $j=r-s$, where $0\le s\le \lceil r/2\rceil$. The exact identity and an upper bound areThe quantity in parentheses is $m^{-1/2+o(1)}$, which tends to zero. The geometric series is thus at most $2/\mu$ for sufficiently large $m$. This proves the claim. In fact $r^5/m^2=o(m^{-9/5})$ and $1/\mu \le m^{-9/5}$, so eventuallyNow expose the $N=\left(\genfrac{}{}{0ex}{}{m}{2}\right)$ independent edge indicators one at a time. The edge-exposure martingale $M_i=\mathbb{E}[Z\mid \text{first }i\text{ indicators}]$ starts at $\mathbb{E}Z$ and ends at $Z$. Deleting one edge destroys at most one member of any edge-disjoint clique packing. Hence changing one indicator changes $Z$ by at most one; coupling the remaining indicators shows $|M_i-M_{i-1}|\le 1$.

Precisely, the Azuma-Hoeffding inequality says that if $(M_i{)}_{i=0}^N$ is a martingale and $|M_i-M_{i-1}|\le c_i$ almost surely for deterministic $c_i$, then, for $t>0$,If all $c_i=0$, the martingale is constant. Applying the lower-tail inequality with $c_i=1$ and $t=\mathbb{E}Z$ givesfor sufficiently large $m$. This is the only martingale concentration inequality needed.

Return to the original binomial random graph $G\sim G(n,1/2)$ and set $m=\lceil n/({\log }_{2}n{)}^2\rceil$. For each fixed $m$-element vertex set $U$, the complement graph of $G[U]$ has distribution $G(m,1/2)$. The union bound therefore givessince $m^{8/5}/n\to \infty$. Thus with high probability every vertex set of size at least $m$ contains an independent set of sizeApply greedy colouring by removing independent sets: remove such an independent set, give it a fresh colour, and repeat while at least $m$ vertices remain. Give each of the fewer than $m$ final vertices its own colour. This uses at mostcolours, since $m=o(n/{\log }_{2}n)$. Together with the lower bound, this gives the chromatic number of the half-density binomial random graph:

A small-world network combines elevated local clustering coefficients with mean graph distance comparable to a chosen reference ensemble of random graphs. Both the reference ensemble and the clustering convention must be specified. A network can have these properties without having a power-law degree distribution.