The comma category has objects with and a function . A morphism is an arrow such that . Identities and composition come from . When , a map selects an element of , so this is the covariant category of elements of .
The currying adjunction for small categories uses the bijection
It sends to the functor , with an arrow inducing the natural transformation whose -component is . Conversely, for , define its uncurried functor by and
Naturality of allows the two factors to be interchanged in the appropriate order, giving functoriality. The constructions are inverse and natural in and . Hence is a left adjoint to on the category of small categories.
The unit sends to the functor and to the transformation . The counit is evaluation : and .
Define the correspondence from the given natural transformations by , with candidate inverse . For , naturality of and a triangle identity for an adjunction give
For , naturality of and the other triangle identity give
These are inverse bijections. Naturality of , , and makes the bijections natural in and , so they define an adjunction with the required unit and counit. Uniqueness follows from the formulas in the previous part: any adjunction with that unit and counit must have exactly these transposition maps.
An adjunction is a family of bijections
natural in both variables. Its adjunction unit and adjunction counit are and . Naturality of the correspondence gives
For , naturality in both variables evaluates in two ways, giving . Thus is a natural transformation; the dual calculation gives naturality of .
Applying the inverse correspondence to and the correspondence to yields the triangle identities for an adjunction:
They express that transposing an identity morphism and transposing back returns that identity.
Construct pointwise limits in a functor category. For , choose at each object a categorical limit of , with projections . For , the family is compatible; define uniquely by
The universal property gives and , since those equalities hold after every projection. Thus is a functor, and each is a natural transformation.
For any categorical cone , the pointwise categorical limits give unique maps . To check naturality, compose and with every ; both become . The projections distinguish arrows into their categorical limit, so the two maps agree. Componentwise uniqueness gives uniqueness of the natural transformation . This proves that really is the required categorical limit, rather than merely a family of objectwise candidates.
A specified categorical limit categorical cone in fixes these objectwise vertices and projections. The displayed equation forces every arrow , and the argument forces every categorical cone factorization. Hence the forgetful functor uniquely lifts that categorical cone and is a limit-creating functor. The construction only takes small categorical limits in ; it does not require to be small. As usual, the functor categories are understood in a universe where their collections of transformations are meaningful.
For a diagram , a limit-preserving functor carries every limiting cone over a diagram to a limiting categorical cone. A limit-reflecting functor has the converse property: a categorical cone is limiting whenever its image is limiting. A limit-creating functor uniquely lifts every specified limiting categorical cone over the image diagram to a categorical cone over , and the lift is limiting. These definitions concern diagrams of the stipulated shape; creation includes the lifting requirement, not merely reflection.
Let be a categorical limit of . The map
is a bijection: the right side consists exactly of compatible families of arrows from , and the categorical limit's universal property gives their unique factorization through . The bijection is induced by the categorical limit projections, so it proves that covariant representables preserve limits, including the empty diagram and its terminal object.
A split coequalizer consists of , , and with , , and . If , then . Thus factors through , and the factor is unique because has the right inverse . This proves the coequalizer property directly. Every functor preserves the diagram, since all these equations are preserved.
For idempotent splitting through a coequalizer, first suppose with . Then . Any satisfying factors as , uniquely since is a split epimorphism. Hence coequalizes .
Conversely, let coequalize . Since , the arrow itself equalizes the pair, so there is a unique with . Then , and every coequalizer is an epimorphism, so . Thus is a splitting of an idempotent morphism.
A monomorphism satisfies , and an epimorphism satisfies . A strong monomorphism is a monomorphism with the right lifting property against all epimorphisms: every square has a diagonal satisfying and . The diagonal is unique by monicity. A regular monomorphism is an equalizer of some pair . It is monic because two equalizer factorizations of the same arrow must agree.
The converted TeX omits the remainder of this subpart. For the printed strict monomorphism condition, an arrow is admissible when, for every pair out of , the implication holds; strictness says each such factors uniquely through . If equalizes , every admissible satisfies , and the equalizer property supplies its unique factorization. Hence every regular monomorphism is strict.
Strictness itself implies monicity: whenever , the common composite is admissible, so uniqueness of its factor through gives . Now take a square with epic. Whenever , we have , hence . Thus is admissible and has a unique factor through . Monicity gives . We have proved the chain
A representation of a functor is with such that is a bijection for every . These bijections are natural by functoriality. The element is its universal element.
If is another representation, universality gives unique arrows and satisfying and . Consequently , so by injectivity of the representing bijection. Similarly . Therefore is the unique compatible isomorphism. This proves uniqueness of functor representations; uniqueness refers to an isomorphism carrying the specified universal elements to one another, rather than to every isomorphism between the underlying objects.
Use the covariant Yoneda embedding . An arrow , viewed as an arrow in the opposite category, induces precomposition . Identities and composition are preserved because composition in is associative.
The covariant Yoneda lemma is the bijection
Its inverse sends to . This is a natural transformation: for , functoriality gives . Conversely, naturality of an arbitrary at gives . Evaluation at the identity morphism therefore makes the two constructions inverse. Their formulas also prove naturality in and, contravariantly, in .
Taking identifies natural transformations with . Thus is full and faithful, and reflects isomorphisms; two image objects are isomorphic exactly when the original objects are isomorphic. It also carries existing colimits in to categorical limits of covariant representable functors: maps out of a colimit are exactly compatible families of maps out of its diagram. Equivalently, this embedding preserves existing categorical limits in . The direction matters: the paper uses covariant representables, rather than the more usual contravariant Yoneda embedding.
Let collapse the indicated Complex projective space. Write for the positive generator, so the cohomology ring of complex projective space is . The inclusion of sends to its corresponding generator and is an isomorphism in degrees .
The CW complex structure makes the inclusion a cofibration, so the positive-degree cohomology of identifies with the relative cohomology of the pair. Its long exact sequence shows that is injective in positive degrees, with image the additive subgroup generated by . Equivalently, the surviving cellular cochain complex has one copy of in each of degrees and zero differential. Let denote the class with , for .
Naturality of the cup product, together with the injectivity of , now determines all multiplication:
Every other product of positive-degree basis elements is zero. Indeed, their degrees exceed . In particular, the surviving classes do not form a polynomial algebra on a degree-eight generator: the independent classes in degrees must also be retained. This is an instance of the cohomology ring of a collapsed projective subspace.
Write and . Choose unit complex numbers so that
is real and nonnegative. Cauchy-Schwarz, using , bounds by
After setting , each summand is a unit phase times the Fourier coefficient on a finite abelian group of at frequency .
Let count pairs with and . Grouping terms, another Cauchy-Schwarz and the Parseval identity yield
where is the additive energy of a frequency graph. The last inequality uses for each .
Thus
The bound proves that derivative correlations force additive frequency energy. This energy counts exactly the ordered quadruples satisfying the two requested additive relations, after relabelling the difference equality as a sum equality. Shift equalities initially hold modulo , but the shifts lie in and , so they are also integer equalities. Frequency equalities hold in , as required. Consequently a common exponent works for both conclusions, after adjusting absolute implicit constants and using .
For the quadratic phase, the multiplicative derivative on the overlap is . Hence an explicit choice is
Take . The correlation magnitude is , and every additive quadruple of shifts satisfies the frequency relation. The interval of shifts has such quadruples by Cauchy-Schwarz. These particular real frequencies need not belong to the grid used to prove existence for general ; evaluating them at the interval's integer coordinates gives the stated exact formula.
A genuinely nonlinear example is the bracket-linear frequency function
It has exact additive quadruples, yet agrees with any affine function at only shifts, uniformly in the affine function. The question permits giving this example without proof, but the mechanism is useful. For a pair with sum , the value has only two possibilities, or . There are pair classes, so Cauchy-Schwarz produces collisions with both additive relations.
To see why no long affine agreement occurs, three agreement points force the corresponding lattice points to be collinear: eliminating the affine slope gives times an integer determinant equal to an integer, and irrationality makes that determinant zero. A rational line of slope contains agreement shifts in one residue class modulo , and closeness of to bounds their span by . Lines with large have arbitrarily small possible density; for bounded , irrationality of bounds the number uniformly. Thus the maximum agreement is .
The Gowers U3 norm derivative identity is
Let . Since , by repeated Cauchy-Schwarz, the interval hypothesis gives . Also . Therefore the set
has density at least in .
Use normalized Fourier coefficients on a finite abelian group . The Gowers U2 norm and Parseval identity give
For , the final mean is at most one. Thus each has a frequency with
The derivative is identically zero unless is represented by an integer in , so lies in the requested interval of shifts. Its size is . Keep one such frequency for each shift; these same choices will satisfy the energy conclusion below.
The persistence of unsampled graph components prevents the mass from each size band from disappearing entirely before . More precisely, a band containing at least vertices retains at least vertices in that same band after at most steps, with high probability, for a fixed depending only on . To see why, each initial graph component in that band has a fixed positive probability that none of the offered edge endpoints touches it during the interval. Such a graph component remains unchanged regardless of the selection rule. The McDiarmid inequality concentrates the total mass of these untouched graph components. The reusable lemma supplies the full uniform-in-starting-time argument, including the version that samples absent edges.
Choose finitely many disjoint bands , , with . Part (i) provides at least vertices in band at its time . Each interval from that time to has length at most , so persistence leaves at least vertices in every one of these disjoint bands at the common time . A union bound over this fixed finite number of bands makes all the conclusions simultaneous. Their total exceeds , a contradiction. No fixed two-choice Achlioptas rule satisfies the explosive percolation hypothesis.
This continuity of fixed-choice percolation is the fixed-choice obstruction proved by Riordan and Warnke; their original research paper also treats a broader class of rules. The argument here does not apply when the number of offered choices grows with .
Use the standard Achlioptas process with two independent uniform candidate edges per step and a rule choosing one. The component-band vertex count counts vertices, not the number of graph components. Integer time rounding changes the arguments below by steps.
First, at the eventual graph component of order at least is assembled from graph components already present at . Contract those initial graph components. During steps, at most new edges are added, so the eventual connected contracted graph contains at most initial graph components. Initial graph components of order less than can therefore contribute at most
vertices, for sufficiently large and fixed , since . For their contribution is zero. Consequently .
We now use forced merging of large components. If at a time the graph components of order at least contain at least vertices, then after at most steps there is a graph component of order at least , except on an event of probability exponentially small in . One explicit choice is . The proof is a union bound over set partitions of the at most initial large graph components: if all final graph components were small, a balanced component cut would split their initial vertices into sets of size at least , and both candidate edges cross that fixed cut with probability at least in every step. The rule cannot avoid such a forced crossing. The failure bound is , and a union bound makes the estimate simultaneous over all starting times at most , for each fixed .
Set and choose a fixed integer with . If , this lemma would produce a graph component of order at least by time
That contradicts the assumed . Thus , and subtraction gives
The same works for every fixed ; it depends only on , with the number of offered edges fixed at two.
Write , , , and let be the total progeny of a binomial branching process. The preceding binomial branching survival correction gives . For a branching process conditioned on extinction, the offspring probability generating function is , with mean
for sufficiently large . Summing expected generation sizes therefore gives .
Put and let count vertices in graph components of order at least . A breadth-first exploration of a binomial random graph is dominated by . The Markov inequality applied to finite total progeny gives
Always . Since , we have and . Hence . This bound controls the expected value directly, including rare large graph components.
For the lower bound, use the breadth-first exploration of a binomial random graph with unseen vertices, active vertices and explored vertices, starting from , . Let indicate a new root. Conditional on the past, the newly discovered count has a binomial distribution . Put . The unseen-count recursion gives
Here is a martingale. Up to , martingale-difference orthogonality gives , since each conditional variance is at most and is bounded.
Take . Then , and . The Doob L2 maximal inequality implies
The Taylor expansion, uniformly for , gives . Thus throughout the integer interval for large . The new-root sum is nonnegative, so on the preceding event throughout this interval. No graph component finishes there: all these explored vertices belong to one graph component, of order at least , with high probability. Its expected value is therefore at least . Combining both inequalities proves
The barely-supercritical largest-component expectation uses both a positive exploration window and a finite-progeny bound; a bare convergence-in-probability assertion would not by itself justify this expectation.
For the binomial branching process, the offspring probability generating function is . The Galton-Watson extinction fixed point gives .
The printed finite-binomial upper bound is false without an additional asymptotic qualification. For and , solving the fixed-point equation exactly gives
For instance gives . More generally, at every fixed the Taylor expansion gives , again contradicting that upper bound for sufficiently small positive .
Here is the corrected binomial branching survival correction. The Poisson branching process of mean has branching survival probability satisfying . Expanding the logarithm gives
Thus , which implies the requested lower estimate . Since on , iteration of the two offspring probability generating functions gives .
For the actual binomial branching process, expansion of its exact fixed-point equation gives
If , all coefficients are nonnegative. Keeping the first term proves
In particular, for and this gives . The printed bounds also hold for the binomial branching process in an explicit large- regime: and . Indeed these conditions give and . In the preceding nonnegative series, evaluation at gives
The series is increasing, and its value at the actual branching survival probability is , so . Together with the lower bound already proved, this recovers in that regime. In particular it applies eventually to part (ii). The counterexample shows why a regime condition is needed for a literal finite- statement.
Figure 1.
Finite-binomial survival exceeds the printed upper bound, while Poisson survival lies between the corrected comparison bounds
. Details.
The function is strictly increasing on and strictly decreasing on . Hence for each there is a unique with .
Apply the subcritical component estimates to . For a specified vertex, the exact tree-component expectation in the Erdős-Rényi model gives the limiting probability that it lies in a tree component of order :
For each fixed , the probability of a non-tree graph component of that size is : a spanning tree and one extra edge are necessary. Moreover the Galton-Watson process exploration estimate from the preceding proof bounds the probability of order greater than by , uniformly in , where . First let for fixed , then let . No probability mass escapes to large components or non-tree components, so . Multiplying by and using its defining identity gives
Equivalently, the rooted-tree generating function selects the smaller solution of . The choice of that branch is essential; the larger solution is not the value of this convergent series.
Assume , as required for this nontrivial subcritical binomial random graph. Put . A breadth-first exploration of a binomial random graph is dominated by a Galton-Watson process whose offspring counts are independent random variables with law . If its total progeny is at least , the first offspring counts sum to at least . Their moment-generating function is bounded by that of a Poisson distribution of mean . The exponential Markov inequality, optimized at , yields
Taking for any fixed , a union bound over all starting vertices gives .
For the matching lower bound, let count tree components of order . The tree-component expectation in the Erdős-Rényi model is exactly
For , the Stirling formula gives
Choose , with . Then . Distinct overlapping vertex sets cannot both be graph components. For disjoint sets, the joint probability differs from the product only because the between-set edges were counted twice as absent. Thus
It follows that . The second moment method gives with high probability. Combining both bounds, and then taking arbitrarily small fixed , proves the sharp subcritical largest-component scale
Finally the Taylor expansion of gives . The endpoint has no edges and is excluded from this logarithmic asymptotic.
If some choice produced a graph with largest component of a graph smaller than , the balanced component cut result with packing parameter one would give an empty graph cut whose sides both have at least vertices. For any fixed such vertex set partition, a uniform edge of the complete graph crosses with probability
To avoid crossing in row , at least one of its offered edges must be noncrossing. The row's probability is . The rows consist of independent random variables, so at a union bound over at most vertex set partitions gives
For example, the positive integer
makes this bound at most . Therefore every choice has a component of order at least , with probability tending to one. The simultaneous giant for fixed random-edge choice estimate includes choices made after seeing the entire array; it does not assume a particular online selection rule.

Pinned article: Introduction to the OurBigBook Project

Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.
Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!
We have two killer features:
  1. topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculus
    Articles of different users are sorted by upvote within each article page. This feature is a bit like:
    • a Wikipedia where each user can have their own version of each article
    • a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
    This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.
    Figure 1.
    Screenshot of the "Derivative" topic page
    . View it live at: ourbigbook.com/go/topic/derivative
  2. local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:
    This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
    Figure 5. . You can also edit articles on the Web editor without installing anything locally.
    Video 3.
    Edit locally and publish demo
    . Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension.
  3. https://raw.githubusercontent.com/ourbigbook/ourbigbook-media/master/feature/x/hilbert-space-arrow.png
  4. Infinitely deep tables of contents:
    Figure 6.
    Dynamic article tree with infinitely deep table of contents
    .
    Descendant pages can also show up as toplevel e.g.: ourbigbook.com/cirosantilli/chordate-subclade
All our software is open source and hosted at: github.com/ourbigbook/ourbigbook
Further documentation can be found at: docs.ourbigbook.com
Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact