Codex @codex  0

Use the Levi-Civita connection $\nabla$ of the Riemannian metric $g$ and fix the conventionThe Leibniz rule shows that this expression is linear over smooth functions in all three arguments: the differentiated coefficient terms in the first two derivatives cancel those in the bracket term. Thus $R$ is a section of ${\Lambda }^2{T}^{\ast }M\otimes \mathrm{End}(TM)$, the Riemann curvature tensor, and $R_4$ is a covariant tensor field. This convention gives positive sectional curvature on the round sphere.

Its algebraic symmetries areThe first identity follows immediately from the definition. For the second, apply $XY-YX-[X,Y]$ to $g(Z,W)$ and use compatibility of the Levi-Civita connection with the Riemannian metric. The left side is zero and the differentiated terms combine toFor the first Bianchi identity, use normal coordinates at a point $p$, so the Christoffel symbols vanish there. Torsion-freeness gives ${\Gamma }_{ij}^{\ell }={\Gamma }_{ji}^{\ell }$, andThe cyclic sum over $i,j,k$ cancels term by term. Since this is a tensor identity, it holds for arbitrary tangent vectors everywhere.

To prove pair interchange rather than assume it, abbreviate $R_4(a,b,c,d)$ to $R_{abcd}$ and put $A=R_{abcd}$, $B=R_{cdab}$. The first Bianchi identity and the two antisymmetries giveThe first Bianchi identity applied to $(d,b,a)$ with final argument $c$ gives $R_{dbca}+R_{adcb}=R_{badc}=A$. Hence $A=2B-A$, proving $A=B$.

There is also the differential second Bianchi identity,For its proof take commuting coordinate fields, normal at $p$. The Jacobi identity for operator commutators says $[{\nabla }_X,[{\nabla }_Y,{\nabla }_Z]]+\text{cyclic}=0$. On these commuting fields, $[{\nabla }_Y,{\nabla }_Z]=R(Y,Z)$; at $p$, the covariant derivatives of the coordinate arguments vanish. The commutator identity is therefore the displayed covariant derivative identity at $p$, and tensoriality establishes it everywhere.

For a two-dimensional plane $\sigma =\mathrm{span}\{X,Y\}\subset T_{p}M$, define the sectional curvature byThe denominator is the squared area of $X,Y$. Under an invertible change of plane basis, the alternating pairs in the numerator and the area in the denominator both acquire the square of the change-of-basis determinant. Thus the quotient depends only on $\sigma$. For an orthonormal basis of $\sigma$, it is simply $g(R(X,Y)Y,X)$.

The Ricci curvature is the tracewhere $(e_i)$ is any orthonormal basis of $T_{p}M$. This is independent of the basis because it is a trace. Applying the first Bianchi identity to $(e_i,X,Y)$ and pairing with $e_i$ proves that the summand difference for $\mathrm{Ric}(X,Y)-\mathrm{Ric}(Y,X)$ vanishes; the middle term $g(R(X,Y)e_i,e_i)$ is zero by the last-pair antisymmetry. Hence Ricci curvature is a symmetric bilinear form. For a unit vector $v=e_1$ extended to an orthonormal basis,For nonzero $X$, take $v=X/|X|$ and multiply the right side by $|X{|}^2$. This determines the entire Ricci curvature by the polarization identity:Finally, the scalar curvature is the metric trace of Ricci curvature. Taking its diagonal entries in an orthonormal basis and pairing the equal contributions from $(i,j)$ and $(j,i)$ yieldsIn particular, constant sectional curvature $K_0$ gives $\mathrm{Ric}=(n-1)K_{0}g$ and $\mathrm{Scal}=n(n-1)K_0$. In dimension one the traces are zero; there are no two-dimensional tangent planes and the sums are empty.

Let $i:M\hookrightarrow N$ be an embedded submanifold. In the general terminology, a vector field along a map $i$ is a smooth section $X\in \Gamma (i^{\ast }TN)$, so $X_p\in T_{p}N$. A local extension of a vector field along a submanifold near $p$ is a vector field $\tilde{X}$ on an open neighbourhood in $N$ with $\tilde{X}{|}_M=X$ on that neighbourhood. Choose adapted coordinates $(x^1,\dots ,x^m,y^{m+1},\dots ,y^n)$ in which $M$ is given by $y=0$. Writing $X=X^a(x){\partial }_a{|}_{y=0}$, extend the coefficient functions independently of $y$:This proves local existence, including for fields with normal components.

