Arnab Sen 2026-11-05
Arnab Sen is a mathematician working in probability theory and mathematical physics. His own biography identifies a Berkeley doctorate completed in 2010, subsequent research at Cambridge, and work at the University of Minnesota. His research includes random graphs, random matrices and disordered models in statistical physics.[ref]
With Nathanaël Berestycki and Christophe Garban, he developed a new state space and topology for the coalescing Brownian flow and proved an probabilistic invariance principle for coalescing random walks under a finite-variance assumption. The theorem connects discrete particle systems with a continuum stochastic flow.[ref]
The physical picture is simple even though convergence of an entire flow is subtle: particles wander separately until meeting, then continue as one. Tracking only the position of one particle misses when two histories merge. A framework for the whole collection must retain that interaction.
Figure 1.
Arnab Sen, portrait from his University of Minnesota homepage
. External portrait linked by the author's own biography.
Barabási-Albert model Created 2026-10-20 Updated 2026-11-05
The Barabási-Albert model constructs a growing random graph by preferential attachment. Starting from a suitable seed, each new vertex brings edges and selects existing endpoints with probability proportional to their current degrees. A convention for sampling distinct endpoints must be specified.[ref]
Older high-degree vertices tend to attract more edges. In the standard large-graph limit, the degree distribution has a tail proportional to , unlike the sharply concentrated degrees of a basic Erdős-Rényi model. Both growth and the attachment rule matter. The model supplies a mechanism for hubs; observing a heavy degree tail alone does not establish that this mechanism generated the data.
Complex network 2026-11-05
A complex network is a graph model of an interacting system whose connectivity has nontrivial structure relevant to its behavior. The phrase does not specify one mathematical graph class: degree heterogeneity, clustered neighborhoods, community organization or changing connectivity may be important depending on the application.
For example, two graphs can have the same numbers of vertices and edges but very different shortest-path graph distances. A six-cycle has average degree two and diameter three; two disjoint triangles also have average degree two but lack paths between the two components. Their equal mean degree conceals a decisive connectivity difference.
Network science therefore uses several measurements and compares them with explicit random graph models. Labels such as small-world network or scale-free network express additional quantitative hypotheses; they should be tested rather than inferred merely because a diagram looks complicated.
Giant component 2026-10-07
A giant component in a sequence of random graphs on vertices has order proportional to . 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.
Largest component of a graph Created 2026-10-07 Updated 2026-10-14
The largest graph component is one with the most vertices. Ties may be broken arbitrarily; 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.
Network science 2026-11-05
Network science studies systems represented by graphs, combining structural measurements, data analysis and models of network formation or dynamics. Vertices represent entities and edges represent a specified relation; directed graphs, weighted graphs and temporal data encode different kinds of interaction.
A transportation network might assign stations to vertices and direct services to edges. Vertex degree counts immediate connections, while shortest-path graph distances measure routes through several stations. These answer different questions: a high-degree station need not minimize all journey times, especially when edge weights represent duration.
Useful models must connect the graph definition to the measured system. A biological network built from physical binding experiments differs from one built from statistical correlation. Comparing an observed statistic with a suitable random graph model helps distinguish a structural pattern from what the vertex and edge counts already imply.
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 for 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 and . 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 criterion, the supplied summaries classify it as a small-world network: clustering is about times the reference value, while path length is only about 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 , , or under the usual definition, not or . 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 , a martingale is an adapted process of integrable random variables satisfying . With no separate filtration specified, take the natural filtration . For deterministic increment bounds , the Hoeffding-Azuma inequality states
To prove it, let . For , convexity on gives
Its conditional expectation is at most . The last inequality follows by integrating for and using evenness. If the bound is immediate. Conditional iteration now yields . The exponential Markov inequality, minimized at , bounds the upper tail by the displayed exponential without the factor two. Apply it to and use the union bound for the two-sided assertion. When every , the deviation probability is zero.
For the chromatic number of a binomial random graph, put , , and . We prove matching bounds; treating suffices. A colour class is an independent set, so . For with fixed , the expected value of the number of independent -sets is
The first moment method gives with probability tending to one. Choosing sufficiently small then gives for all sufficiently large on that event.
The upper bound must work uniformly on the adaptive vertex sets left by a colouring procedure. Set
For a specified -set , its complement graph has distribution . Let count its -cliques, count distinct ordered pairs sharing an edge, and be the maximum edge-disjoint clique packing. The allowed clique-count estimates at this value of give
The overlap quantity, if the diagonal is included, has the exact expression after division by ; 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 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 by the Cauchy-Schwarz inequality. Thus, with a zero ratio when ,
The middle inequality follows from . Toggling one ambient edge changes by at most one: at most one member of a packing uses it. Reveal the independent edges successively and form the edge-exposure martingale for . 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 gives
This is clique-packing amplification of moment bounds. A union bound over all -sets is now strong enough:
since . Thus every such set contains an independent set of size . Repeatedly remove and colour one whenever at least vertices remain; then colour each of the fewer than remaining vertices separately. This greedy colouring by removing independent sets uses at most
Choose so . Combining the two high-probability events proves
The 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 , take , and let count its -cliques. Put and let 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 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 by the Cauchy-Schwarz inequality. Interpret the ratio as zero when . A second application of the Cauchy-Schwarz inequality, now to expectations, gives
Counting ordered pairs of -sets with common vertices, including identical sets when , yields
The shared edges account for the factor . We claim
Here are the estimates, including the large overlaps. For , the probability that a random -set contains any specified elements is at most . Summing over their choices inside the first -set gives
The logarithm of is a convex function, a quadratic in , so the maximum on this interval is at an endpoint. We have . As , the other endpoint satisfies
and is smaller than for sufficiently large . Summing at most terms gives .
For the other half of the overlaps, write , where . The exact identity and an upper bound are
The quantity in parentheses is , which tends to zero. The geometric series is thus at most for sufficiently large . This proves the claim. In fact and , so eventually
Now expose the independent edge indicators one at a time. The edge-exposure martingale starts at and ends at . Deleting one edge destroys at most one member of any edge-disjoint clique packing. Hence changing one indicator changes by at most one; coupling the remaining indicators shows .
Precisely, the Azuma-Hoeffding inequality says that if is a martingale and almost surely for deterministic , then, for ,
If all , the martingale is constant. Applying the lower-tail inequality with and gives
for sufficiently large . This is the only martingale concentration inequality needed.
Return to the original binomial random graph and set . For each fixed -element vertex set , the complement graph of has distribution . The union bound therefore gives
since . Thus with high probability every vertex set of size at least contains an independent set of size
Apply greedy colouring by removing independent sets: remove such an independent set, give it a fresh colour, and repeat while at least vertices remain. Give each of the fewer than final vertices its own colour. This uses at most
colours, since . Together with the lower bound, this gives the chromatic number of the half-density binomial random graph:
Probabilistic combinatorics Created 2026-09-24 Updated 2026-11-05
Probabilistic combinatorics uses probability to study discrete structures and to prove that particular structures exist. One chooses a random object and shows that the probability of the desired property is positive, without necessarily constructing an explicit example.
For example, color the vertices of a finite graph independently with two colors. Each edge crosses the resulting cut with probability , so the expected cut size is half the number of edges. Some outcome therefore has at least that many crossing edges. Random graphs, concentration inequalities, and the Lovász local lemma extend this idea to more demanding existence questions.
Small-world network 2026-10-20
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.