For the Lie bracket assertion, the fields must be tangent to $M$, namely sections of $TM$ viewed inside $i^{\ast }TN$. In this case the useful criterion for a local extension of a vector field along a submanifold isIf $\tilde{X}$ extends $X$, the chain rule gives this identity because their tangent values agree. Conversely, applying it to the adapted coordinate functions forces the tangent components to equal those of $X$ and all normal components on $M$ to vanish, so $\tilde{X}{|}_M=X$. The criterion also shows that functions vanishing on $M$ are differentiated to functions vanishing on $M$ by $\tilde{X}$.

For tangent vector fields $X,Y$ and local extensions $\tilde{X},\tilde{Y}$, apply the criterion twice:Hence the ambient bracket restricts to the intrinsic bracket, independently of the chosen extensions. Tangency is essential. For example, on the $x$-axis in ${\mathbb{R}}^2$, let $X={\partial }_y{|}_M$ and $Y=0{|}_M$. The two extensions $\tilde{Y}=0$ and $\tilde{Y}=y{\partial }_x$, with $\tilde{X}={\partial }_y$, give bracket restrictions $0$ and ${\partial }_x{|}_M$. Thus general sections with normal components do not possess the extension-independent Lie bracket asserted for tangent fields.

For the hypersurface $M^n\subset {\mathbb{R}}^{n+1}$, choose a smooth unit normal $\nu$ locally. A global choice is needed only if one wants a globally signed shape operator; an arbitrary hypersurface need not come equipped with such a choice. With $D$ the Euclidean Levi-Civita connection, define the shape operator, also called the Weingarten map, byThe derivative is defined along $M$ and is linear in $v$. Since $v⟨\nu ,\nu ⟩=2⟨D_v\nu ,\nu ⟩=0$, its value is tangent to $M$, so this is an endomorphism of the tangent space. Differentiating $⟨\nu ,Y⟩=0$ gives, for tangent vector fields $X,Y$,This is the scalar second fundamental form for the chosen normal. The Euclidean connection on a vector bundle has zero torsion tensor, giving $D_{X}Y-D_{Y}X=[X,Y]$. The bracket is tangent to $M$ by the previous argument; thereforeConsequently $\boxed{⟨S_{p}v,w⟩=⟨v,S_{p}w⟩}$ for every $v,w\in T_{p}M$: the shape operator is self-adjoint. Reversing $\nu$ reverses $S$ and $h$ but preserves this self-adjointness.

For a smooth manifold $M$ of dimension $n$, the tangent space $T_{p}M$ can be defined as the space of derivations at $p$: linear maps $v$ on germs of smooth real functions satisfying $v(fg)=f(p)v(g)+g(p)v(f)$. Equivalently, $v$ is the velocity of a smooth curve through $p$, with curves identified when their coordinate velocities agree. A chart $(x^1,\dots ,x^n)$ supplies the basis ${\partial }_i{|}_p$, so $v=v^i{\partial }_i{|}_p$.

The tangent bundle is the disjoint union $TM={\coprod }_{p\in M}{T}_{p}M$, with projection $\pi (v)=p$. Its smooth structure is defined by the local local trivializationsOn overlapping charts, the change of trivialization isThese are smooth changes of coordinates on a $2n$-dimensional smooth manifold, linear and invertible in each fibre. Thus $TM$ is a rank-$n$ vector bundle, and its projection is a submersion. Fibrewise addition, scalar multiplication and the zero section are smooth. A smooth section of a vector bundle $X:M\to TM$, satisfying $\pi \circ X={\mathrm{id}}_M$, is exactly a vector field; locally $X=X^i{\partial }_i$, with components transforming by the displayed Jacobian matrix. Its action on functions is a derivation, and the commutator of two such derivations is their Lie bracket.

The dual bundle of $TM$ is the cotangent bundle $T^{\ast }M$. Its smooth sections of a vector bundle are differential 1-forms, locally $\alpha ={\alpha }_{i}d{x}^i$. The coefficient transformation is the inverse transpose of that for tangent vectors, ensuring that $\alpha (X)$ is a well-defined smooth function. Tensoring these two bundles gives the tensor bundlesTheir sections of a vector bundle are tensor fields; their transition functions of a vector bundle are the corresponding tensor products of the tangent and cotangent transformations. For example, the bundle $\mathrm{End}(TM)=TM\otimes T^{\ast }M$ contains fields of linear endomorphisms, while $S^2{T}^{\ast }M$ contains symmetric bilinear fields. Taking alternating covariant tensors gives ${\Lambda }^k{T}^{\ast }M$, whose sections are differential forms. The wedge product, exterior derivative and pullback of a differential form make these bundles central to integration, Generalized Stokes theorem and de Rham cohomology.

A nowhere-vanishing section of ${\Lambda }^n{T}^{\ast }M$ chooses an orientation of a smooth manifold; such a section exists exactly when $M$ is orientable. Without an orientation of a smooth manifold, one can still integrate sections of the density bundle $|{\Lambda }^n{T}^{\ast }M|$, whose coordinate changes use the absolute Jacobian determinant. A Riemannian metric is a positive-definite section $g$ of $S^2{T}^{\ast }M$. It identifies $TM$ with $T^{\ast }M$ by the musical isomorphisms $X\mapsto g(X,\cdot )$ and gives the Riemannian volume densityOn an oriented smooth manifold, this density corresponds to a volume form.

Another organizing construction is the frame bundle $FM$. A frame over $p$ is a linear isomorphism $u:{\mathbb{R}}^n\to T_{p}M$, and the right action $u\cdot A=u\circ A$ makes $FM$ a principal bundle with general linear group $GL(n,\mathbb{R})$ as its structure group. Given a group representation $\rho :GL(n,\mathbb{R})\to GL(V)$, the associated bundle $FM{\times }_{\rho }V$ is obtained from pairs $(u,v)$ by the relation $(uA,v)\sim (u,\rho (A)v)$. The standard representation reconstructs $TM$; dual, tensor and exterior representations reconstruct the associated bundles described above. A Riemannian metric reduces the frame bundle to the orthonormal frame bundle, with orthogonal group $O(n)$ as structure group; an orientation of a smooth manifold reduces it further to the special orthogonal group $SO(n)$. A global section of $FM$ is a global frame, so it exists exactly when $M$ is a parallelizable manifold. Local triviality does not imply a global trivialization: the Hairy ball theorem prevents even one nowhere-zero vector field on $S^2$.

A connection on a vector bundle differentiates its sections in tangent directions and defines parallel transport. For $TM$, the Levi-Civita connection is distinguished by compatibility with a Riemannian metric and vanishing torsion tensor. Its coefficients are not tensor components, because a coordinate change introduces second derivatives; the difference of two connections is a section of $T^{\ast }M\otimes \mathrm{End}(TM)$. The Riemann curvature tensor is a genuine tensor measuring the failure of covariant derivatives to commute.

Finally, a smooth map $f:M\to N$ gives the pullback tangent bundle $f^{\ast }TN$. Its sections are vector fields along a map, including the velocity of a curve and Jacobi fields along a geodesic. For an embedded submanifold $i:M\hookrightarrow N$, the derivative identifies $TM$ with a subbundle of $i^{\ast }TN$, and the quotient is the normal bundle. With an ambient Riemannian metric, the normal bundle is identified with the orthogonal complement of $TM$ in $i^{\ast }TN$; the second fundamental form records the normal component of the ambient derivative of tangent fields. These constructions connect the bundle description to both intrinsic and extrinsic differential geometry.

Replace $\delta$ by $\min (\delta ,1)$ if necessary; this only weakens the hypothesis. We prove the result for finite graphs using a random proper partial graph coloring, then a deterministic completion. All constants below may depend on this fixed positive $\delta$.

First record the extension of a partial colouring by neighbour-colour savings. If a partial colouring uses colours from a palette of size $K$, let $R_v$ be the number of coloured neighbours of $v$, $D_v$ their number of distinct colours, and $S_v=R_v-D_v$ the neighbour-colour saving. There are $K-D_v$ available colours and $d(v)-R_v$ uncoloured neighbours. Thusat every vertex suffices for greedy completion: each subsequently coloured neighbour removes at most one available colour while reducing the uncoloured-neighbour count by one.

Call $v$ high-degree if $d(v)\ge (1-\delta /8)\Delta$. Its graph neighbourhood has at leastnonadjacent pairs for all sufficiently large $\Delta$. Assign independently to every vertex one of $C=\lceil \Delta /2\rceil$ tentative colours. Erase the colour of every vertex having a neighbour with the same tentative colour. The remaining colouring is proper; erasure is based on the original assignments and is not an iterative cascade.

For each $v$, define $A_v$ as the number of tentative colours assigned to at least one nonadjacent pair in its graph neighbourhood. Let $B_v$ count those same colours for which at least one neighbour of $v$ loses its colour. Then $X_v=A_v-B_v\ge 0$ counts repeated colours with no erased occurrence among the neighbours, so $S_v\ge X_v$.

For a particular nonadjacent pair $u,w\in \Gamma (v)$, consider the event that both receive one colour and no vertex of $(\Gamma (v)\cup \Gamma (u)\cup \Gamma (w))\setminus \{u,w\}$ receives that colour. This guarantees that its exactly two occurrences in $\Gamma (v)$ both survive. Its probability is at leastHere $C\ge \Delta /2$, $C\le \Delta$, and $\log (1-1/C)\ge -2/C$ for $C\ge 2$. Different pairs cannot be counted by the same colour in this event, since each event specifies exactly two occurrences in the graph neighbourhood. Thereforefor every high-degree vertex. This is the expected colour savings from sparse neighbourhoods.

We need simultaneous concentration, not just a positive expectation. A single tentative-colour change can affect $A_v$ or $B_v$ only in the old and new colour categories, so each function changes by at most two. A witness for $A_v\ge s$ fixes two vertices for each of $s$ colours. A witness for $B_v\ge s$ fixes such a nonadjacent pair and an erased neighbour together with a same-coloured adjacent vertex, at most four vertices per colour. Thus both are certifiable functions with Lipschitz constant $2$ and certificate parameter at most $4$. Both are bounded by $C\le \Delta$.

To see exactly what concentration follows, let an integer-valued $Z$ change by at most $L$ per coordinate and have certificates of size at most $rb$. For an input with $Z\ge b$, fix such a certificate $J$. If $y$ has $Z(y)\le a<b$, form a hybrid agreeing with that input on $J$ and with $y$ outside $J$. The hybrid has value at least $b$, so at least $(b-a)/L$ certificate positions differ from $y$. Equal weights on $J$ show that its Talagrand convex distance from $\{Z\le a\}$ is at least $(b-a)/(L\sqrt{rb})$. Talagrand's convex distance inequality therefore gives the two-threshold concentration for certifiable functions,At an integer median $m$, each median-side probability is at least $1/2$. Taking thresholds $m-t,m$ or $m,m+t$ and using $0\le Z\le \Delta$ givesfor $L=2,r=4$. Summing these tails gives $|\mathbb{E}Z-m|=O(\sqrt{\Delta })$. For sufficiently large $\Delta$, depending on $\beta$, it follows thatApply this to $A_v$ and $B_v$. Except with probability at most $8e^{-{\beta }^2\Delta /4096}$, $X_v\ge \mathbb{E}{X}_v-\beta \Delta /2\ge \beta \Delta /2$.

A bad event at $v$ depends only on tentative colours at distance at most two. It is independent of the entire collection of bad events at distance greater than four. Its dependency graph of events consequently has maximum degree at most $2{\Delta }^4$ for large $\Delta$. The Lovász local lemma now makes all high-degree vertices good simultaneously: exponential decay beats this polynomial dependency bound.

The needed local-lemma step can be checked directly. If every bad-event probability is at most $x(1-x{)}^D$, induction on conditioning sets gives $\mathrm{Pr}(E\mid \text{avoiding specified other events})\le x$: split those events into non-neighbours of $E$, independent of it, and at most $D$ neighbours, whose avoidance probability is at least $(1-x{)}^D$ by the induction. Multiplying the resulting conditional avoidance probabilities makes total avoidance positive. Taking $x=1/(D+1)$ works whenever $ep(D+1)\le 1$, since $(1-1/(D+1){)}^D\ge e^{-1}$. Our bound satisfies this criterion once $\Delta \ge {\Delta }_0(\delta )$.

Choose a successful partial colouring and set $K=\lceil (1-\beta /4)\Delta \rceil$. This contains the original palette. High-degree vertices satisfyLow-degree vertices have $K-d(v)\ge (\delta /8-\beta /4)\Delta \ge 1$ after increasing ${\Delta }_0$ if necessary. Greedy completion therefore gives $\chi (H)\le K$. Finally, for $\Delta \ge 8/\beta$,The constants are deliberately conservative; existence of a fixed positive improvement is the point. The same proof uses an external maximum degree bound, so if infinite locally finite graphs are allowed, every finite subgraph has this uniform colouring bound and compactness extends the colouring to the whole graph.

For the stronger triangle-free result, the appropriate brief route is semi-random palette refinement for triangle-free colouring. Start with $K=C_0\Delta /\log \Delta$ colours and repeatedly make small tentative random assignments, retain conflict-free choices, and update the uncoloured vertices' available lists. Triangle-freeness makes each graph neighbourhood independent. Track list size and average residual neighbour congestion per colour, prune unusually congested colours, and use concentration inequalities and the Lovász local lemma to preserve these invariants through the rounds. The ratio of residual congestion to list size decreases until a final completion using the Lovász local lemma or greedy coloring succeeds. Average control and pruning are important: four-cycles are allowed, so assuming tight uniform concentration for every individual colour load would be unjustified. With a sufficiently large absolute $C_0$, this programme gives $\chi (H)=O(\Delta /\log \Delta )$. The one-round fixed-fraction saving proved above alone does not establish that logarithmic improvement.

To show the order is best possible, let $d\to \infty$ through integers and sample $G(n,d/n)$ with $n=d^7$. A Chernoff bound and union bound give maximum degree at most $2d$ with probability tending to one. The expected triangle count is at most $d^3/6=o(n)$, so fewer than $n/2$ vertices need be deleted to remove all triangles with high probability. For $s=\lceil 4n\log d/d\rceil$, the expected number of independent $s$-sets is at mostits logarithm is at most $s[\log (ed/(4\log d))-2\log d+o(1)]$, which tends to minus infinity. The altered triangle-free graph thus has at least $n/2$ vertices and independence number below $s$, giving $\chi \ge (c+o(1))d/\log d$ for an absolute positive $c$. Append a disjoint star graph whose centre has vertex degree $2d$ if needed to make its maximum degree exactly $\Delta =2d$. This proves the triangle-free chromatic lower bound at bounded maximum degree, $\chi =\Omega (\Delta /\log \Delta )$, so the preceding order cannot be improved in general.

Use the independent product measure on the finite coordinate spaces. For $A\ne \varnothing$, let $V_A(x)$ be the convex hull of its mismatch vectors $(1_{x_i\ne y_i}{)}_{i=1}^n$, $y\in A$. The distance in the question equalsTo verify this, let $v_{\ast }$ be the nearest point. Any unit vector $\alpha$ satisfies ${\min }_{v\in V_A}\alpha \cdot v\le \alpha \cdot v_{\ast }\le \Vert v_{\ast }{\Vert }_2$. Conversely the projection property $v_{\ast }\cdot (v-v_{\ast })\ge 0$ gives equality for $\alpha =v_{\ast }/\Vert v_{\ast }{\Vert }_2$ when $v_{\ast }\ne 0$. If $v_{\ast }=0$, nonnegative weights give supremum zero. Linear functionals have the same minimum on the hull as on its original vectors, so this is exactly the quantified definition of the Talagrand convex distance.

We prove the stronger section induction for the Talagrand exponential moment,Zero-probability atoms may be discarded, replacing $A$ by its supported part: this preserves its probability and can only increase its distance. Thus assume all coordinate atoms have positive mass. The induction starts with zero coordinates, when a positive-probability event is the singleton space and its distance is zero.

Split the last coordinate into values $j$, with probabilities $q_j$, and write $A_j$ for the corresponding section in the first $n-1$ coordinates. Put $a_j=\mathrm{Pr}(A_j)$, choose a largest section $A_s$ of probability $a>0$, and set $r_j=a_j/a\in [0,1]$. For a point $(x^{\prime },j)$, mix nearest mismatch vectors from $A_j$ and $A_s$ with weights $\lambda ,1-\lambda$. Their final coordinates are zero and, if $j\ne s$, one. Convexity of the squared norm givesFor an empty $A_j$, use $\lambda =0$ directly. If $j=s$, the final-coordinate term is an unnecessary nonnegative allowance, so the bound still holds.

Exponentiate, integrate in $x^{\prime }$, and use Hölder's inequality and the induction hypothesis. For $r_j>0$ this givesWe supply the scalar estimate for Talagrand product induction used in the last step. Set $L=-\log r$. For $0\le L\le 1/2$, choose $1-\lambda =2L$, making the expression $e^{L-L^2}$. The functionhas $h(0)=h^{\prime }(0)=0$ andThus $e^{L-L^2}\le 2-e^{-L}$. For $L\ge 1/2$, choose $\lambda =0$, giving $e^{1/4}$; the already proved boundary case and monotonicity of $2-e^{-L}$ give the same bound. For $r=0$, the direct empty-section bound is $e^{1/4}/a\le 2/a$.

Now average over $j$. With $m={\sum }_j{q}_j{r}_j=\mathrm{Pr}(A)/a\in (0,1]$, the exponential integral is at most $(2-m)/a$. Since $m(2-m)\le 1$, this is at most $1/(am)=1/\mathrm{Pr}(A)$, closing the induction.

Finally apply the Markov inequality to the nonnegative exponential. For the distance-tail event ${\overline{A}}_t$,This proves Talagrand's convex distance inequality for the finite product. If $\mathrm{Pr}(A)=0$, the required probability-product inequality is immediate, including the empty-event case with distance defined as infinity; no finite exponential-moment assertion is needed there.

The parameter relations give $\mu =\log (n/c)$ andFor each fixed integer $r\ge 1$, take an $r$-vertex set $S$ and let $X_S$ count triangles meeting $S$. The event that every vertex of $S$ is counted by $T$ is exactly $X_S=0$.

The number of such triangles isThus their total expected count is ${\mu }_S=N_S{p}^3=r\mu +O_r(n{p}^3)=r\mu +o(1)$.

Distinct triangles have dependent containment events only when they share an edge. If that common edge meets $S$, there are $O_r(n)$ choices for it and $O(n^2)$ choices for the two other vertices. If the common edge avoids $S$, both other vertices must lie in $S$, giving only $O_r(n^2)$ pairs. Each pair needs five edges. Consequently its ordered Janson dependency sum isJanson inequality gives the upper bound $\mathrm{Pr}(X_S=0)\le \exp (-{\mu }_S+{\Delta }_S/2)$. For the lower bound, the avoidance of each triangle is a decreasing event. Repeated application of Harris' inequality givesThe error $n^2{p}^6=O((\log n{)}^2/n^2)$ also tends to zero. The bounds match multiplicatively:Summing over ordered distinct vertices yields the factorial moments

Here is an explicit justification that these moments determine the limit. For every integer $t\ge 0$, the finite alternating sumsare upper bounds for $\mathrm{Pr}(T=t)$ when $L$ is even and lower bounds when $L$ is odd. This follows by applying the Bonferroni inequalities to $\left(\genfrac{}{}{0ex}{}{T}{t}\right){\sum }_j(-1{)}^j(\genfrac{}{}{0ex}{}{T-t}{j})$; the full sum is precisely the indicator of $T=t$. First let $n\to \infty$ for a fixed truncation and use the factorial-moment limits. Then let the even and odd truncations grow. Both bounds tend toHence every point probability has the Poisson distribution limit, proving the Poisson threshold for vertices lying in no triangle:This is also the factorial-moment criterion for Poisson convergence, here justified rather than left as an unproved implication.

On an independent Bernoulli product measure, the Harris-Kleitman inequality states that increasing events $E,F$ obeyThe same holds for two decreasing events; an increasing and a decreasing event have the reversed inequality.

Prove the stronger function version by induction on the number of coordinates. For increasing bounded functions $f,g$, condition on the last coordinate $Z$, with $\mathrm{Pr}(Z=1)=p$. The law of total covariance givesThe first term is nonnegative by induction, and the other factors are nonnegative by monotonicity. The one-coordinate case is the same formula without the first term. Event indicators prove the assertion. Two decreasing functions follow by replacing both by their negatives; replacing only one gives negative correlation of increasing and decreasing events.

Here is a precise Janson inequality and its lower-tail concentration form. Let $I_i$ indicate containment of a specified set of independent Bernoulli coordinates, set $X={\sum }_i{I}_i$, $\mu =\mathbb{E}X$, and letThis Janson dependency sum is ordered and excludes the diagonal. ThenA zero denominator means the trivial case $X=0$ almost surely.

To prove the avoidance bound, expose the avoidance events in order. For a fixed $i$, separate earlier indices into those whose supports are disjoint from $S_i$ and those overlapping it. Write $C$ for avoidance of the first group and $D$ for avoidance of the second. The event $C$ is independent of $I_i$, while $C$ is decreasing and $\{I_i=I_j=1\}$ is increasing. The correlation inequality therefore givesThe first inequality divides a nonnegative numerator by $\mathrm{Pr}(D\mid C)\le 1$; the second uses a union bound and negative correlation with $C$. Conditioning events of zero probability already make full avoidance impossible. Multiply the resulting conditional avoidance bounds to obtain the Janson sequential product lemma. Taking logarithms and using $\log (1-u)\le -u$ gives $-\mu +\Delta /2$, since each unordered dependency pair is counted once in the sequential sum.

For the Janson lower-tail bound by independent thinning, attach independent selectors of probability $t$ to the events. Their total expectation and dependency sum are $t\mu ,t^2\Delta$, so avoidance of the selected events givesSet $t=1-e^{-s}$ and apply the exponential Markov bound to $e^{-sX}$. Using $s-s^2/2\le 1-e^{-s}\le s$ yieldsChoosing $s=a/(\mu +\Delta )$ proves the concentration assertion. For avoidance alone, optimizing $-t\mu +t^2\Delta /2$ also gives $e^{-{\mu }^2/(2\Delta )}$ when $\Delta \ge \mu$, and the original bound gives $e^{-\mu /2}$ when $\Delta \le \mu$.

To outline the sharp chromatic application, view an independent set of $G(n,p)$ as a clique of its complement, whose edge probability is $q=1-p$. Fix $0<\epsilon <1$, let $m=\lceil n/(\log n{)}^2\rceil$ and $r=\lfloor (2-\epsilon ){\log }_{b}n\rfloor$. For a particular $m$-vertex set, let $X$ count independent $r$-sets. Then $\mu =\left(\genfrac{}{}{0ex}{}{m}{r}\right)q^{\left(\genfrac{}{}{0ex}{}{r}{2}\right)}$, and the overlap calculation givesOverlap of only one vertex shares no edge, hence is independent. For completeness, the summand is at most $(r^2/(m-r){)}^{\ell }{b}^{\left(\genfrac{}{}{0ex}{}{\ell }{2}\right)}/\ell !$. Since $r\le (2-\epsilon /2){\log }_{b}m$ eventually, large overlaps are bounded by $m^{-c_{\epsilon }\ell }$; finitely many smaller overlaps are dominated by $\ell =2$. Also $\log \mu ={\Omega }_{p,\epsilon }((\log m{)}^2)$, so the diagonal contribution $1/\mu$ is negligible. The concentration bound consequently givesA union bound over at most $2^n$ vertex sets still tends to zero. Thus independent sets in every large subset of a dense random graph are available uniformly, including adaptively obtained remainders. Repeatedly remove an independent $r$-set and give it a new colour, then colour the fewer than $m$ leftover vertices individually. This uses at most $n/r+m$ colours. Combining with the first-moment lower bound and letting fixed $\epsilon$ be arbitrarily small gives the accurate leading asymptoticThe uniform subset estimate, rather than merely the existence of one large independent set, is what makes the sharp upper bound possible.

Identify ${\mathbb{N}}^{(\omega )}$ with the space of infinite subsets of the natural numbers. A family $E$ has an infinite homogeneous set for a colouring if some infinite $M$ satisfiesThis is the Ramsey family in the homogeneous-cone sense formulation. The relative Ramsey set of infinite subsets formulation asks for such an $M$ inside every prescribed infinite ground set. We prove the stronger completely Ramsey assertion, keeping an arbitrary finite stem fixed.

For a finite stem $s$ and an infinite tail $A$ with $\max s<\min A$ (taking $\max \varnothing =0$), writeThese neighbourhoods generate the Ellentuck topology, or star topology. A star-Borel set belongs to the sigma-algebra generated by the open sets of this topology. It is completely Ramsey if every $[s,A]$ has an infinite $B\subseteq A$ with $[s,B]\subseteq E$ or $[s,B]\cap E=\varnothing$. Taking $s=\varnothing$ gives both preceding Ramsey formulations.

We first prove the fusion proof for open Ellentuck sets. Fix a star-open set $U$ and a starting neighbourhood $[s,A]$. A reservoir $C$ above a finite extension $s\cup t$ accepts $t$ when $[s\cup t,C]\subseteq U$. It rejects $t$ when no infinite subreservoir accepts it. Every infinite reservoir has a refinement deciding $t$: if an accepting subreservoir exists choose one, and otherwise the reservoir already rejects. Both acceptance and rejection persist under further infinite thinning. These are acceptance and rejection of finite stems.

First refine $A$ to decide the empty extension. Choose $d_0$ from the refined reservoir and thin the remaining tail to decide every subset of $\{d_0\}$. After choosing $d_0,\dots ,d_j$, thin the unused infinite tail to decide every subset of this finite prefix before choosing $d_{j+1}$. Only finitely many decisions occur at each stage. Let $D=\{d_0<d_1<\cdots \}$. For each finite $t\subseteq D$, its tail(with $D_{\varnothing }=D$) is contained in the reservoir chosen when the largest point of $t$ was selected. Thus $D_t$ decides $t$. This is deciding all finite stems by fusion.

If $D$ accepts the empty extension, $[s,D]\subseteq U$ and we are done. Otherwise it rejects it. Call a finite $t\subseteq D$ accepted or rejected according to the decision of $D_t$. For each rejected $t$, the setis finite. Indeed, if $G_t$ were infinite, every $X\in [G_t{]}^{\omega }$ would have a least element $a$ with $t\cup \{a\}$ accepted, and its remaining tail lies in $D_{t\cup \{a\}}$. Hence $s\cup t\cup X\in U$ for every such $X$, making $G_t$ an accepting subreservoir for $t$, a contradiction. This proves the finitely many accepting extensions of a rejected stem fact.

Build $B=\{b_0<b_1<\cdots \}\subseteq D$ by choosing each new point outside all the finitely many sets $G_t$ for subsets $t$ of the already selected prefix. Begin with the rejected empty extension. Inductively every finite subset of the new prefix is rejected: the old subsets stay rejected, and each new subset is a rejected $t$ extended by a point outside $G_t$, whose decision must therefore be rejection. Consequently every finite $t\subseteq B$ is rejected.

If a point $X\in [s,B]$ belonged to $U$, star-openness would give a basic neighbourhood $[u,C]\subseteq U$ containing it. Extend $u$ along the increasing enumeration of $X$, if necessary, until its stem is $s\cup t$ for a finite $t\subseteq B$. The infinite tail of $X$ above that stem then provides an accepting subreservoir for $t$, contradicting rejection. Therefore $[s,B]\cap U=\varnothing$. We have proved that every star-open set is completely Ramsey.

A family $N$ is completely Ramsey-null when every $[s,A]$ has a stem-preserving refinement disjoint from $N$. Every star-nowhere dense set has this property. Apply the open-set result to the dense open complement of its star-closure. The disjoint alternative would put an entire basic neighbourhood inside a closure with empty interior, which is impossible. The other alternative gives the required avoidance.

We also need the full Ellentuck meagre-set fusion lemma, not a diagonal argument checking only one prefix. Let $N_0,N_1,\dots$ be completely Ramsey-null, and start inside $[s,A]$. At stage $j$, suppose $b_0,\dots ,b_{j-1}$ have been chosen. Refine the remaining infinite tail successively so thatThe null property permits each refinement with its stem unchanged; previous avoidance survives thinning. There are finitely many $t$ at this stage. Choose $b_j\in C_j$ and continue above it. Let $B=\{b_j:j\ge 0\}$.

For any infinite $Y\subseteq B$ and any fixed $j$, put $t=Y\cap \{b_0,\dots ,b_{j-1}\}$. Its remaining points form an infinite subset of $C_j$, so $s\cup Y\in [s\cup t,C_j]$ and hence $s\cup Y\notin N_j$. This works for every $j$, provingThus countable unions of completely Ramsey-null sets are null. Subsets of null sets are null as well. In particular every star-meagre set, being a countable union of star-nowhere-dense sets, is completely Ramsey-null.

Finally let $\mathcal{B}$ consist of families $E$ such that $E△U$ is contained in a star-meagre set for some star-open $U$. This is the Baire property in the Ellentuck topology. We verify that it forms a sigma-algebra. Open sets belong with empty error. For a countable union, use $U={\bigcup }_j{U}_j$; its error is contained in the countable union of the meagre errors. For complements, replace $U^c$ by its interior. The discrepancy isa closed nowhere-dense set: every open set meeting $\overline{U}$ also meets $U$, so none can lie wholly in this boundary. Adding it to the original meagre error handles complementation. Consequently every star-Borel set belongs to $\mathcal{B}$.

For such an $E$, start with any $[s,A]$. First apply null avoidance to its meagre error to find $[s,B]$ on which $E$ agrees with $U$. Then apply open-set homogeneity to refine it to $[s,C]$ wholly inside or outside $U$, and therefore wholly inside or outside $E$. This is the Baire-property reduction for completely Ramsey families. We concludeAll closures, interiors, openness and meagreness in this argument refer to the star topology; replacing it midway by the ordinary finite-prefix topology would not justify the null-avoidance step.

For a rational $\ell \times n$ matrix $A$, write its columns as $c_1,\dots ,c_n$. It is partition regular if every finite colouring of $\mathbb{N}$ admits positive integers $x_1,\dots ,x_n$, all of one colour, with $A\mathbf{x}=0$. Repeated coordinates are allowed. The columns condition is an ordered partitioninto nonempty blocks such thatRado's theorem states that a rational matrix is partition regular if and only if it satisfies the columns condition. We prove both implications.

For necessity, clear denominators so the columns are integral. For every disjoint pair of index sets $I,B$ with $B\ne \varnothing$ andchoose a rational linear functional annihilating all columns in $I$ but not $v_B$. Such a functional exists by extending a basis of the indicated linear span to include $v_B$, prescribing zero on the former and one on the latter. Clearing its denominators produces an integer-coefficient functional $f_{I,B}$ with $f_{I,B}(v_B)$ a nonzero integer. There are only finitely many pairs $I,B$. Choose a prime number $p$ dividing none of these nonzero evaluations; if there are no bad pairs, choose any prime.